平衡树有关题目小结

一、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

四、。。。咕了

 
上一篇:概率论与数理统计教程 第三版 茆诗松 读书笔记5


下一篇:数字信号处理实验(二) —— 利用FFT实现快速卷积