题目大意：定义一个\(n\)个数的序列\(p_1,p_2,\cdots,p_n\)，若\(n=1\)，则该序列权值为\(1\)，否则定义该序列的权值是将原序列排序后相邻两项积的和，\(\text{即当}a\text{是}1 \sim n \text{的排列且满足} p_{a_1}\leq p_{a_2}\leq \cdots \leq p_{a_n}\text{时，该序列的权值为} \sum_{i=1}^{n-1} p_{a_i} \cdot p_{a_{i+1}}\)。现在给你一个\(n\)个数的序列，从中随机选取一个非空子序列（即不要求连续），假设所有的子序列被选到的概率相等，问取出的子序列的权值的期望时多少，动态带单点值修改，询问原序列和每次操作后的子序列权值的期望\(\mod 10^9+7\)的结果。
题解：先考虑静态的情况，假设没有修改操作，该怎么处理这一道题。假设数组已经有序，我们考虑两个数\(p_i,p_j\)对答案的贡献是什么，当\(p_i,p_j\)对答案产生贡献时，一定时它们全部被选上且它们中间的数全部没有被选上时的情况，概率为\(\frac{1}{2^{j-i+1}}\)，所以序列的期望权值可以写成\(\sum_{i=1}^{n} \sum_{j=i+1}^{n} p_i \cdot p_j \cdot \frac{1}{2^{j-i+1}}\)，时间复杂度\(O(n^2)\)，别说带询问了，不带询问都过不了，考虑对这个式子进行优化，令\(f_i=\sum_{j=1}^{i} p_j \cdot 2^{i-1}\)，那么答案可以写成\(\sum_{i=1}^{n} p_i \cdot \frac{1}{2^j} \cdot f_{i-1}\)，时间复杂度\(O(n)\)。
不带修改的处理完了，接下来考虑带修改的情况，因为需要排序后再处理，所以用权值线段树维护这个序列（当然，你要用平衡树我也拦不了你），考虑线段树上的每个节点应当维护什么信息，熟悉CDQ分治的同学们应该都会做，令当前区间为\((l,r)\)（假设\((l,r)\)内的每一个数都存在在原序列中），维护\(val\)为当前区间的权值，\(sz\)为当前区间内数的个数，\(Lval=\sum_{i=l}^{r} p_i \cdot 2^{i-l}\)，\(Rval=\sum_{i=l}^{r} p_i \cdot \frac{1}{2^{i-l+1}}\)。所以单点\(a\)加入时，这个点的值是这么赋的：\(val=0,sz=1,Lval=a,Rval=\frac{a}{2}\)，然后信息合并时这么合并的（令\(lc\)和\(rc\)为其在线段树上的左右孩子）：
\[val=val_{lc}+val_{rc}+\frac{Lval_{lc}\cdot (\frac{1}{2^{sz_{lc}}}\cdot Rval_{rc})}{2}\]
\[sz=sz_{lc}+sz_{rc}\]
\[Lval=Lval_{lc}+ Lval_{rc}\cdot 2^{sz_{lc}}\]
\[Rval=Rval_{lc}+ Rval_{rc}\cdot \frac{1}{2^{sz_{lc}}}\]
这样维护之后就可以了。
下面是代码：
#include <map>
#include <cstdio>
#include <algorithm>
using namespace std;
int quick_power(int a,int b,int Mod){
int ans=1;
while(b){
if(b&1){
ans=1ll*ans*a%Mod;
}
a=1ll*a*a%Mod;
b>>=1;
}
return ans;
}
void read(int &a){
a=0;
char c=getchar();
while(c<'0'||c>'9'){
c=getchar();
}
while(c>='0'&&c<='9'){
a=(a<<1)+(a<<3)+(c^48);
c=getchar();
}
}
const int Maxn=300000;
const int Mod=1000000007;
const int Inf=1000000000;
struct Question{
int x,v;
}qu[Maxn+5];
struct Segment_Node{
int lson,rson;
int l_val,r_val;
int sz,val;
}seg[(Maxn<<3)+5];
multimap<int,int> mp;
int p[Maxn+5];
int pos[Maxn<<1|5];
int Root,id_tot;
int power_2[Maxn+5],inv_2[Maxn+5];
void init(){
power_2[0]=1;
inv_2[0]=1;
power_2[1]=2;
inv_2[1]=quick_power(2,Mod-2,Mod);
for(int i=2;i<=Maxn;i++){
inv_2[i]=1ll*inv_2[i-1]*inv_2[1]%Mod;
power_2[i]=(power_2[i-1]<<1)%Mod;
}
}
void push_up(int root){
seg[root].sz=seg[seg[root].lson].sz+seg[seg[root].rson].sz;
seg[root].l_val=(seg[seg[root].lson].l_val+1ll*seg[seg[root].rson].l_val*power_2[seg[seg[root].lson].sz]%Mod)%Mod;
seg[root].r_val=(seg[seg[root].lson].r_val+1ll*seg[seg[root].rson].r_val*inv_2[seg[seg[root].lson].sz]%Mod)%Mod;
seg[root].val=(seg[seg[root].lson].val+seg[seg[root].rson].val+1ll*seg[seg[root].lson].l_val*seg[seg[root].rson].r_val%Mod*inv_2[seg[seg[root].lson].sz]%Mod)%Mod;
}
void insert(int x,int a,int &root=Root,int left=1,int right=Inf){
if(root==0){
root=++id_tot;
}
if(left==right){
if(a==1){
seg[root].sz=1;
seg[root].l_val=pos[x];
seg[root].r_val=1ll*pos[x]*inv_2[1]%Mod;
seg[root].val=0;
}
else{
seg[root].sz=0;
seg[root].l_val=0;
seg[root].r_val=0;
seg[root].val=0;
}
return;
}
int mid=(left+right)>>1;
if(x<=mid){
insert(x,a,seg[root].lson,left,mid);
}
else{
insert(x,a,seg[root].rson,mid+1,right);
}
push_up(root);
}
int main(){
init();
int n;
read(n);
for(int i=1;i<=n;i++){
read(p[i]);
mp.insert(make_pair(p[i],0));
}
int q;
read(q);
for(int i=1;i<=q;i++){
read(qu[i].x);
read(qu[i].v);
mp.insert(make_pair(qu[i].v,0));
}
multimap<int,int>::iterator it;
it=mp.begin();
int id_tot=0;
while(it!=mp.end()){
(it->second)=++id_tot;
pos[id_tot]=(it->first);
it++;
}
for(int i=1;i<=n;i++){
it=mp.lower_bound(p[i]);
p[i]=(it->second);
mp.erase(it);
}
for(int i=1;i<=q;i++){
it=mp.lower_bound(qu[i].v);
qu[i].v=(it->second);
mp.erase(it);
}
for(int i=1;i<=n;i++){
insert(p[i],1);
}
printf("%d\n",seg[Root].val);
for(int i=1;i<=q;i++){
insert(p[qu[i].x],-1);
p[qu[i].x]=qu[i].v;
insert(p[qu[i].x],1);
printf("%d\n",seg[Root].val);
}
return 0;
}Codeforces 1316F. Battalion Strength 题解
原文：https://www.cnblogs.com/withhope/p/12426661.html