一、P2042 [NOI2005]维护数列
要求维护一个数列，支持以上几种操作。
此题可以看作平衡树的一个大模板，由于是区间问题，所以用splay或者fhqtreap，我用了fhqtreap（写起来太舒服了）。
数据范围：
你可以认为在任何时刻，数列中至少有 1 个数。
输入数据一定是正确的，即指定位置的数在数列中一定存在。
50%的数据中，任何时刻数列中最多含有 30 000 个数；
100%的数据中，任何时刻数列中最多含有 500 000 个数。
100%的数据中，任何时刻数列中任何一个数字均在[-1 000, 1 000]内。
100%的数据中，M ≤20 000，插入的数字总数不超过 4 000 000 。
1.插入和删除tot个数：因为这题时间卡的很紧，所以不能使用比较方便的那种O(nlogn)方式插入，因为此题是区间，所以插入的数据必是单调插入，所以此处使用笛卡尔树的建树方式，复杂度为O(n)，因为需要用到栈，此处建议手写栈，STL太慢了（STL一生黑QAQ）。这题还得用读入优化，不知是 。删除的话直接将区间提取出来删掉就可以了。但是，此处有个问题，删除的空间需要回收，因为只有128M内存，貌似最多也就开1e6，但是，数据范围告诉了数列中最多有5e5个数字，所以删除的时候就要求空间回收，下次插入的时候要插到这些空间中（再来个栈就完事了，小问题）。
2.修改和反转：像线段树一样就好了，打个标记，然后再访问的时候往下推。
3.求和求最大子序列，维护sum,lmax,rmax,mmax就行了。
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int MAX=5e5+20,INF=0x7fffffff;
4 struct ppp{
5 int val,ch[2],rnd,sum,lmax,rmax,mmax,size;
6 int change,reverse;
7 }treap[MAX];
8 int n,m,tot,root,name[MAX],st[MAX];
9 int read()
10 {
11 int tmp=0,fh=1; char c=getchar();
12 while ((c<'0'||c>'9')&&c!='-') c=getchar();
13 if (c=='-') fh=-1,c=getchar();
14 while (c>='0'&&c<='9') tmp=tmp*10+c-48,c=getchar();
15 return tmp*fh;
16 }
17 inline int NEW(int val)
18 {
19 int p=name[tot--];
20 treap[p]=(ppp){val,0,0,rand(),0,0,0,0,0,0,0};
21 treap[p].val=val;
22 treap[p].rnd=rand();
23 treap[p].sum=val;
24 treap[p].lmax=treap[p].rmax=treap[p].mmax=val;
25 treap[p].size=1;
26 treap[p].change=INF;
27 return p;
28 }
29 inline void reuse(int p)
30 {
31 if(!p) return ;
32 name[++tot]=p;
33 reuse(treap[p].ch[0]);
34 reuse(treap[p].ch[1]);
35 }
36 inline void down(int p)
37 {
38 if(p==0) return;
39 if(treap[p].reverse)
40 {
41 treap[p].reverse=0;
42 swap(treap[p].ch[1],treap[p].ch[0]);
43 treap[treap[p].ch[0]].reverse^=1;
44 treap[treap[p].ch[1]].reverse^=1;
45 swap(treap[p].lmax,treap[p].rmax);
46 }
47 if(treap[p].change!=INF)
48 {
49 int k=treap[p].change;
50 treap[p].change=INF;
51 treap[p].rmax=treap[p].mmax=treap[p].lmax=(k>=0? k*treap[p].size:k);
52 treap[p].sum=treap[p].size*k;
53 treap[p].val=k;
54 treap[treap[p].ch[0]].change=k;
55 treap[treap[p].ch[1]].change=k;
56 }
57 }
58 inline void update(int p)
59 {
60 down(treap[p].ch[0]);
61 down(treap[p].ch[1]);
62 treap[p].sum=treap[p].val+treap[treap[p].ch[0]].sum+treap[treap[p].ch[1]].sum;
63 treap[p].size=treap[treap[p].ch[0]].size+treap[treap[p].ch[1]].size+1;
64 treap[p].lmax=max(treap[treap[p].ch[0]].lmax,treap[treap[p].ch[0]].sum+treap[p].val+max(0,treap[treap[p].ch[1]].lmax));
65 treap[p].rmax=max(treap[treap[p].ch[1]].rmax,treap[treap[p].ch[1]].sum+treap[p].val+max(0,treap[treap[p].ch[0]].rmax));
66 treap[p].mmax=max(max(treap[treap[p].ch[0]].mmax,treap[treap[p].ch[1]].mmax),treap[p].val+max(0,treap[treap[p].ch[0]].rmax)+max(0,treap[treap[p].ch[1]].lmax));
67 }
68
69 inline int build(int k)//笛卡尔树的建树方式 按照权值升序插入 O(n)
70 {
71 int tem_root,top=0;
72 tem_root=read();
73 tem_root=NEW(tem_root);
74 st[++top]=tem_root;
75 for(int i=1;i<k;i++)//k-1 次循环
76 {
77 int val;
78 val=read();
79 int p=NEW(val),last=0;
80 while(top and treap[st[top]].rnd>treap[p].rnd)//小根堆
81 {
82 treap[p].ch[0]=st[top];
83 update(st[top]);
84 top--;
85 }
86 if(top)
87 treap[st[top]].ch[1]=p;
88 else
89 tem_root=p;
90 st[++top]=p;
91 update(p);
92 }
93 while(top)
94 {
95 update(st[top]);
96 top--;
97 }
98 return tem_root;
99 }
100 inline void split(int now,int &x,int &y,int rank)
101 {
102 down(now);
103 if(rank>=treap[now].size)
104 {
105 x=now,y=0;
106 return ;
107 }
108 if(rank<=0)
109 {
110 y=now,x=0;
111 return ;
112 }
113 if(rank<=treap[treap[now].ch[0]].size)
114 {
115 y=now;
116 split(treap[now].ch[0],x,treap[now].ch[0],rank);
117 }
118 else
119 {
120 x=now;
121 split(treap[now].ch[1],treap[now].ch[1],y,rank-treap[treap[now].ch[0]].size-1);
122 }
123 update(now);
124 }
125 inline int merge(int x,int y)
126 {
127 down(x);down(y);
128 if(x==0 or y==0)
129 return x+y;
130 if(treap[x].rnd<treap[y].rnd)
131 {
132 treap[x].ch[1]=merge(treap[x].ch[1],y);
133 update(x);
134 update(treap[x].ch[1]);
135 return x;
136 }
137 else
138 {
139 treap[y].ch[0]=merge(x,treap[y].ch[0]);
140 update(y);
141 update(treap[y].ch[0]);
142 return y;
143 }
144 }
145 inline void remove(int pos,int num)
146 {
147 int x=0,y=0,z=0;
148 split(root,x,y,pos-1);
149 split(y,y,z,num);
150 reuse(y);
151 root=merge(x,z);
152 }
153 inline void insert(int pos,int num)
154 {
155 int x,y,z;
156 split(root,x,y,pos);
157 z=build(num);
158 root=merge(merge(x,z),y);
159 }
160 inline void make_same(int pos,int num,int c)
161 {
162 int x=0,y=0,z=0;
163 split(root,x,y,pos-1);
164 split(y,y,z,num);
165 treap[y].change=c;
166 y=merge(y,z);
167 root=merge(x,y);
168 }
169 inline void reverse(int pos,int num)
170 {
171 int x=0,y=0,z=0;
172 split(root,x,y,pos-1);
173 split(y,y,z,num);
174 treap[y].reverse^=1;
175 y=merge(y,z);
176 root=merge(x,y);
177 }
178 inline void getsum(int pos,int sum)
179 {
180 int x=0,y=0,z=0;
181 split(root,x,y,pos-1);
182 split(y,y,z,sum);
183 printf("%d\n",treap[y].sum);
184 y=merge(y,z);
185 root=merge(x,y);
186 }
187 inline void maxsum()
188 {
189 printf("%d\n",treap[root].mmax);
190 }
191 int main()
192 {
193 //scanf("%d%d",&n,&m);
194 n=read();m=read();
195 for (int i=500010;i;i--) name[++tot]=i;
196 treap[0].lmax=treap[0].rmax=treap[0].mmax=-INF;
197 root=build(n);
198 char opt[15];
199 for(int i=1;i<=m;i++)
200 {
201 char c=getchar();
202 while(c<'A' or c>'Z') c=getchar();
203 opt[0]=c;opt[1]=getchar();opt[2]=getchar();
204 while((c>='A' and c<='Z') or c=='-') c=getchar();
205 if(opt[0]=='I')
206 {
207 int k=read(),jkl=read();
208 //scanf("%d%d",&k,&jkl);
209 insert(k,jkl);
210 }
211 else if(opt[0]=='D')
212 {
213 int O=read(),P=read();
214 //scanf("%d%d",&O,&P);
215 remove(O,P);
216 }
217 else if(opt[2]=='K')
218 {
219 int O=read(),P=read(),C=read();
220 //scanf("%d%d%d",&O,&P,&C);
221 make_same(O,P,C);
222 }
223 else if(opt[0]=='R')
224 {
225 int O=read(),P=read();
226 //scanf("%d%d",&O,&P);
227 reverse(O,P);
228 }
229 else if(opt[0]=='G')
230 {
231 int O=read(),P=read();
232 //scanf("%d%d",&O,&P);
233 getsum(O,P);
234 }
235 else
236 maxsum();
237 }
238 return 0;
239 }
View Code
二、P2596 [ZJOI2006]书架
这题最大的问题就是要根据区间的内的编号来找到点的排名，记录父节点即可，记录每个值所在点的编号，然后递归求rank即可
1 #include<bits/stdc++.h>
2 using namespace std;
3 const int MAX=8e4+30,INF=0x7fffffff;
4 struct ppp{
5 int val,ch[2],size,rand,fa;
6 }treap[MAX];
7 int n,m,tot,root,st[MAX],top,pic[MAX];
8 inline int NEW(int val)
9 {
10 tot++;
11 treap[tot].val=val;
12 treap[tot].size=1;
13 treap[tot].rand=rand();
14 return tot;
15 }
16 inline void update(int p)
17 {
18 treap[p].size=treap[treap[p].ch[0]].size+treap[treap[p].ch[1]].size+1;
19 if(treap[p].ch[0]!=0)
20 treap[treap[p].ch[0]].fa=p;
21 if(treap[p].ch[1]!=0)
22 treap[treap[p].ch[1]].fa=p;
23 }
24 inline void split(int now,int &x,int &y,int rank)
25 {
26 if(rank<=0)
27 {
28 y=now,x=0;
29 return ;
30 }
31 if(rank>=treap[now].size)
32 {
33 x=now,y=0;
34 return ;
35 }
36 if(treap[treap[now].ch[0]].size>=rank)
37 {
38 y=now;
39 split(treap[now].ch[0],x,treap[now].ch[0],rank);
40 }
41 else
42 {
43 x=now;
44 split(treap[now].ch[1],treap[now].ch[1],y,rank-treap[treap[now].ch[0]].size-1);
45 }
46 update(now);
47 }
48 inline int merge(int x,int y)
49 {
50 if(x==0 or y==0)
51 return x+y;
52 if(treap[x].rand<treap[y].rand)
53 {
54 treap[x].ch[1]=merge(treap[x].ch[1],y);
55 update(x);
56 return x;
57 }
58 else
59 {
60 treap[y].ch[0]=merge(x,treap[y].ch[0]);
61 update(y);
62 return y;
63 }
64 }
65 inline int build(int k)
66 {
67 int tem_root;
68 scanf("%d",&tem_root);
69 tem_root=NEW(tem_root);
70 pic[treap[tem_root].val]=tem_root;
71 st[++top]=tem_root;
72 for(int i=1;i<k;i++)
73 {
74 int val;
75 scanf("%d",&val);
76 int p=NEW(val);
77 pic[val]=p;
78 int last=0;
79 while(top and treap[st[top]].rand>treap[p].rand)
80 {
81 //treap[p].ch[0]=st[top];
82 last=st[top];
83 update(st[top]);
84 top--;
85 }
86 treap[p].ch[0]=last;
87 if(top)
88 treap[st[top]].ch[1]=p;
89 else
90 tem_root=p;
91 st[++top]=p;
92 update(p);
93 }
94 while(top)
95 {
96 update(st[top]);
97 top--;
98 }
99 return tem_root;
100 }
101 inline int find(int p)
102 {
103 int fa=treap[p].fa;
104 if(fa==0 or p==0) return 0;
105 int son=treap[fa].ch[1]==p;
106 if(son) return treap[treap[fa].ch[0]].size+1+find(fa);
107 else return find(fa);
108 }
109 inline int getrank(int p)
110 {
111 return find(p)+treap[treap[p].ch[0]].size+1;
112 }
113 int main()
114 {
115 scanf("%d%d",&n,&m);
116 root=build(n);
117 for(int i=1;i<=m;i++)
118 {
119 char s[10];
120 int val;
121 scanf("%s %d",s,&val);
122 if(s[0]=='T')
123 {
124 int p=pic[val];
125 int rank=getrank(p);
126 int x,y,z;
127 split(root,x,y,rank-1);
128 split(y,z,y,1);
129 root=merge(merge(z,x),y);
130 }
131 else if(s[0]=='B')
132 {
133 int p=pic[val];
134 int rank=getrank(p);
135 int x,y,z;
136 split(root,x,y,rank-1);
137 split(y,z,y,1);
138 root=merge(merge(x,y),z);
139 }
140 else if(s[0]=='I')
141 {
142 int t;
143 scanf("%d",&t);
144 if(t==0) continue;
145 if(t==1) t=0;
146
147 int p=pic[val];
148 int rank=getrank(p);
149 int x,y,z,q;
150 split(root,x,y,rank-1+t);
151 split(y,z,y,1);
152 split(y,q,y,1);
153 root=merge(merge(x,q),merge(z,y));
154 }
155 else if(s[0]=='A')
156 {
157 int p=pic[val];
158 int rank=getrank(p);
159 printf("%d\n",rank-1);
160 }
161 else if(s[0]=='Q')
162 {
163 int x,y,z;
164 split(root,x,y,val-1);
165 split(y,z,y,1);
166 printf("%d\n",treap[z].val);
167 root=merge(merge(x,z),y);
168 }
169 }
170 return 0;
171 }
View Code
三、P3285 [SCOI2014]方伯伯的OJ
无力吐槽，此题动态开点。。。debug了一整天，代码漏洞颇多。。。。QAQ 1 #include<bits/stdc++.h>
2 using namespace std;
3 const int MAX=3e5+100,INF=0x7fffffff;
4 struct ppp{
5 int ch[2],rnd,size,l,r,fa;
6 }treap[MAX];
7 map<int,int> f;
8 int n,m,a,tot,root,lnow=INF,cnt=0;
9 void update(int p)
10 {
11 treap[p].size=treap[treap[p].ch[0]].size+treap[treap[p].ch[1]].size+treap[p].r-treap[p].l+1;
12 treap[treap[p].ch[0]].fa=treap[treap[p].ch[1]].fa=p;
13 treap[0]=(ppp){0,0,0,0,0,0,0};
14 }
15 int divide(int now,int k)//now保留前k个
16 {
17 if(k==treap[now].r-treap[now].l+1) return 0;
18 if(k==0) return now;
19 tot++;
20 treap[tot]=(ppp){0,0,rand(),0,treap[now].l+k,treap[now].r,0};
21
22 f[treap[now].r]=tot;
23 f[treap[now].l+k-1]=now;
24
25 treap[now].r=treap[now].l+k-1;
26 treap[tot].ch[1]=treap[now].ch[1];
27 if(treap[now].rnd<treap[tot].rnd)//tot防在右下角
28 {
29 treap[now].ch[1]=tot;
30 update(tot);
31 update(now);
32 }
33 else
34 {
35 treap[now].ch[1]=0;
36 treap[tot].ch[0]=now;
37 treap[tot].fa=treap[now].fa;
38 treap[treap[now].fa].ch[treap[treap[now].fa].ch[1]==now?1:0]=tot;
39 update(now);
40 update(tot);
41 update(treap[tot].fa);
42 }
43 if(treap[tot].fa==0) root=tot;
44 return tot;
45 }
46 int merge(int x,int y)
47 {
48 if(x==0 or y==0)
49 return x+y;
50 if(treap[x].rnd>treap[y].rnd)
51 {
52 treap[y].ch[0]=merge(x,treap[y].ch[0]);
53 update(y);
54 return y;
55 }
56 else
57 {
58 treap[x].ch[1]=merge(treap[x].ch[1],y);
59 update(x);
60 return x;
61 }
62 }
63 void split(int now,int &x,int &y,int rank)
64 {
65 if(rank==0)
66 {
67 treap[now].fa=treap[y].fa;
68 x=0,y=now;
69 return ;
70 }
71 if(rank>=treap[now].size)
72 {
73 treap[now].fa=treap[x].fa;
74 x=now,y=0;
75 return ;
76 }
77 if(treap[treap[now].ch[0]].size>=rank)
78 {
79 treap[now].fa=treap[y].fa;
80 y=now;
81 split(treap[now].ch[0],x,treap[now].ch[0],rank);
82 update(now);
83 }
84 else if(treap[treap[now].ch[0]].size+treap[now].r-treap[now].l+1<=rank)
85 {
86 treap[now].fa=treap[x].fa;
87 x=now;
88 split(treap[now].ch[1],treap[now].ch[1],y,rank-(treap[treap[now].ch[0]].size+treap[now].r-treap[now].l+1));
89 update(now);
90 }
91 else
92 {
93 int ori_fa=treap[now].fa;
94 int k=divide(now,rank-treap[treap[now].ch[0]].size-1);
95 int q=divide(k,1);
96 while(treap[now].fa!=ori_fa)
97 now=treap[now].fa;
98 split(now,x,y,rank);
99 }
100 }
101 void init()
102 {
103 root=++tot;
104 treap[root]=(ppp){0,0,rand(),n,1,n,0};
105 f[n]=root;
106 }
107 int find(int p)
108 {
109 int fa=treap[p].fa;
110 if(fa==0 or p==0 or p==fa) return 0;
111 int son=treap[fa].ch[1]==p;
112 if(son) return treap[treap[fa].ch[0]].size+treap[fa].r-treap[fa].l+1+find(fa);
113 else return find(fa);
114 }
115 int getrank(int x)
116 {
117 map<int,int>::iterator it=f.lower_bound(x);
118 int p=it->second;
119 return find(p)+treap[treap[p].ch[0]].size+x-treap[p].l+1;
120 }
121 int main()
122 {
123 scanf("%d%d",&n,&m);
124 init();
125 for(int i=1;i<=m;i++)
126 {
127 int opt,x1,y1;
128 scanf("%d%d",&opt,&x1);
129 x1-=a;
130 if(opt==1)
131 {
132 scanf("%d",&y1);
133 y1-=a;
134 int rank=getrank(x1);
135 printf("%d\n",rank);
136 a=rank;
137 int x=0,y=0,z=0;
138 split(root,x,y,rank-1);
139 split(y,z,y,1);
140 treap[z].l=treap[z].r=y1;
141 f[y1]=z;
142 f.erase(x1);
143 root=merge(merge(x,z),y);
144 }
145 else if(opt==2)
146 {
147 int rank=getrank(x1);
148 printf("%d\n",rank);
149 a=rank;
150 int x=0,y=0,z=0;
151 split(root,x,y,rank-1);
152 split(y,z,y,1);
153 root=merge(merge(z,x),y);
154 }
155 else if(opt==3)
156 {
157 int rank=getrank(x1);
158 printf("%d\n",rank);
159 a=rank;
160 int x=0,y=0,z=0;
161 split(root,x,y,rank-1);
162 split(y,z,y,1);
163 root=merge(merge(x,y),z);
164 }
165 else if(opt==4)
166 {
167 int x=0,y=0,z=0;
168 split(root,x,y,x1-1);
169 split(y,z,y,1);
170 a=treap[z].l;
171 printf("%d\n",a);
172 root=merge(merge(x,z),y);
173 }
174 }
175 return 0;
176 }
View Code