抱歉，您的浏览器无法访问本站
本页面需要浏览器支持（启用）JavaScript
了解详情 >

SP19543 GSS8 - Can you answer these queries VIII

发布于：2019年7月27日

传送门

洛谷上面翻译有毒，一是没有数据范围，其实n≤200000n \le 200000，二是没有样例，这里粘贴一组SPOJ\rm SPOJ样例，和自己的对拍数据。

SPOJ\rm SPOJ样例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
input:
4
1 2 3 5
7
Q 0 2 0
I 3 4
Q 2 4 1
D 0
Q 0 3 1
R 1 2
Q 0 1 0
output:
6
26
40
4

我的对拍数据

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
input
20
1574452022 549188900 68567242 1729321800 30592296 1234967064 1540591694 1298547924 1791505596 347980114 142536772 369008392 492229442 883499152 569859698 1891123126 1765828398 540013562 1182847552 1727333276 
20
R 0 378520004
I 0 1564716480
D 1
R 0 1349444400
R 0 1758121648
I 0 1716182608
Q 1 1 1
R 1 2068268798
I 1 727687312
I 2 1307033320
Q 1 2 1
I 3 54907522
Q 1 3 7
R 3 1157040456
I 1 379786942
Q 2 3 1
I 1 1497285546
D 4
Q 3 4 2
D 4
output:
1758121648
3341753952
347894054
3341753952
1060881840

附送数据生成器（注意生成器要记录一个curcur代表当前数组的长度，否则删除操作容易搞错）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include <bits/stdc++.h>
#define ui unsigned int
using namespace std;
inline int read(){
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x*10)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}

const char op[4]={'I','D','R','Q'};
inline ui Randui(){
    return (((rand()<<(ui)15)|(rand()))<<1)|(rand()%2);
}
int cur;
int main(){
    srand(time(NULL));
    freopen("gss8.in","w",stdout);
    int n=20;
    printf("%d\n",n);
    for (register int i=1;i<=n;++i){
        printf("%u ",Randui());
    }
    printf("\n");
    int q=20;
    printf("%d\n",q);
    for (register int i=1;i<=q;++i){
        int opr=rand()%4;
        while (cur==0&&opr==1) opr=rand()%4;
        putchar(op[opr]);
        putchar(' ');
        if (opr==0){
            printf("%d %u\n",cur==0?0:rand()%cur+1,Randui());
            cur++;
        }
        else if (opr==1){
            printf("%d\n",cur==0?0:rand()%cur+1);
            cur--;
        }
        else if (opr==2){
            printf("%d %u\n",cur==0?0:rand()%cur+1,Randui());
        }
        else {
            int l=(cur==0?0:rand()%cur+1);
            int r=(cur==0?0:rand()%cur+1);
            if (l>r) swap(l,r);
            printf("%d %d %d\n",l,r,rand()%11);
        }
    }
}

好了步入正题。

第一步，看见插入和删除操作，立马要条件反射地想到平衡树，这里使用FHQTreap\rm FHQ Treap实现。

第二步，发现I,D,R\rm I,D,R操作都比较好实现，唯独Q\rm Q比较烦人，又发现0≤k≤100 \le k \le 10，就有了思路。

考虑在每个节点上维护一个数组ansans，其中ans[k]=∑i=lrA[i]×(i−l+1)kans[k]=\sum_{i=l}^r A[i] \times (i-l+1)^k

考虑如何维护ansans

我们推一推式子：

设整个区间左右端点为[l,r][l,r]，中间的根节点为mm，也就是说，根节点代表[m,m][m,m]，左子树代表[l,m−1][l,m-1]，右子树代表[m+1,r][m+1,r]，对于所有的kk，我们要知道所有的∑i=lrA[i]×(i−l+1)k\sum _{i=l}^r{A[i] \times (i-l+1)^k}

大力拆式子，首先，对于前面的部分∑i=lm−1A[i]×(i−l+1)k\sum_{i=l}^{m-1}A[i] \times (i-l+1)^k，它其实就是左子树代表的和，直接相加。

（程序里的ii其实是上面的kk）

1
tree[x].ans[i]=tree[lc(x)].ans[i];//左半部分

接下来的过程中，我们设s=m−l+1s=m-l+1

别忘了中间还要一个根节点，就是A[m]×(m−l+1)kA[m] \times (m-l+1)^k，即A[m]×skA[m] \times s^k

1
tree[x].ans[i]+=tree[x].val*(ui)Pow[s][i];//中间

最后烦人的是右子树，发现剩下还没消掉的和还有∑i=m+1rA[i]×(i−l+1)k\sum _{i=m+1}^r A[i] \times (i-l+1)^k，

我们慢慢来，先拆成这个样子：∑i=m+1rA[i]×((m−l+1)+(i−m))k\sum _{i=m+1}^r A[i] \times ((m-l+1)+(i-m))^k

于是右边的式子可以用二项式定理展开：

考虑把那个A[i]A[i]提到里面去，则有：

注意到A[i]A[i](i−m)k−j(i-m)^{k-j}其实就是右子树代表的和，所以直接相乘即可。

1
2
3
for (register int j=0;j<=i;++j){//右半部分
     tree[x].ans[i]+=tree[rc(x)].ans[j]*Pow[s][i-j]*C[i][j];
}

注意题目要mod  232\mod 2^{32}，我们采用unsigned int\text {unsigned int}自然溢出来取模。

