[关闭]
@zzzc18 2017-06-23T09:35:40.000000Z 字数 4915 阅读 1132

树套树 Treap+Segment_Tree

线段树 Treap

二逼平衡树

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

1.查询k在区间内的排名

2.查询区间内排名为k的值

3.修改某一位值上的数值

4.查询k在区间内的前驱(前驱定义为严格小于x，且最大的数，若不存在输出-2147483647)

5.查询k在区间内的后继(后继定义为严格大于x，且最小的数，若不存在输出2147483647)

总之上面的询问就是树套树的套路了

洛谷上的数据很铁，时间也紧，不加奇技淫巧的优化本方法过不了（正解往往是CDQ分治和zky线段树等）

我就(zhi)说(hui)Treap+线段树

询问是区间内的，所以线段树在外层，Treap在内层

每一个线段树节点是一个Treap //参见Build函数

由于每个节点单独一个Treap开不下，Treap的空间要统一使用，但每个Treap有自己的root和size //见node

操作1：和线段树的查询一样，只不过在区间内要用Treap去找比查询值小的数的个数，求和后再加1

操作2：看代码，通过二分找到其值究竟是多少

操作3：线段树单点修改，在经过节点的Treap删去原来的值，加入新值

操作4，5：凡是满足条件的线段树区间内都用Treap把前驱后继求一下，前驱取最大值，后继取最小值（注意返回值：若没有找到，前驱返回-INF，后即返回INF）

