1914514

· · 个人记录

因为是选子序列，把序列排序之后和原序列等价。

在第 i 个位置上存四元组 [f_i,S_i,g_i,T_i] 分别表示以第 i 个数为结尾的权值和、\sum_{j=1}^{i} f_j、以第 i 个数为结尾的方案（即 2^{cnt([1,i])-1}）、\sum_{j=1}^{i} g_j a_j，转移是简单的，于是可以直接 \text{DDP} 做到 O(k^3 n \log n)，k = 4 且 \log n 是线段树给的，算下来过不了（

换种思路，因为是期望，考虑线性性，对每个 pair (i,j)（i \gt j）计算它们的贡献，那么当且仅当 k \in (j,i) 均不被选且 i,j 均被选，也就是有 \dfrac{a_ia_j}{2^{i-j+1}} 的贡献，于是有

\large{ \sum_{i=1}^{n} \sum_{j=1}^{i-1} \dfrac{a_ia_j}{2^{i-j+1}} = \sum_{i=1}^{n} 2^{-i}a_i \sum_{j=1}^{i-1} 2^{j-1}a_j }

权值线段树上维护 \begin{aligned} S_1(l,r) = \sum_{i=l}^{r} 2^{-i}a_i \end{aligned}，\begin{aligned} S_2(l,r) = \sum_{i=l}^{r} 2^{i-1}a_i \end{aligned}，\begin{aligned} S(l,r) = \sum_{i=l}^{r} 2^{-i}a_i \sum_{j=l}^{i-1} 2^{j-1}a_j \end{aligned}，可以轻易地 Push Up。

离散化的方法同 掉进兔子洞，即相同数加上已出现次数，使得每个操作的值对应权值线段树上恰好一个叶子。

复杂度 O((n + q) \log (n+q))。 

#define Geq(a,n,x) lower_bound(a+1,a+n+1,x)-a
using ll = long long;
constexpr int N = 300003, p = 1e9+7;
inline int P(int &x,int y){ return (x+=y)>=p&&(x-=p), x; }
int n, q, a[N], Pw[N], iPw[N], cnt[N<<1], b[N<<1], len;
struct qry { int x, d; } qr[N]; bitset<N<<1> vis;

__attribute__((constructor)) static void
_sntnt_miao_qie_zhe_ge_ti_tai_qiang_le_() {
    Pw[0] = iPw[0] = 1, Pw[1] = 2, iPw[1] = 500000004;
    for(int i=2;i<N;++i) Pw[i] = (Pw[i-1]<<1)%p, iPw[i] = 1ll*iPw[i-1]*iPw[1]%p;
}

struct SegTree {
    int siz[N<<3], S1[N<<3], S2[N<<3], S[N<<3];
    inline void Push(int u){
        int lc = u<<1, rc = u<<1|1, d1 = 1ll*iPw[siz[lc]]*S1[rc]%p, d2 = 1ll*Pw[siz[lc]]*S2[rc]%p;
        P(S1[u] = S1[lc], d1), P(S2[u] = S2[lc], d2), siz[u] = siz[lc] + siz[rc], P(S[u] = S[lc], S[rc]), P(S[u], 1ll*S2[lc]*d1%p);
    }
    inline void Mdf(int u,int l,int r,int x){
        if(l == r) return vis[l] ? (siz[u] = 1, S1[u] = 1ll*iPw[1]*b[l]%p, S2[u] = b[l]) : (siz[u] = S1[u] = S2[u] = 0), void();
        int mid=l+r>>1; x <= mid ? Mdf(u<<1,l,mid,x) : Mdf(u<<1|1,mid+1,r,x); Push(u);
    }
} T;

main(){
    rd(n); for(int i=1;i<=n;++i) rd(a[i]);
    copy(a+1, a+n+1, b+1), rd(q), len = n;
    for(int i=1;i<=q;++i)
        rd(qr[i].x), b[++len] = rd(qr[i].d);
    sort(b+1, b+len+1);
    auto Discrete = [](int &x)->void { int y = Geq(b, len, x); x = y + cnt[y], ++cnt[y]; };
    for(int i=1;i<=n;++i)
        Discrete(a[i]), vis[a[i]] = 1, T.Mdf(1,1,len,a[i]);
    writeln(T.S[1]); //, T.Prt();
    for(int i=1;i<=q;++i)
        Discrete(qr[i].d), vis[a[qr[i].x]] = 0, T.Mdf(1,1,len,a[qr[i].x]),
        vis[(a[qr[i].x] = qr[i].d)] = 1, T.Mdf(1,1,len,a[qr[i].x]), writeln(T.S[1]); //, T.Prt();
}