题解 SP19543 【GSS8 - Can you answer these queries VIII】

2019-08-06 20:31:26


感觉还是有点难度的。

首先这个操作显然用平衡树维护。

注意到 $k$ 很小,考虑每个节点对于每个 $k$ 都维护一个 $ans$ 。

考虑怎么合并两个区间的信息:

$$\begin{aligned}\sum_{i=l}^ra_i(i-l+1)^k&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i(i-l+1)^k\right)\\&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i\big((mid-l+1)-(i-mid)\big)^k\right)\\&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{i=mid+1}^ra_i\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}(i-mid)^{j}\right)\\&=\left(\sum_{i=l}^{mid}a_i(i-l+1)^k\right)+\left(\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}\sum_{i=mid+1}^ra_i(i-mid)^{j}\right)\\&=lans_k+\left(\sum_{j=0}^k{k\choose j}(mid-l+1)^{k-j}rans_j\right)\end{aligned}$$

这样子就很好合并了。

然后因为是平衡树,所以直接把当前节点丢到左区间(或右区间)去,然后就是两个区间合并了。

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
#define int unsigned int

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=200000+10,K=10+10;

int n,Q;
int C[K][K];

inline void init() {
    srand(19260817);
    for (re int i=C[0][0]=1;i<=10;++i)
        for (re int j=C[i][0]=1;j<=i;++j)
            C[i][j]=C[i-1][j]+C[i-1][j-1];
}

// fhq treap
int root,tot=0;
int ch[N][2],sz[N],val[N],rnd[N];
int ans[N][K],pw[K];

inline int newnode(int w) {
    ++tot;
    sz[tot]=1,val[tot]=w,rnd[tot]=rand();
    for (re int i=0;i<=10;++i) ans[tot][i]=w;
    return tot;
}
inline void pushup(int x) {
    int ls=ch[x][0],rs=ch[x][1];
    sz[x]=sz[ls]+sz[rs]+1;
    for (re int i=pw[0]=1;i<=10;++i) pw[i]=pw[i-1]*(sz[ls]+1);
    for (re int k=0;k<=10;++k) {
        ans[x][k]=ans[ls][k]+val[x]*pw[k];
        for (re int i=0;i<=k;++i) ans[x][k]+=C[k][i]*pw[k-i]*ans[rs][i];
    }
}
inline void split(int o,int k,int& x,int& y) {
    if (!o) { x=y=0; return; }
    if (k<=sz[ch[o][0]]) y=o,split(ch[o][0],k,x,ch[o][0]);
    else x=o,split(ch[o][1],k-sz[ch[o][0]]-1,ch[o][1],y);
    pushup(o);
}
inline int merge(int A,int B) {
    if (!A||!B) return A+B;
    if (rnd[A]<rnd[B]) { ch[A][1]=merge(ch[A][1],B),pushup(A); return A; }
    else { ch[B][0]=merge(A,ch[B][0]),pushup(B); return B; }
}

signed main() {
    init();
    n=read();
    for (re int i=1;i<=n;++i) root=merge(root,newnode(read()));
    Q=read();
    while (Q--) {
        char op[2]; scanf("%s",op);
        int o,r,z;
        if (op[0]=='I') {
            int p=read()+1,w=read();
            split(root,p-1,o,r);
            root=merge(merge(o,newnode(w)),r);
        } else if (op[0]=='D') {
            int p=read()+1;
            split(root,p-1,o,r),split(r,1,r,z);
            root=merge(o,z);
        } else if (op[0]=='R') {
            int p=read()+1,w=read();
            split(root,p-1,o,r),split(r,1,r,z);
            val[r]=w,pushup(r);
            root=merge(merge(o,r),z);
        } else {
            int L=read()+1,R=read()+1,k=read();
            split(root,L-1,o,r),split(r,R-L+1,r,z);
            printf("%u\n",ans[r][k]);
            root=merge(merge(o,r),z);
        }
    }
    return 0;
}