讲完了。。。

  1. #prag\
  2. ma GCC optimize("O3")
  4. #include<cstdio>
  5. #include<cstdlib>
  6. #include<algorithm>
  7. #define MAXN 1200009
  8. #define INF 0x7fffffff
  9. using namespace std;
  11. int n,m;
  12. int a[MAXN];
  14. struct T_T{
  15.     int ls,rs,rd,sz,num,val;
  16. }node[MAXN];
  17. int size;
  19. class Tree_Heap{
  20.     public:
  21.         int root,ans;
  22.         int m;
  24.         void update(int x){
  25.             node[x].sz=node[node[x].ls].sz+node[node[x].rs].sz+node[x].num;
  26.         }
  28.         void rotate_l(int &k){
  29.             int y=node[k].rs;
  30.             node[k].rs=node[y].ls;
  31.             node[y].ls=k;
  32.             node[y].sz=node[k].sz;
  33.             update(k);
  34.             k=y;
  35.         }
  37.         void rotate_r(int &k){
  38.             int y=node[k].ls;
  39.             node[k].ls=node[y].rs;
  40.             node[y].rs=k;
  41.             node[y].sz=node[k].sz;
  42.             update(k);
  43.             k=y;
  44.         }
  46.         void insert(int &k,int v){
  47.             if(k==0){
  48.                 size++;k=size;node[k].val=v;
  49.                 node[k].sz=node[k].num=1;node[k].rd=rand();
  50.                 return;
  51.             }
  52.             node[k].sz++;
  53.             if(node[k].val==v){
  54.                 node[k].num++;
  55.             }
  56.             else if(v>node[k].val){
  57.                 insert(node[k].rs,v);
  58.                 if(node[node[k].rs].rd<node[k].rd)rotate_l(k);
  59.             }
  60.             else{
  61.                 insert(node[k].ls,v);
  62.                 if(node[node[k].ls].rd<node[k].rd)rotate_r(k);
  63.             }
  64.         }
  66.         void del(int &k,int v){
  67.             if(k==0)return;
  68.             if(node[k].val==v){
  69.                 if(node[k].num>1){
  70.                     node[k].sz--;node[k].num--;
  71.                     return;
  72.                 }
  73.                 if(node[k].ls==0 || node[k].rs==0)k=node[k].ls+node[k].rs;
  74.                 else if(node[node[k].ls].rd<node[node[k].rs].rd){
  75.                     rotate_r(k);
  76.                     del(k,v);
  77.                 }
  78.                 else{
  79.                     rotate_l(k);
  80.                     del(k,v);
  81.                 }
  82.             }
  83.             else if(node[k].val<v){
  84.                 node[k].sz--;
  85.                 del(node[k].rs,v);
  86.             }
  87.             else{
  88.                 node[k].sz--;
  89.                 del(node[k].ls,v);
  90.             }
  91.         }
  93.         int n2r(int x){
  94.             int u=root;int re=1;
  95.             while(u){
  96.                 if(node[u].val<x){
  97.                     re+=node[node[u].ls].sz+node[u].num;
  98.                     u=node[u].rs;
  99.                 }
  100.                 else
  101.                     u=node[u].ls;
  102.             }
  103.             return re;
  104.         }
  106.         int r2n(const int &k,int x){
  107.             if(k==0) return 0;
  108.             if(x<=node[node[k].ls].sz) return r2n(node[k].ls,x);
  109.             else if(x>node[node[k].ls].sz+node[k].num)return r2n(node[k].rs,x-node[k].num-node[node[k].ls].sz);
  110.             else return node[k].val;
  111.         }
  113.         void pred(const int &k,int x){
  114.             if(k==0)return;
  115.             if(node[k].val<x){
  116.                 ans=k;
  117.                 pred(node[k].rs,x);
  118.             }
  119.             else{
  120.                 pred(node[k].ls,x);
  121.             }
  122.         }
  124.         void succ(const int &k,int x){
  125.             if(k==0)return;
  126.             if(node[k].val>x){
  127.                 ans=k;
  128.                 succ(node[k].ls,x);
  129.             }
  130.             else
  131.                 succ(node[k].rs,x);
  132.         }
  134.         int Succ(int x){
  135.             ans=0;
  136.             succ(root,x);
  137.             return ans?node[ans].val:INF;
  138.         }
  140.         int Pred(int x){
  141.             ans=0;
  142.             pred(root,x);
  143.             return ans?node[ans].val:-INF;
  144.         }
  146.         void INS(int x){
  147.             insert(root,x);
  148.         }
  150.         void DEL(int x){
  151.             del(root,x);
  152.         }
  154.         int N2R(int x){
  155.             return n2r(x);
  156.         }
  158.         void DEBUG(int k){
  159.             if(k==0)
  160.                 return;
  161.             DEBUG(node[k].ls);
  162.             printf("DEBUG-------%d\n",node[k].val);
  163.             DEBUG(node[k].rs);
  164.         }
  165. };
  167. class Segment_Tree_For_Treap{
  168.     public:
  169.         Tree_Heap Treap[MAXN];
  170.         int cnt;
  171.         struct T_T_T{
  172.             int ls,rs,left_range,right_range;
  173.         }tree[MAXN];
  174.         int rank(int k,int l,int r,int v){
  175.             if(l<=tree[k].left_range && tree[k].right_range<=r){
  176.                 int t=Treap[k].N2R(v)-1;
  177.                 return t;
  178.             }
  179.             int re=0;
  180.             int mid=(tree[k].left_range+tree[k].right_range)>>1;
  181.             if(l<=mid) re+=rank(tree[k].ls,l,r,v);
  182.             if(mid+1<=r) re+=rank(tree[k].rs,l,r,v);
  183.             return re;
  184.         }
  186.         int Build(int l,int r){
  187.             int now=++cnt;
  188.             tree[now].left_range=l;tree[now].right_range=r;
  189.             if(l==r){
  190.                 Treap[now].INS(a[l]);
  191.                 //Treap[now].DEBUG(Treap[now].root);
  192.                 //printf("\n\n");
  193.                 return now;
  194.             }
  195.             for(int i=l;i<=r;i++){
  196.                 Treap[now].INS(a[i]);
  197.                 //Treap[now].DEBUG(Treap[now].root);
  198.                 //printf("\n\n");
  199.             }
  200.             int mid=(l+r)>>1;
  201.             tree[now].ls=Build(l,mid);
  202.             tree[now].rs=Build(mid+1,r);
  203.             return now;
  204.         }
  206.         void change(int k,int pos,int v){
  207.             Treap[k].DEL(a[pos]);
  208.             Treap[k].INS(v);
  209.             //Treap[k].DEBUG(Treap[k].root);
  210.             //printf("\n\n");
  211.             if(tree[k].left_range==tree[k].right_range){
  212.                 a[pos]=v;
  213.                 return;
  214.             }
  215.             int mid=(tree[k].left_range+tree[k].right_range)>>1;
  216.             if(pos<=mid)change(tree[k].ls,pos,v);
  217.             else change(tree[k].rs,pos,v);
  218.         }
  220.         int Pred(int k,int l,int r,int v){
  221.             if(l<=tree[k].left_range && tree[k].right_range<=r){
  222.                 return Treap[k].Pred(v);
  223.             }
  224.             int s=-INF;
  225.             int mid=(tree[k].left_range+tree[k].right_range)>>1;
  226.             if(l<=mid) s=max(s,Pred(tree[k].ls,l,r,v));
  227.             if(mid+1<=r) s=max(s,Pred(tree[k].rs,l,r,v));
  228.             return s;
  229.         }
  231.         int Succ(int k,int l,int r,int v){
  232.             if(l<=tree[k].left_range && tree[k].right_range<=r){
  233.                 return Treap[k].Succ(v);
  234.             }
  235.             int s=INF;
  236.             int mid=(tree[k].left_range+tree[k].right_range)>>1;
  237.             if(l<=mid) s=min(s,Succ(tree[k].ls,l,r,v));
  238.             if(mid+1<=r) s=min(s,Succ(tree[k].rs,l,r,v));
  239.             return s;
  240.         }
  242.         int n2r(int l,int r,int val){
  243.             return rank(1,l,r,val)+1;
  244.         }
  246.         int r2n(int k,int l,int r,int v){
  247.             int ll=0,rr=100000000;
  248.             while(ll<=rr){
  249.                 int mid=(ll+rr)>>1;
  250.                 if(n2r(l,r,mid)>v) rr=mid-1;
  251.                 else ll=mid+1;
  252.             }
  253.             return rr;
  254.         }
  255. }Seg;
  257. int zz(){
  258.     scanf("%d%d",&n,&m);
  259.     int i;
  260.     for(i=1;i<=n;i++)
  261.         scanf("%d",&a[i]);
  262.     Seg.Build(1,n);
  263.     for(i=1;i<=m;i++){
  264.         int opt,l,r,k,pos;
  265.         scanf("%d",&opt);
  266.         if(opt==1){
  267.             scanf("%d%d%d",&l,&r,&k);
  268.             printf("%d\n",Seg.n2r(l,r,k));
  269.         }
  270.         if(opt==2){
  271.             scanf("%d%d%d",&l,&r,&k);
  272.             printf("%d\n",Seg.r2n(1,l,r,k));
  273.         }
  274.         if(opt==3){
  275.             scanf("%d%d",&pos,&k);
  276.             Seg.change(1,pos,k);
  277.         }
  278.         if(opt==4){
  279.             scanf("%d%d%d",&l,&r,&k);
  280.             printf("%d\n",Seg.Pred(1,l,r,k));
  281.         }
  282.         if(opt==5){
  283.             scanf("%d%d%d",&l,&r,&k);
  284.             printf("%d\n",Seg.Succ(1,l,r,k));
  285.         }
  286.     }
  287.     return 0;
  288. }
  290. int zzz=zz();
  292. int main(){
  293.     ;
  294. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注