#106. 二逼平衡树（附带详细代码注释）

attack

发布于 2018-04-12 11:23:10

9110

发布于 2018-04-12 11:23:10

文章被收录于专栏：数据结构与算法数据结构与算法数据结构与算法

内存限制：512 MiB时间限制：4000 ms标准输入输出

题目类型：传统评测方式：文本比较

上传者：匿名

提交提交记录统计讨论测试数据

题目描述

这是一道模板题。

您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：

查询 x xx 在区间内的排名；
查询区间内排名为 k kk 的值；
修改某一位置上的数值；
查询 x xx 在区间内的前趋（前趋定义为小于 x xx，且最大的数）；
查询 x xx 在区间内的后继（后继定义为大于 x xx，且最小的数）。

输入格式

第一行两个数 n,m n, mn,m，表示长度为 n nn 的有序序列和 m mm 个操作。第二行有 n nn 个数，表示有序序列。

下面有 m mm 行，每行第一个数表示操作类型：

之后有三个数 l,r,x l, r, xl,r,x 表示查询 x xx 在区间 [l,r] [l, r][l,r] 的排名；
之后有三个数 l,r,k l, r, kl,r,k 表示查询区间 [l,r] [l, r][l,r] 内排名为 k kk 的数；
之后有两个数 pos,x \mathrm{pos}, xpos,x 表示将 pos \mathrm{pos}pos 位置的数修改为 x xx；
之后有三个数 l,r,x l, r, xl,r,x 表示查询区间 [l,r] [l, r][l,r] 内 x xx 的前趋；
之后有三个数 l,r,x l, r, xl,r,x 表示查询区间 [l,r] [l, r][l,r] 内 x xx 的后继。

输出格式

对于操作 1,2,4,5 1, 2, 4, 51,2,4,5 各输出一行，表示查询结果。

样例

样例输入

9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5

样例输出

数据范围与提示

1≤n,m≤5×104,−108≤k,x≤108 1 \leq n, m \leq 5 \times 10 ^ 4, -10 ^ 8 \leq k, x \leq 10 ^ 81≤n,m≤5×104,−108≤k,x≤108

显示分类标签

树套树，我写的是线段树套splay

当然也可以树状数组套主席树。

据说还可以用分块搞。。。。。。。。

代码里有详细的注释，

