首页 > > 程序设计 > C/C++ >

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

2018-06-17 22:05:47来源：未知 阅读 ()

新老客户大回馈,云服务器低至5折

内存限制：512 MiB时间限制：4000 ms标准输入输出
题目类型：传统评测方式：文本比较
上传者： 匿名
提交提交记录统计讨论测试数据
 

题目描述

这是一道模板题。

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

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

输入格式

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

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

  1. 之后有三个数 l,r,x l, r, xl,r,x 表示查询 x xx 在区间 [l,r] [l, r][l,r] 的排名；
  2. 之后有三个数 l,r,k l, r, kl,r,k 表示查询区间 [l,r] [l, r][l,r] 内排名为 k kk 的数；
  3. 之后有两个数 pos,x \mathrm{pos}, xpos,x 表示将 pos \mathrm{pos}pos 位置的数修改为 x xx；
  4. 之后有三个数 l,r,x l, r, xl,r,x 表示查询区间 [l,r] [l, r][l,r] 内 x xx 的前趋；
  5. 之后有三个数 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

样例输出

2
4
3
4
9

数据范围与提示

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×10?4??,−10?8??≤k,x≤10?8??

显示分类标签

 

 

树套树，我写的是线段树套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 }

 

标签：

版权申明：本站文章部分自网络，如有侵权，请联系：west999com@outlook.com
特别注意：本站所有转载文章言论不代表本站观点，本站所提供的摄影照片，插画，设计作品，如需使用，请与原作者联系，版权归原作者所有

上一篇：3674: 可持久化并查集加强版

下一篇：条形码问题 dp+求某个序列在某种排列中的序号的方法

相关文章

IDC资讯： 主机资讯 注册资讯 托管资讯 vps资讯 网站建设

网站运营： 建站经验 策划盈利 搜索优化 网站推广 免费资源

网站联盟： 联盟新闻 联盟介绍 联盟点评 网赚技巧

行业资讯： 搜索引擎 网络游戏 电子商务 广告传媒

网络编程： Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它

服务器技术： Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护

软件技巧： 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷

网页制作： FrontPages Dreamweaver Javascript css photoshop fireworks Flash

程序设计： Java技术 C/C++ VB delphi

网络知识： 网络协议 网络安全 网络管理 组网方案 Cisco技术

操作系统： Win2000 WinXP Win2003 Mac OS Linux FreeBSD

热门词条
最新资讯
热门关注
热门标签