输出unsigned int\text {unsigned int}我们使用\text{printf("%u")}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
#include <bits/stdc++.h>
#define MAXN 200005
#define MAXK 12
#define ui unsigned int //因为题目%2^32所以可以用unsigned int自动取模
using namespace std;
inline int readi() {
    int x=0,f=1;
    char ch=getchar();
    while (ch<'0'||ch>'9') {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0'&&ch<='9') {
        x=(x*10)+(ch-'0');
        ch=getchar();
    }
    return x*f;
}
inline ui readu(){
    ui x=0;
    char ch=getchar();
    while (ch<'0'||ch>'9'){
        ch=getchar();
    }
    while (ch>='0'&&ch<='9'){
        x=(x*(ui)(10))+(ui)(ch-'0');
        ch=getchar();
    }
    return x;
}
ui C[MAXK][MAXK],Pow[MAXN][MAXK];
//pow[i][j] i^j
inline void Init(){
    for (register int i=0;i<MAXK;++i){
        C[i][0]=C[i][i]=1;
        for (register int j=1;j<i;++j){
            C[i][j]=C[i-1][j]+C[i-1][j-1];
        }
    }
    for (register int i=1;i<MAXN;++i){
        Pow[i][0]=1;
        for (register int j=1;j<MAXK;++j){
            Pow[i][j]=Pow[i][j-1]*i;
        }
    }
}
namespace FHQ_Treap{
    struct node{
        int l,r;
        int pri;
        int sz;
        ui val;
        ui ans[MAXK];//ans[i]表示sigma l<=i<=r A[i]*(i-l+1)^k
    }tree[MAXN];
    int tot;
    #define lc(i) tree[i].l
    #define rc(i) tree[i].r
    //注意fhq treap和线段树不同：根节点不会算
    inline void Update(int x){
        tree[x].sz=tree[lc(x)].sz+tree[rc(x)].sz+1;
        const int s=tree[lc(x)].sz+1;
        for (register int i=0;i<MAXK;++i){
            tree[x].ans[i]=tree[lc(x)].ans[i];//左半部分
            tree[x].ans[i]+=tree[x].val*(ui)Pow[s][i];//中间
            for (register int j=0;j<=i;++j){//右半部分
                tree[x].ans[i]+=tree[rc(x)].ans[j]*(ui)Pow[s][i-j]*(ui)C[i][j];
            }
        }
    }
    inline int New(ui v){
        tree[++tot].val=v;
        tree[tot].pri=rand();
        tree[tot].sz=1;
        for (register int i=0;i<MAXK;++i){
            tree[tot].ans[i]=v;
        }
        return tot;
    }
    int Merge(int x,int y){
        if (!x||!y) return x+y;
        if (tree[x].pri<tree[y].pri){
            rc(x)=Merge(rc(x),y),Update(x);
            return x;
        }
        else {
            lc(y)=Merge(x,lc(y)),Update(y);
            return y;
        }
    }
    void Split(int i,int k,int &x,int &y){
        if (!i) {
            x=y=0;
        }
        else {
            if (tree[lc(i)].sz>=k) {y=i,Split(lc(i),k,x,lc(i));}//在左子树
            else {x=i,Split(rc(i),k-tree[lc(i)].sz-1,rc(i),y);}//在右子树
            Update(i);
        }
    }
    //以上为FHQ Treap
    int root,x,y,z;
    inline void Add(int pos,ui num){//在pos插入num
        Split(root,pos,x,y);
        root=Merge(Merge(x,New(num)),y);
    }
    inline void Del(int pos){//删除pos处元素
        Split(root,pos,x,y);
        Split(y,1,y,z);
        root=Merge(x,z);
    }
};
using namespace FHQ_Treap;
inline char gc(){
    char ch=getchar();
    while (ch!='I'&&ch!='D'&&ch!='R'&&ch!='Q') ch=getchar();
    return ch;
}
signed main(){
    Init();
    srand(time(NULL));
    int n=readi();
    for (register int i=1;i<=n;++i){
        root=Merge(root,New(readu()));
    }
    int q=readi();
    while (q--){
        char opr=gc();
        if (opr=='I'){
            int pos=readi();
            ui val=readu();
            Add(pos,val);
        }
        else if (opr=='D'){
            int pos=readi();
            Del(pos);
        }
        else if (opr=='R'){
            int pos=readi();ui val=readu();
            Del(pos),Add(pos,val);
        }
        else {
            int l=readi(),r=readi(),k=readi();
            Split(root,r+1,x,z);
            Split(x,l,x,y);
            printf("%u\n",tree[y].ans[k]);
            root=Merge(Merge(x,y),z);
        }
    }
}

然后你就把GSS\text{GSS}系列最难的一道题切掉了。

相关文章
P1486 [NOI2004]郁闷的出纳员 FHQ TreapP2234 [HNOI2002]营业额统计 平衡树P2286 [HNOI2004]宠物收养场 平衡树P3380 【模板】二逼平衡树（树套树）基本概念

博客内容遵循 署名-非商业性使用-相同方式共享 4.0 国际 (CC BY-NC-SA 4.0) 协议

本文永久链接是：https://gaisaiyuno.github.io/archives/3ef91b62.html

更新于：2022年6月14日

题解

毒瘤

平衡树

FHQ Treap

评论