看不懂的可以发评论

  1 #include<iostream>
  2 #include<cstring>
  3 #include<cstdio>
  4 #include<algorithm>
  5 #define ls k<<1
  6 #define rs k<<1|1
  7 using namespace std;
  8 const int MAXN=2000001;
  9 inline void read(int &n)
 10 {    char c='+';int x=0;bool flag=0;while(c<'0'||c>'9'){c=getchar();if(c=='-')flag=1;}    
 11     while(c>='0'&&c<='9'){x=x*10+(c-48);c=getchar();}    n=flag==1?-x:x;    }
 12 struct node
 13 {
 14     int l,r,root,mx,mn;
 15 }tree[MAXN];
 16 struct sp
 17 {
 18     int size;// 子节点的数目 
 19     int ch[2];// 孩子 
 20     int fa;// 父节点 
 21     int cnt;// 出现的次数 
 22     int num;// 节点的值 
 23 }s[MAXN];
 24 int sz=0;
 25 inline void pushup(int k)//上传splay标记 
 26 {    s[k].size=s[s[k].ch[0]].size+s[s[k].ch[1]].size+s[k].cnt;    }
 27 inline void pushup_s(int k)// 上传线段树的标记 
 28 {    tree[k].mx=max(tree[ls].mx,tree[rs].mx);    tree[k].mn=min(tree[ls].mn,tree[rs].mn);}
 29 inline int son(int x)// 判断x是父亲的哪个儿子 
 30 {    return s[s[x].fa].ch[1]==x;}
 31 inline int connect(int x,int f,bool how)
 32 {    s[x].fa=f;    s[f].ch[how]=x;}
 33 inline void rotate(int &root,int x)// 对x进行双旋操作 
 34 {
 35     int f=s[x].fa; bool d=son(x);
 36     if(f==root)    root=x,s[x].fa=0;
 37     else connect(x,s[f].fa,son(f));
 38     connect(s[x].ch[!d],f,d);connect(f,x,!d);
 39     pushup(f);pushup(x);
 40 }
 41 inline void splay(int &root,int x,int i)// 把x伸展到i号节点 
 42 {
 43     for(int f;(f=s[x].fa)!=i;)
 44     {
 45         if(s[f].fa==i){rotate(root,x);break;}
 46         rotate(root,(son(x)==son(f))?f:x );
 47         rotate(root,x);
 48     }
 49 }
 50 inline void insert(int &k,int c)// k节点，插入值为c的元素
 51 { 
 52     if(k==0)// 如果是该节点是根节点，或者没有被访问过 
 53     {
 54         k=++sz;/* 新开一个节点*/     s[k].size=s[k].cnt=1;
 55         s[k].num=c;    return ;// 给新开节点赋初值 
 56     }
 57     if(s[k].num==c)    s[k].cnt++;// 找到值和要插入的值相同的节点，直接把出现次数++ 
 58     else if(s[k].num<c)//如果当前节点的值比要插入的节点的值小 
 59         insert(s[k].ch[1],c),// 那就往右孩子插 
 60         s[s[k].ch[1]].fa=k;//　同时更改右孩子的父亲 
 61     else
 62         insert(s[k].ch[0],c),
 63         s[s[k].ch[0]].fa=k;// 往左孩子插，同时更改左孩子的父亲 
 64     pushup(k);// 在进行本次操作的时候会引起cnt的改变，不要忘了上传标记！ 
 65 }
 66 inline void buildseg(int k,int l,int r)//下标为k，左端点为l，右端点为r 
 67 {
 68     tree[k].l=l;tree[k].r=r;
 69     if(l==r)    return ;
 70     int mid=(l+r)>>1;
 71     buildseg(ls,l,mid);
 72     buildseg(rs,mid+1,r);// 线段树模板，没啥好说的， 
 73 }
 74 inline int getpre(int k,int val)//小于val的最大值 
 75 {
 76     int pos=k,ret;
 77     while(pos)
 78         if(s[pos].num>=val)    pos=s[pos].ch[0];//如果当前的值大于val，那么要找的值一定在左孩子 
 79         else    ret=pos,    pos=s[pos].ch[1];// 反之去右孩子找 
 80     return ret;// 这样找到的一定是在整棵平衡树中，小于val的最大值 
 81 }
 82 inline int getsuc(int k,int val)//找大于val的最小值 
 83 {
 84     int pos=k,ret;
 85     while(pos)
 86         if(s[pos].num<=val)    pos=s[pos].ch[1];
 87         else    ret=pos,    pos=s[pos].ch[0];
 88     return ret;//正好与上面的相反。找大于val的最小值 
 89 }
 90 inline int getk(int k,int val)//在编号为k的splay中找值为val的编号 
 91 {
 92     if(s[k].num==val)    return k;
 93     if(s[k].num<val)    return getk(s[k].ch[1],val);
 94     if(s[k].num>val)    return getk(s[k].ch[0],val);
 95 }
 96 inline void build(int k,int pos,int x)// 在下标为k，位置为pos的地方插入一个值为x的元素 
 97 {
 98     insert(tree[k].root,x);//在线段树root节点的splay中插入一个值为x的元素 
 99     if(tree[k].l==tree[k].r)
100     {    tree[k].mx=x;    tree[k].mn=x;/* 到达叶子节点*/     return ;/* 别忘了返回！ */    }
101     int mid=(tree[k].l+tree[k].r)>>1;
102     if(pos<=mid)    build(ls,pos,x);
103     if(pos>mid)        build(rs,pos,x);
104     pushup_s(k);//别忘了上传线段树标记 
105 }
106 inline void dfsseg(int k)//对以k下标开始的线段树进行遍历
107 {
108     int x=getsuc(tree[k].root,-1),y=getpre(tree[k].root,1e8+1);//这样计算出来的x和y一定满足：x是k号线段树中的最小值的位置，y是k号线段树中最大值的位置 
109     splay(tree[k].root,x,0);//将x旋转到根 
110     s[x].size++;s[x].ch[0]=++sz;s[sz].fa=x;s[sz].size=s[sz].cnt=1;s[sz].num=-1;
111     splay(tree[k].root,y,0);
112     s[y].size++;s[y].ch[1]=++sz;s[sz].fa=y;s[sz].size=s[sz].cnt=1;s[sz].num=1e8+1;
113     if(tree[k].l==tree[k].r)    return ;
114     dfsseg(ls);    dfsseg(rs);// 对于每一个线段，增加两个虚节点 
115 }
116 inline int getmax(int k,int l,int r)//在l到r中找最大的元素 
117 {
118     if(l<=tree[k].l&&tree[k].r<=r)    return tree[k].mx;
119     int mid=(tree[k].l+tree[k].r)>>1,ret=-1;
120     if(l<=mid)    ret=max(ret,getmax(ls,l,r));
121     if(mid<r)    ret=max(ret,getmax(rs,l,r));
122     return ret;
123 }
124 inline int getmin(int k,int l,int r)//在l到r中找最小的元素 
125 {
126     if(l<=tree[k].l&&tree[k].r<=r)    return tree[k].mn;
127     int mid=(tree[k].l+tree[k].r)>>1,ret=1e8+1;
128     if(l<=mid)    ret=min(ret,getmin(ls,l,r));
129     if(mid<r)    ret=min(ret,getmin(rs,l,r));
130     return ret;
131 }
132 inline int query_order(int k,int l,int r,int val)//下标为k，查询val在区间l到r中有多少比它小的数 -----------
133 {
134     if(l<=tree[k].l&&tree[k].r<=r)
135     {
136         int p=getpre(tree[k].root,val);// 找到小于它的值中最大值所对应的节点编号 
137         splay(tree[k].root,p,0);// 把他旋转到根节点 
138         return s[p].size-s[s[p].ch[1]].size-1;//注意这里不能直接返回左孩子的大小！！！！---------------------- 
139     }
140     int mid=(tree[k].l+tree[k].r)>>1,ret=0;
141     if(l<=mid)    ret+=query_order(ls,l,r,val);
142     if(r>mid)    ret+=query_order(rs,l,r,val);
143     return ret;
144 }
145 inline void delet(int &k,int val)//删除值为val的节点 
146 {
147     int x=getk(k,val);//得到值为val的编号 
148     if(s[x].cnt>1)// 如果有不止一个节点 
149         splay(k,x,0),    s[x].cnt--,    s[x].size--;
150     else
151     {
152         int p=getpre(k,val),su=getsuc(k,val);// 找到前驱和后继 
153         splay(k,p,0);splay(k,su,p);// 把前驱旋转到根节点，把后继旋转到根节点的孩子 
154         s[su].ch[0]=0;// 删除后继的左孩子，表示没有小于他的点，这样就成功把x节点删除 
155     }
156 }
157 inline void modify(int k,int pos,int pre,int now)//在下标为k的线段树中的pos位置值为pre的节点的值修改为now 
158 {
159     delet(tree[k].root,pre);// 先把pre删掉 
160     insert(tree[k].root,now);// 再把now加上 
161     if(tree[k].l==tree[k].r)
162     {    tree[k].mx=now;    tree[k].mn=now;    return ;/*更改叶节点的值 */    }
163     int mid=(tree[k].l+tree[k].r)>>1;
164     if(pos<=mid)    modify(ls,pos,pre,now);
165     if(pos>mid)        modify(rs,pos,pre,now);
166     pushup_s(k);// 别忘了上传标记！ 
167 }
168 inline int query_pre(int k,int l,int r,int val)// 求在区间l到r中val的前驱 
169 {
170     if(l<=tree[k].l&&tree[k].r<=r)
171         return s[getpre(tree[k].root,val)].num;
172     int mid=(tree[k].l+tree[k].r)>>1,ret=-1;
173     if(l<=mid)    ret=max(ret,query_pre(k<<1,l,r,val));
174     if(mid<r)    ret=max(ret,query_pre(k<<1|1,l,r,val));
175     return ret;
176 }
177 inline int query_suc(int k,int l,int r,int val)// 求在区间l到r中val的后继 
178 {
179     if(l<=tree[k].l&&tree[k].r<=r)
180         return s[getsuc(tree[k].root,val)].num;
181     int mid=(tree[k].l+tree[k].r)>>1,ret=1e8+1;
182     if(l<=mid)    ret=min(ret,query_suc(k<<1,l,r,val));
183     if(mid<r)    ret=min(ret,query_suc(k<<1|1,l,r,val));
184     return ret;
185 }
186 inline int query_number(int L,int R,int val)// 在L到R的区间中查找val的排名 
187 {
188     int l=1,r=getmax(1,L,R),mid,ret,tmp;
189     while(l<=r)//二分答案 
190     {
191         mid=(l+r)>>1;
192         tmp=query_order(1,L,R,mid);
193         if(tmp<val)
194             ret=mid,    l=mid+1;
195         else
196             r=mid-1;
197     }
198     return ret;
199 }
200 int n,m;
201 int date[MAXN];
202 int main()
203 {
204     read(n);read(m);
205     buildseg(1,1,n);//建好线段树 
206     for(int i=1;i<=n;i++)    read(date[i]);//读入初始数据 
207     for(int i=1;i<=n;i++)
208         build(1,i,date[i]);//把每一个元素都插到线段树里面去 
209     dfsseg(1);// 把线段树的所有节点增加两个虚节点 
210     while(m--)
211     {
212         int l,r,k,pos,opt;
213         read(opt);
214         if(opt==1)//查询k在l到r中的排名 
215         {
216             read(l);read(r);read(k); 
217             printf("%d\n",query_order(1,l,r,k)+1);
218         }
219         if(opt==2)// 查询排名为k的值 
220         {
221             read(l);read(r);read(k);
222             printf("%d\n",query_number(l,r,k));
223         }
224         if(opt==3)// 将pos位置的数修改为k 
225         {
226             read(pos);read(k);
227             modify(1,pos,date[pos],k);
228             date[pos]=k;//顺便修改date的值 
229         }
230         if(opt==4)
231         {
232             read(l);read(r);read(k);
233             int tmp=query_pre(1,l,r,k);// 查询tmp的前驱 
234             if(tmp!=1e8+1)
235                 printf("%d\n",tmp);
236             else
237                 printf("%d\n",getmax(1,l,r));
238             //printf("-2147483647\n");
239         }
240         if(opt==5)
241         {
242             read(l);read(r);read(k);
243             int tmp=query_suc(1,l,r,k);
244             if(tmp!=-1)
245                 printf("%d\n",tmp);
246             else
247                 printf("%d\n",getmin(1,l,r));
248             //printf("2147483647\n");
249         }
250     }
251     return 0;
252 }

本文参与腾讯云自媒体分享计划，分享自作者个人站点/博客。

原始发表：2017-08-09 ，如有侵权请联系 cloudcommunity@tencent.com 删除

数据结构