[CF1316F] Battalion Strength

题目链接

Solution

考虑每一个数对 $(i,j)\ (i<j)$ 的贡献，它等于 $i,j$ 同时出现且之间没有数字出现的概率 $\frac{1}{2^{j-i+1}}$ 乘上能力值之积，即 $\frac{p_ip_j}{2^{j-i+1}}$. 于是答案可写作：

$$\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n\frac{p_ip_j}{2^{j-i+1}}=\sum\limits_{i=1}^n\left[2^{i-1}p_i\sum\limits_{i+1}^n\frac{p_j}{2^j}\right]$$

要维护修改操作，容易想到用值域线段树完成，考虑如何 pushup：

运用和 CDQ 分治类似的思想，我们只需要考虑如何统计 $i$ 从左子区间取、$j$ 从右子区间取的贡献。设左子区间共有 $k$ 个数，那么 $i\leq k<j$，于是贡献为：

$$\left(\sum\limits_{i=1}^k2^{i-1}p_i\right)\left(\sum\limits_{j=k+1}^n\frac{p_j}{2^j}\right)=\left(\sum\limits_{i=1}^k2^{i-1}p_i\right)\frac{\left(\sum\limits_{j=1}^{n-k}\frac{p_j}{2^j}\right)}{2^k}$$

因此每个线段树节点维护四个信息：

• $val$：即答案
• $cnt$：有多少个数
• $Lval=\sum\limits_{i=1}^{cnt}2^{i-1}p_i$
• $Rval=\sum\limits_{i=1}^{cnt}\frac{p_i}{2^i}$

pushup 时：

• $val=val_l+val_r+\frac{Lval_l\cdot Rval_r}{2^{cnt_l}}$
• $cnt=cnt_l+cnt_r$
• $Lval=Lval_l+Lval_r\cdot 2^{cnt_l}$
• $Rval=Rval_l+\frac{Rval_r}{2^{cnt_l}}$

最后，在叶节点处做更改时需要手推一下式子；幂次预处理，否则会 TLE.

Code

#include<algorithm>
#include<cstdio>

using namespace std;

template<typename T>void read(T&x){x=0;int fl=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')
fl=-1;ch=getchar();}while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}x*=fl;}
template<typename T,typename...Args>inline void read(T&t,Args&...args){read(t);read(args...);}

typedef long long LL;

const int N = 300005;
const LL MOD = 1000000007;

int n, q;
LL t[N<<1], P[N], invP[N], p[N], maxx;
struct Query{
    int pos;
    LL x;
}que[N];

void disc(){
    sort(t+1, t+t[0]+1);
    t[0] = unique(t+1, t+t[0]+1) - (t+1);
    for(int i = 1; i <= n; i++){
        p[i] = lower_bound(t+1, t+t[0]+1, p[i]) - t;
        maxx = max(maxx, p[i]);
    }
    for(int i = 1; i <= q; i++){
        que[i].x = lower_bound(t+1, t+t[0]+1, que[i].x) - t;
        maxx = max(maxx, que[i].x);
    }
}

inline LL fpow(LL bs, LL idx){
    LL res = 1;
    bs %= MOD;
    while(idx){
        if(idx & 1) (res *= bs) %= MOD;
        (bs *= bs) %= MOD;
        idx >>= 1;
    }
    return res % MOD;
}

struct segTree{
    int l, r;
    LL val, Lval, Rval, cnt;
}tr[N<<3];
#define lid id<<1
#define rid id<<1|1
#define mid ((tr[id].l + tr[id].r) >> 1)
inline void pushup(int id){
    tr[id].val = (tr[lid].val + tr[rid].val + tr[lid].Lval * tr[rid].Rval % MOD * invP[tr[lid].cnt]) % MOD;
    tr[id].Lval = (tr[lid].Lval + tr[rid].Lval * P[tr[lid].cnt]) % MOD;
    tr[id].Rval = (tr[lid].Rval + tr[rid].Rval * invP[tr[lid].cnt]) % MOD;
    tr[id].cnt = tr[lid].cnt + tr[rid].cnt;
}
void build(int id, int l, int r){
    tr[id].l = l, tr[id].r = r;
    tr[id].val = tr[id].Lval = tr[id].Rval = tr[id].cnt = 0;
    if(tr[id].l == tr[id].r)    return;
    build(lid, l, mid);
    build(rid, mid+1, r);
    pushup(id);
}
void add(int id, int x, int val){
    if(tr[id].l == tr[id].r){
        tr[id].cnt += val;
        if(tr[id].cnt > 0)
            tr[id].val = t[x] * t[x] % MOD * ((tr[id].cnt * P[tr[id].cnt-1] - P[tr[id].cnt] + 1) % MOD) % MOD * invP[tr[id].cnt] % MOD;
        else    tr[id].val = 0;
        tr[id].Lval = (P[tr[id].cnt] - 1) % MOD * t[x] % MOD;
        tr[id].Rval = (P[tr[id].cnt] - 1) * invP[tr[id].cnt] % MOD * t[x] % MOD;
        return;
    }
    if(x <= mid)    add(lid, x, val);
    else    add(rid, x, val);
    pushup(id);
}

int main(){
    read(n);
    P[0] = 1, invP[0] = 1;
    for(int i = 1; i <= n; i++){
        read(p[i]);
        t[++t[0]] = p[i];
        P[i] = P[i-1] * 2 % MOD;
        invP[i] = fpow(P[i], MOD - 2) % MOD;
    }
    read(q);
    for(int i = 1; i <= q; i++){
        read(que[i].pos, que[i].x);
        t[++t[0]] = que[i].x;
    }
    disc();
    build(1, 1, maxx);
    for(int i = 1; i <= n; i++) add(1, p[i], 1);
    printf("%lld\n", tr[1].val);
    for(int i = 1; i <= q; i++){
        add(1, p[que[i].pos], -1);
        add(1, que[i].x, 1);
        p[que[i].pos] = que[i].x;
        printf("%lld\n", tr[1].val);
    }
    return 0;
}