二逼平衡树树套树

不用解释了吧……经典板子……
题解也没什么写的……就是一句话：一遍写对省了再debug麻烦。
  1 #include<iostream>
  2 #include<cstdio>
  3 #include<algorithm>
  4 #include<cstring>
  5 #include<cstdlib>
  6 using namespace std;
  7 #define ls(x) (x->ch[0])
  8 #define rs(x) (x->ch[1])
  9 #define size(x) ((x) ? (x->size) : (0))
 10 #define Lson l,mid,id<<1
 11 #define Rson mid+1,r,id<<1|1
 12 const int maxn=50010,inf=1000000000;
 13 struct Node
 14 {
 15     int key,val,size,num;
 16     Node *ch[2];
 17     void Init(int x=0)
 18     {
 19         val=x;size=1;num=1;key=rand();
 20         ch[0]=ch[1]=NULL;
 21     }
 22     bool operator <(const Node &x)const
 23     {
 24         return key<x.key;
 25     }
 26     int Cmp(int x)const
 27     {
 28         if(x==val)return -1;
 29         return x>val;
 30     }
 31     void Maintain()
 32     {
 33         size=num;
 34         if(ch[0])size+=ch[0]->size;
 35         if(ch[1])size+=ch[1]->size;
 36     }
 37 };
 38 Node *root[maxn<<2];
 39 Node node[maxn<<6];
 40 int tot=1,tmp,n,m,a[maxn];
 41 Node* NewNode(int v)
 42 {
 43     node[tot].Init(v);
 44     return &node[tot++];
 45 }
 46 void Rotate(Node* &rt,int d)
 47 {
 48     Node *t=rt->ch[d^1];
 49     rt->ch[d^1]=t->ch[d];t->ch[d]=rt;
 50     rt->Maintain();t->Maintain();
 51     rt=t;
 52 }
 53 void Insert(Node* &rt,int x)
 54 {
 55     if(!rt)rt=NewNode(x);
 56     else
 57     {
 58         int d=rt->Cmp(x);
 59         if(d<0)rt->num++;
 60         else
 61         {
 62             Insert(rt->ch[d],x);
 63             if(rt->ch[d]>rt)Rotate(rt,d^1);
 64         }
 65     }
 66     rt->Maintain();
 67 }
 68 void Build(int l,int r,int id,int x,int num)
 69 {
 70     Insert(root[id],num);
 71     if(l==r)return;
 72     int mid=(l+r)>>1;
 73     if(x<=mid)Build(Lson,x,num);
 74     else Build(Rson,x,num);
 75 }
 76 void Ask_Rank(Node* &rt,int x)
 77 {
 78     if(!rt)return;
 79     if(x==rt->val)
 80     {
 81         tmp+=size(ls(rt));
 82         return;
 83     }
 84     if(rt->val>x)Ask_Rank(ls(rt),x);
 85     else
 86     {
 87         tmp+=size(ls(rt))+rt->num;
 88         Ask_Rank(rs(rt),x);
 89     }
 90 }
 91 void Get_Rank(int l,int r,int id,int x,int y,int num)
 92 {
 93     if(l==x&&r==y)
 94     {
 95         Ask_Rank(root[id],num);
 96         return;
 97     }
 98     int mid=(l+r)>>1;
 99     if(mid>=y)Get_Rank(Lson,x,y,num);
100     else if(mid<x)Get_Rank(Rson,x,y,num);
101     else
102     {
103         Get_Rank(Lson,x,mid,num);
104         Get_Rank(Rson,mid+1,y,num);
105     }
106 }
107 void Get_Index(int x,int y,int k)
108 {
109     int num,l=0,r=inf,mid;
110     while(l<=r)
111     {
112         mid=(l+r)>>1;tmp=1;
113         Get_Rank(1,n,1,x,y,mid);
114         if(tmp<=k)
115         {
116             l=mid+1;
117             num=mid;
118         }
119         else r=mid-1;
120     }
121     printf("%d
",num);
122 }
123 void Delete(Node* &rt,int x)
124 {
125     int d=rt->Cmp(x);
126     if(d<0)
127     {
128         if(rt->num==1)
129         {
130             if(ls(rt)&&rs(rt))
131             {
132                 int d2=ls(rt)>rs(rt);
133                 Rotate(rt,d2);
134                 Delete(rt->ch[d2],x);
135             }
136             else
137             {
138                 Node *t=NULL;
139                 if(ls(rt))t=ls(rt);
140                 else t=rs(rt);
141                 rt=t;
142             }
143         }
144         else rt->num--;
145     }
146     else Delete(rt->ch[d],x);
147     if(rt)rt->Maintain();
148 }
149 void Change(int l,int r,int id,int x,int nxt,int cur)
150 {
151     Delete(root[id],cur);
152     Insert(root[id],nxt);
153     if(l==r)return;
154     int mid=(l+r)>>1;
155     if(x<=mid)Change(Lson,x,nxt,cur);
156     else Change(Rson,x,nxt,cur);
157 }
158 void Ask_Pre(Node* &rt,int x)
159 {
160     if(!rt)return;
161     if(x>rt->val)
162     {
163         tmp=max(tmp,rt->val);
164         Ask_Pre(rs(rt),x);
165     }
166     else Ask_Pre(ls(rt),x);
167 }
168 void Get_Pre(int l,int r,int id,int x,int y,int num)
169 {
170     if(l==x&&r==y)
171     {
172         Ask_Pre(root[id],num);
173         return;
174     }
175     int mid=(l+r)>>1;
176     if(mid>=y)Get_Pre(Lson,x,y,num);
177     else if(mid<x)Get_Pre(Rson,x,y,num);
178     else
179     {
180         Get_Pre(Lson,x,mid,num);
181         Get_Pre(Rson,mid+1,y,num);
182     }
183 }
184 void Ask_Suf(Node* &rt,int x)
185 {
186     if(!rt)return;
187     if(x<rt->val)
188     {
189         tmp=min(tmp,rt->val);
190         Ask_Suf(ls(rt),x);
191     }
192     else Ask_Suf(rs(rt),x);
193 }
194 void Get_Suf(int l,int r,int id,int x,int y,int num)
195 {
196     if(l==x&&r==y)
197     {
198         Ask_Suf(root[id],num);
199         return;
200     }
201     int mid=(l+r)>>1;
202     if(mid>=y)Get_Suf(Lson,x,y,num);
203     else if(mid<x)Get_Suf(Rson,x,y,num);
204     else
205     {
206         Get_Suf(Lson,x,mid,num);
207         Get_Suf(Rson,mid+1,y,num);
208     }
209 }
210 int haha()
211 {
212     freopen("psh.in","r",stdin);
213     freopen("psh.out","w",stdout);
214     int op,l,r,k,pos;
215     scanf("%d%d",&n,&m);
216     for(int i=1;i<=n;i++)scanf("%d",&a[i]);
217     for(int i=1;i<=n;i++)Build(1,n,1,i,a[i]);
218     while(m--)
219     {
220         scanf("%d",&op);
221         switch(op)
222         {
223             case 1:scanf("%d%d%d",&l,&r,&k);tmp=1;
224                     Get_Rank(1,n,1,l,r,k);
225                     printf("%d
",tmp);break;
226             case 2:scanf("%d%d%d",&l,&r,&k);
227                     Get_Index(l,r,k);break;
228             case 3:scanf("%d%d",&pos,&k);
229                     Change(1,n,1,pos,k,a[pos]);
230                     a[pos]=k;break;
231             case 4:scanf("%d%d%d",&l,&r,&k);tmp=0;
232                     Get_Pre(1,n,1,l,r,k);
233                     printf("%d
",tmp);break;
234             case 5:scanf("%d%d%d",&l,&r,&k);tmp=inf;
235                     Get_Suf(1,n,1,l,r,k);
236                     printf("%d
",tmp);break;
237         }
238     }
239     //while(1);
240 }
241 int sb=haha();
242 int main(){;}
View Code
只要是活着的东西，就算是神我也杀给你看。
二逼平衡树 树套树

二逼平衡树树套树
