树套树小结-白红宇

树套树小结

阅读量：5103 次

发布时间：2019-06-13

本文共 32350 字，大约阅读时间需要 107 分钟。

（写篇博客证明自己还活着）

在OI中，有些时候我们会遇到一些维护多维信息的题目，比如经典的三维偏序，或者带修改区间k小值

这个时候有的dalao就会跳出来大喊“整体二分！”“CDQ！”

然而这并不是我们今天讨论的重点……并且在强制在线的情况下，上面这两种算法就无能为力了。

那么我们就需要用数据结构乱堆树套树的方法来解决这类问题。这类树套树解法以码量大和难调试著称。

通过用一种（棵？）数据结构维护一维信息，我们可以实现在线地维护多维信息。

那么让我们开始总结一下树套树吧！

一.线段树/树状数组套平衡树

这大概是没接触过树套树的同学接触的第一种树套树类型吧。。。

这种套法一般是用外层的树维护区间信息，在外层树的每一个节点放一棵内层树，内层的树维护权值信息。

比如说查区间第k大，用套平衡树的做法就是二分权值val->到这个区间对应的log个线段树节点上查val的rank值，加起来与目标值进行比较

这种做法的空间需求是$O(nlogn)$的，由于每个元素都会在logn个外层树节点中插入自己

而时间复杂度上，除了查询区间第k大，每次操作是O(nlog2n)的，

由于在logn个外层树上都要用$O(logn)$的时间查询

查询第k大是$O(nlog3n)$的，由于在logn个外层树上都要用$O(logn)$的时间查询。

这种类型的树套树，经典的有：

bzoj3196 二逼平衡树

1 #include
      
         2 #include
       
          3 #include
        
           4 #include
         
            5 #include
          
             6 using namespace std;  7 const int N=50000+10;  8 int val[N],n,m,a,b,c,o;  9 struct node 10 { 11     node* ch[2]; 12     int rank,val,size,ge; 13     node (int x){val=x;rank=rand();size=ge=1;ch[1]=ch[0]=NULL;} 14     void tain() 15     { 16         size=1; 17         if(ch[0])size+=ch[0]->size; 18         if(ch[1])size+=ch[1]->size; 19     } 20 }; 21 inline int s(node* o){
    return o?o->size:0;} 22 node* root[4*N]; 23 void rotate(node* &o,int d) 24 { 25     node* k=o->ch[d^1];o->ch[d^1]=k->ch[d];k->ch[d]=o; 26     o->tain();k->tain();o=k; 27 } 28 void insert(node* &o,int val) 29 { 30     if(o==NULL){o=new node(val);return;} 31     if(val
           
            val) 32 { 33 insert(o->ch[0],val); 34 if(o->ch[0]->rank > o->rank) 35 rotate(o,1); 36 } 37 else 38 { 39 insert(o->ch[1],val); 40 if(o->ch[1]->rank > o->rank) 41 rotate(o,0); 42 } 43 o->tain(); 44 } 45 inline void build(int le,int ri,int num) 46 { 47 for(int i=le;i<=ri;i++)insert(root[num],val[i]); 48 } 49 void treeins(int le,int ri,int num) 50 { 51 build(le,ri,num); 52 if(le==ri)return; 53 int mi=(le+ri)>>1; 54 treeins(le,mi,num<<1); 55 treeins(mi+1,ri,(num<<1)|1); 56 } 57 void remove(node* &o,int val) 58 { 59 if(val==o->val) 60 { 61 if(o->ch[0]&&o->ch[1]) 62 { 63 int d2=(o->ch[0]->rank > o->ch[1]->rank)?1:0; 64 rotate(o,d2);remove(o->ch[d2],val); 65 } 66 else 67 { 68 node* u=NULL; 69 if(o->ch[0]!=NULL)u=o->ch[0]; 70 else u=o->ch[1]; 71 delete o; 72 o=u; 73 } 74 } 75 else 76 if(val< o->val)remove(o->ch[0],val); 77 else remove(o->ch[1],val); 78 if(o)o->tain(); 79 } 80 inline int find_rank(node* o,int val) 81 { 82 int ge=0; 83 while(o) 84 { 85 if(val> o->val)ge+=s(o->ch[0])+1,o=o->ch[1]; 86 else o=o->ch[0]; 87 } 88 return ge; 89 } 90 int tree_rank(int le,int ri,int num,int val) 91 { 92 if(a<=le&&ri<=b)return find_rank(root[num],val); 93 int mi=(le+ri)>>1; 94 int ret=0; 95 if(b<=mi)return tree_rank(le,mi,num<<1,val); 96 if(mi
            
             >1;105 int ans=tree_rank(1,n,1,mi)+1; 106 if(ans<=val)l=mi+1;107 else r=mi-1;108 }109 return r;110 }111 inline int pre(int le,int ri,int val)112 {113 int tmp=tree_rank(1,n,1,val);114 return divide_rank(tmp);115 }116 inline int re(int le,int ri,int val)117 {118 int tmp=tree_rank(1,n,1,val+1)+1;119 return divide_rank(tmp);120 }121 void change(int le,int ri,int num,int pos,int pre,int now)122 {123 remove(root[num],pre);124 insert(root[num],now);125 if(le==ri)return;126 int mi=(le+ri)>>1;127 if(pos<=mi)change(le,mi,num<<1,pos,pre,now);128 else change(mi+1,ri,(num<<1)|1,pos,pre,now);129 }130 int main()131 {132 scanf("%d%d",&n,&m);133 for(int i=1;i<=n;i++)134 scanf("%d",&val[i]);135 treeins(1,n,1);136 while(m--)137 {138 scanf("%d",&o);139 switch(o)140 {141 case 1:142 scanf("%d%d%d",&a,&b,&c);143 printf("%d\n",tree_rank(1,n,1,c)+1);break;144 case 2:145 scanf("%d%d%d",&a,&b,&c);146 printf("%d\n",divide_rank(c));break;147 case 3:148 scanf("%d%d",&a,&b);149 change(1,n,1,a,val[a],b);val[a]=b;break;150 case 4:151 scanf("%d%d%d",&a,&b,&c);152 printf("%d\n",pre(a,b,c));break;153 case 5:154 scanf("%d%d%d",&a,&b,&c);155 printf("%d\n",re(a,b,c));break;156 }157 }158 //while(1);159 }

BZOJ3196

bzoj3262 陌上花开

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 const int N=100010,K=200010; 6 int n,k,tot,bit[K]; 7 struct node 8 { 9     int a,b,c,val,id,ans;10     node(){val=ans=0;}11     inline void read(){scanf("%d%d%d",&a,&b,&c);}12     inline void print()13         {printf("a=%d b=%d c=%d val=%d id=%d\n",a,b,c,val,id);}14 }q[N],tmp[N];15 int cnt[N],st[N];16 inline int lowbit(int a){
    return a&-a;}17 inline void add(int a,int val)18     {
    while(a<=k)bit[a]+=val,a+=lowbit(a);}19 inline int query(int a)20     {
    int ret=0;while(a)ret+=bit[a],a-=lowbit(a);return ret;}21 inline bool mt1(const node &a,const node &b)22 {23     if(a.a==b.a&&a.b==b.b)return a.c
         
          >1,l1=l,l2=mi+1;37     for(i=l;i<=r;++i)38         if(q[i].a<=mi)add(q[i].c,q[i].val);39         else q[i].ans+=query(q[i].c);40     for(i=l;i<=r;++i)41         if(q[i].a<=mi)add(q[i].c,-q[i].val);42     for(i=l;i<=r;++i)43         if(q[i].a<=mi)tmp[l1++]=q[i];44         else tmp[l2++]=q[i];45     for(i=l;i<=r;++i)q[i]=tmp[i];46     CDQ(l,mi),CDQ(mi+1,r);47 }48 int main()49 {50     register int i,j,sum;51     scanf("%d%d",&n,&k);sum=n;52     for(i=1;i<=n;++i)q[i].read(),q[i].val=1;53     sort(q+1,q+n+1,mt1);54     for(n=1,i=2;i<=sum;++i)55         if(same(q[i],q[n]))++q[n].val;56         else q[++n]=q[i];57     for(i=1;i<=n;++i)q[i].a=i;58     sort(q+1,q+n+1,mt2);59     CDQ(1,n);60     for(i=1;i<=n;++i)cnt[q[i].ans]+=q[i].val;61     for(i=0;i

CDQ打法

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 #include 
          
             6 using namespace std;  7 char B[1<<15],*S=B,*T=B;  8 #define getc ( (S==T&&( (T=(S=B)+fread(B,1,1<<15,stdin)),S==T) ) ?0:*S++ )  9 inline int read() 10 { 11     int x=0;register char c=getc; 12     while(c<'0'||c>'9')c=getc; 13     while(c>='0'&&c<='9')x=10*x+(c^48),c=getc; 14     return x; 15 } 16 #define N 100010 17 #define K 200010 18 struct flower{ 19     int a,b,c,ge; 20     inline void init(){a=read(),b=read(),c=read(),ge=1;} 21     inline bool operator == (const flower x) const 22         {
    return a==x.a&&b==x.b&&c==x.c;} 23 }f[N]; 24 inline bool mt(const flower &a,const flower &b) 25 { 26     if(a.a!=b.a)return a.a
           
            size+ch[1]->size;} 35 }mema[N<<5],*null=new Treap(); 36 inline Treap* newTreap(int val=0,int size=0,int key=rand()) 37 { 38 Treap *o=mema+(tota++);o->ch[0]=o->ch[1]=null; 39 o->val=val,o->cnt=o->size=size,o->key=key; 40 return o; 41 } 42 inline Treap* merge(Treap *a,Treap *b) 43 { 44 if(a==null)return b; 45 if(b==null)return a; 46 if(a->key > b->key) 47 {a->ch[1]=merge(a->ch[1],b);a->update();return a;} 48 else 49 {b->ch[0]=merge(a,b->ch[0]);b->update();return b;} 50 } 51 #define D pair
            
              52 inline D split(Treap *o,int val) 53 { 54 if(o==null)return D(null,null); 55 D y; 56 if(o->val>val) 57 y=split(o->ch[0],val),o->ch[0]=y.second,o->update(),y.second=o; 58 else 59 y=split(o->ch[1],val),o->ch[1]=y.first,o->update(),y.first=o; 60 return y; 61 } 62 inline void insert(Treap *&o,flower p,int key) 63 { 64 if(o->key
             
              ch[0]=y.first,x->ch[1]=y.second,x->update(),o=x; 69 return; 70 } 71 if(o->val>p.c)insert(o->ch[0],p,key); 72 else insert(o->ch[1],p,key); 73 o->update(); 74 } 75 inline int grs(Treap *o,int val) 76 { 77 if(o==null)return 0; 78 return (o->val>val)?grs(o->ch[0],val):grs(o->ch[1],val)+o->ch[0]->size+o->cnt; 79 } 80 #define max(a,b) ((a)>(b)?(a):(b)) 81 #define min(a,b) ((a)<(b)?(a):(b)) 82 int maxb; 83 struct node 84 { 85 Treap *alter;node *ch[2]; 86 }*root,memb[K<<1]; 87 inline node* build(int l,int r) 88 { 89 node *o=memb+(totb++);o->alter=null; 90 if(l==r)return o; 91 int mi=l+r>>1; 92 o->ch[0]=build(l,mi);o->ch[1]=build(mi+1,r); 93 return o; 94 } 95 inline void insert(node *&o,int l,int r,flower p) 96 { 97 insert(o->alter,p,rand()); 98 if(l==r)return; 99 int mi=l+r>>1;100 if(p.b<=mi)insert(o->ch[0],l,mi,p);101 else insert(o->ch[1],mi+1,r,p);102 }103 inline int query(node *o,int l,int r,int L,int R,int val)104 {105 if(L<=l&&r<=R)return grs(o->alter,val);106 int mi=l+r>>1,ret=0;107 if(L<=mi)ret=query(o->ch[0],l,mi,L,R,val);108 if(mi
              
               ch[1],mi+1,r,L,R,val);109 return ret;110 }111 inline void intn()112 {113 null=mema+(tota++),null->size=null->cnt=null->val=0;114 null->key=-1;null->ch[0]=null->ch[1]=null;115 root=build(1,maxb);116 }117 int main()118 {119 register int i,sum;120 n=read(),k=read();121 for(i=1;i<=n;++i)f[i].init(),maxb=max(maxb,f[i].b);122 sort(f+1,f+n+1,mt);intn();123 for(sum=n,n=1,i=2;i<=sum;++i)124 if(f[i]==f[n])++f[n].ge;125 else f[++n]=f[i];126 for(i=1;i<=n;++i)127 insert(root,1,maxb,f[i]),128 cnt[query(root,1,maxb,1,f[i].b,f[i].c)-1]+=f[i].ge;129 for(i=0;i

树套树打法

bzoj3295 动态逆序对

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5 typedef long long LL; 6 const int N=100010,M=50010; 7 struct node 8 { 9     int tim,val,pos;10     node (int a=0,int b=0,int c=0){tim=a,val=b,pos=c;}11 }q[N];12 int cnt,n,m,a[N],match[N],step[M];13 bool vis[N];14 LL delta[2][N],num[2][N],bit[N];15 inline int lowbit(int a){
    return a&-a;}16 inline void add(int a,LL b)17     {
    while(a<=n)bit[a]+=b,a+=lowbit(a);}18 inline LL sum(int a)19     {LL ret=0;while(a)ret+=bit[a],a-=lowbit(a);return ret;}20 inline void gsum0()21 {22     for(register int i=1;i<=n;++i)23         num[0][i]=sum(a[i]),add(a[i],1);24     memset(bit,0,sizeof(bit));25 }26 inline void gsum1()27 {28     for(register int i=n;i;--i)29         num[1][i]=sum(a[i]),add(1,1),add(a[i],-1);30     memset(bit,0,sizeof(bit));31 }32 inline void readin()33 {34     register int i;scanf("%d%d",&n,&m);35     for(i=1;i<=n;++i)36         scanf("%d",&a[i]),a[i]=n-a[i]+1,match[a[i]]=i;37     gsum0();gsum1();38     for(i=1;i<=m;++i)39         scanf("%d",&step[i]),step[i]=n-step[i]+1,vis[step[i]]=1;40 }41 inline bool mt1(const node &a,const node &b){
    return a.pos
         
          >1,i;47     CDQ0(l,mi);CDQ0(mi+1,r);48     sort(q+l,q+r+1,mt1);49     for(i=l;i<=r;++i)50         if(q[i].tim<=mi)add(q[i].val,1);51         else delta[0][q[i].tim]+=sum(q[i].val);52     for(i=l;i<=r;++i)53         if(q[i].tim<=mi)add(q[i].val,-1);54 }55 inline void CDQ1(int l,int r)56 {57     if(l==r)return;58     register int mi=l+r>>1,i;59     CDQ1(l,mi);CDQ1(mi+1,r);60     sort(q+l,q+r+1,mt1);61     for(i=r;i>=l;--i)62         if(q[i].tim<=mi)add(1,1),add(q[i].val,-1);63         else delta[1][q[i].tim]+=sum(q[i].val);64     for(i=r;i>=l;--i)65         if(q[i].tim<=mi)add(1,-1),add(q[i].val,1);66 }67 int main()68 {69     register int i;readin();70     for(i=1;i<=m;++i)71         q[++cnt]=node(cnt,step[i],match[step[i]]);72     for(i=1;i<=n;++i)73         if(!vis[a[i]])q[++cnt]=node(cnt,a[i],i);74     CDQ0(1,n),sort(q+1,q+n+1,mt2),CDQ1(1,n);75     LL ans=0;int pos;76     for(i=1;i<=n;++i)ans+=num[0][i];77     for(i=1;i<=m;++i)78     {79         printf("%lld\n",ans),pos=match[step[i]],80         ans-=(num[0][pos]+num[1][pos]),81         ans+=(delta[0][i]+delta[1][i]);82     }83 }

CDQ打法

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 using namespace std;  6 #define N 100010  7 int n,m,tota,totb;  8 int a[N],b[N],tmp[N];  9 #define LL long long 10 LL ans; 11 struct Treap 12 { 13     int val,size,key;Treap *ch[2]; 14     Treap(){ch[0]=ch[1]=NULL;val=size=0;} 15     inline void update(){size=ch[0]->size+1+ch[1]->size;} 16 }mema[N<<5],*null=new Treap(); 17 inline Treap* newTreap(int val=0,int key=rand()) 18 { 19     Treap *o=mema+(tota++); 20     o->ch[0]=o->ch[1]=null; 21     o->key=key;o->val=val; 22     o->size=1;return o; 23 } 24 inline Treap* merge(Treap* a,Treap* b) 25 { 26     if(a==null)return b; 27     if(b==null)return a; 28     if(a->key > b->key) {a->ch[1]=merge(a->ch[1],b);a->update();return a;} 29     else {b->ch[0]=merge(a,b->ch[0]),b->update();return b;} 30 } 31 #define D pair
          
            32 inline D split1(Treap *o,int k) 33 { 34     if(o==null)return D(null,null); 35     D y; 36     if(o->ch[0]->size>=k) 37         y=split1(o->ch[0],k),o->ch[0]=y.second,o->update(),y.second=o; 38     else  39         y=split1(o->ch[1],k-o->ch[0]->size-1),o->ch[1]=y.first,o->update(),y.first=o; 40     return y; 41 } 42 inline D split2(Treap *o,int val) 43 { 44     if(o==null)return D(null,null); 45     D y; 46     if(o->val>=val) 47         y=split2(o->ch[0],val),o->ch[0]=y.second,o->update(),y.second=o; 48     else  49         y=split2(o->ch[1],val),o->ch[1]=y.first,o->update(),y.first=o; 50     return y; 51 } 52 inline void del(Treap *&o,int val) 53 { 54     if(o==null)return; 55     if(o->val>val)del(o->ch[0],val); 56     else if(o->val==val){o=merge(o->ch[0],o->ch[1]);return;} 57     else del(o->ch[1],val); 58     o->update(); 59 } 60 inline void insert(Treap *&o,int val,int key) 61 { 62     if(o->key
           
            ch[0]=y.first,x->ch[1]=y.second; 67 x->update(),o=x; 68 return; 69 } 70 else if(o->val>=val)insert(o->ch[0],val,key); 71 else insert(o->ch[1],val,key); 72 o->update(); 73 } 74 inline int grb(Treap *o,int val) 75 { 76 if(o==null)return 0; 77 return (o->val<=val)?grb(o->ch[1],val):(grb(o->ch[0],val)+o->ch[1]->size+1); 78 } 79 inline int grs(Treap *o,int val) 80 { 81 if(o==null)return 0; 82 return (o->val>=val)?grs(o->ch[0],val):(grs(o->ch[1],val)+o->ch[0]->size+1); 83 } 84 struct node 85 { 86 Treap *summa;node *ch[2]; 87 node(){ch[0]=ch[1]=NULL;} 88 }memb[N<<1],*root; 89 inline node* build(int l,int r) 90 { 91 node *o=memb+(totb++);o->summa=null; 92 if(l==r)return o; 93 int mi=l+r>>1; 94 o->ch[0]=build(l,mi),o->ch[1]=build(mi+1,r); 95 return o; 96 } 97 inline int queryl(node *o,int l,int r,int L,int R,int val) 98 { 99 if(L<=l&&r<=R)return grb(o->summa,val);100 int mi=l+r>>1,ret=0;101 if(L<=mi)ret=queryl(o->ch[0],l,mi,L,R,val);102 if(mi
            
             ch[1],mi+1,r,L,R,val);103 return ret;104 }105 inline int queryr(node *o,int l,int r,int L,int R,int val)106 {107 if(L<=l&&r<=R)return grs(o->summa,val);108 int mi=l+r>>1,ret=0;109 if(L<=mi)ret=queryr(o->ch[0],l,mi,L,R,val);110 if(mi
             
              ch[1],mi+1,r,L,R,val);111 return ret;112 }113 inline void insert(node *o,int l,int r,int pos,int val)114 {115 insert(o->summa,val,rand());116 if(l==r)return;117 int mi=l+r>>1;118 if(pos<=mi)insert(o->ch[0],l,mi,pos,val);119 else insert(o->ch[1],mi+1,r,pos,val);120 }121 inline void del(node *o,int l,int r,int pos,int val)122 {123 del(o->summa,val);124 if(l==r)return;125 int mi=l+r>>1;126 if(pos<=mi)del(o->ch[0],l,mi,pos,val);127 else del(o->ch[1],mi+1,r,pos,val);128 }129 inline void get_base(int l,int r)130 {131 if(l==r)return;132 int mi=l+r>>1,p=l,q=mi+1,h=l;133 get_base(l,mi),get_base(mi+1,r);134 while(p<=mi&&q<=r)135 if(a[p]
              
               '9')c=getc;147 while(c>='0'&&c<='9')x=10*x+(c^48),c=getc;148 return x;149 }150 int main()151 {152 register int i,j;153 null->ch[0]=null->ch[1]=null,null->key=-0x7fffffff;154 n=read(),m=read(),root=build(1,n);155 for(i=1;i<=n;++i)a[i]=read(),insert(root,1,n,i,a[i]);156 memcpy(b,a,sizeof(a));157 get_base(1,n);158 for(i=1;i<=n;++i)tmp[b[i]]=i;159 while(m--)160 i=read(),j=tmp[i],printf("%lld\n",ans),161 ans-=queryl(root,1,n,1,j,i)+queryr(root,1,n,j,n,i),162 del(root,1,n,j,i);163 }

树套树打法

bzoj2141 排队（和上面那题差不多，就不附代码了）

这些题没有太大的难度，直接按照题意操作即可～

二.线段树/树状数组套权值线段树

如果是套线段树，就是我们常说的“树状数组套主席树”了。

其实这里的内层线段树并不是主席树，而是很多颗权值线段树.

这样套的好处就是让原本静态的主席树变得可以支持修改，因为每次修改只会更改logn级别棵内层树的信息

线段树依然有区间加减性，因此对于某一个给定区间我们可以用log棵权值线段树通过加减来“拼”出对应区间的线段树

所以每一种操作都是$O(nlog²n)$的.

这类树套树的习题有：

bzoj4009 接水果（模型转换之后整体二分or线段树套线段树）

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 using namespace std;  5 #define inf 1000000000  6 #define N 40010  7 int tot,cnt,n,p,q,e,adj[N];  8 struct edge{
    int zhong,next;}s[N<<1];  9 inline void add(int qi,int zhong) 10     {s[++e].zhong=zhong;s[e].next=adj[qi];adj[qi]=e;} 11 char B[1<<15],*S=B,*T=B; 12 #define getc ( S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T)?0:*S++ ) 13 inline int read() 14 { 15     int x=0;register char c=getc; 16     while(c<'0'||c>'9')c=getc; 17     while(c>='0'&&c<='9')x=10*x+(c^48),c=getc; 18     return x; 19 } 20 int f[N][16],bin[25],tp,deep[N]; 21 int st[N],ed[N],val[N],l[N],r[N],num; 22 inline void mission1(int rt) 23     {
    for(int i=1;i<=tp;++i)f[rt][i]=f[f[rt][i-1]][i-1];} 24 inline int LCA(int a,int b) 25 { 26     if(deep[a]
         
          0;i-=lowbit(i))ret+=bit[i]; 59     return ret; 60 } 61 struct plate{
    int x1,x2,y1,y2,val;}pl[N<<1]; 62 struct fruit{
    int x,y,k,id;}fr[N],tmp1[N],tmp2[N]; 63 struct node{
    int x,y1,y2,val,id;}eve[N*5]; 64 inline bool mt(const plate &a,const plate &b){
    return a.val
          
           R)return; 69     if(le==ri) 70     { 71         for(int i=L;i<=R;++i)ans[fr[i].id]=pl[le].val; 72         return; 73     } 74     int a=0,b=0,mi=le+ri>>1;tot=0; 75     for(int i=le;i<=mi;++i) 76         eve[++tot]=(node){pl[i].x1,pl[i].y1,pl[i].y2,1,0}, 77         eve[++tot]=(node){pl[i].x2,pl[i].y1,pl[i].y2,-1,q+1}; 78     for(int i=L;i<=R;++i) 79         eve[++tot]=(node){fr[i].x,fr[i].y,0,0,i}; 80     sort(eve+1,eve+tot+1,mt2); 81     for(int i=1;i<=tot;++i) 82         if(L<=eve[i].id&&eve[i].id<=R)sum[eve[i].id]=query(eve[i].y1); 83         else update(eve[i].y1,eve[i].y2,eve[i].val); 84     for(int i=L;i<=R;++i) 85         if(sum[i]>=fr[i].k)tmp1[++a]=fr[i]; 86         else tmp2[++b]=fr[i],tmp2[b].k-=sum[i]; 87     for(int i=1;i<=a;++i)fr[i+L-1]=tmp1[i]; 88     for(int i=1;i<=b;++i)fr[i+L+a-1]=tmp2[i]; 89     get_ans(le,mi,L,L+a-1),get_ans(mi+1,ri,L+a,R); 90 } 91 int main() 92 { 93     register int i,j,a,b,c,lca,x; 94     n=read(),p=read(),q=read(); 95     for(i=bin[0]=1;i<=20;++i)bin[i]=bin[i-1]<<1; 96     while(bin[tp+1]<=n)++tp; 97     for(i=1;i
           
            l[b])a^=b,b^=a,a^=b;103 if(a!=lca)104 pl[++cnt]=(plate){l[a],r[a],l[b],r[b],c};105 else106 {107 x=gonear(b,a);108 if(l[x]>1)pl[++cnt]=(plate){ 1,l[x]-1,l[b],r[b],c};109 if(r[x]
            
             l[b])a^=b,b^=a,a^=b;116 fr[i]=(fruit){l[a],l[b],c,i};117 }118 sort(pl+1,pl+cnt+1,mt),get_ans(1,cnt,1,q);119 for(i=1;i<=q;++i)printf("%d\n",ans[i]);120 }

整体二分

（没打树套树……懒了233）

bzoj1146 网络管理Network（树状数组套主席树上树）

1 #include 
      
         2 #include 
       
          3 using namespace std;  4 #define N 80010  5 #define inf 100000000  6 char B[1<<15],*S=B,*T=B;  7 #define GG puts("invalid request!")  8 #define getc ( S==T&&(T=(S=B)+fread(B,1,1<<15,stdin),S==T) ?0:*S++ )  9 inline int read() 10 { 11     int x=0;register char c=getc; 12     while(c<'0'||c>'9')c=getc; 13     while(c>='0'&&c<='9')x=10*x+(c^48),c=getc; 14     return x; 15 } 16 int n,e=0,adj[N],t[N],tot,m; 17 struct edge{
    int zhong,next;}s[N<<1]; 18 inline void add(int qi,int zhong) 19     {s[++e].zhong=zhong;s[e].next=adj[qi];adj[qi]=e;} 20 #define lowbit(a) ((a)&(-(a))) 21 int num,l[N],r[N]; 22 struct node 23 { 24     node *ch[2];int size; 25     node(){ch[0]=ch[1]=NULL;size=0;} 26 }*root[N<<1],mem[(N<<8)+10],*null,*stacka[1010],*stackb[1010]; 27 inline void insert(node *&o,int l,int r,int pos,int val) 28 { 29     if(o==null) 30         o=mem+(tot++),o->size=0,o->ch[0]=o->ch[1]=null; 31     o->size+=val;if(l==r)return; 32     int mi=l+r>>1; 33     if(pos<=mi)insert(o->ch[0],l,mi,pos,val); 34     else insert(o->ch[1],mi+1,r,pos,val); 35 } 36 inline void insert(int id,int val,int opt) 37 { 38     while(id<=m) 39         insert(root[id],0,inf,val,opt),id+=lowbit(id); 40 } 41 int f[N][17],bin[25],tp,deep[N],cnta,cntb; 42 inline void mission1(int rt) 43     {
    for(int i=1;i<=tp;++i)f[rt][i]=f[ f[rt][i-1] ][i-1];} 44 inline void dfs1(int rt,int fa) 45 { 46     f[rt][0]=fa,deep[rt]=deep[fa]+1;mission1(rt); 47     l[rt]=++num,insert(l[rt],t[rt],1); 48     for(int i=adj[rt];i;i=s[i].next) 49         if(s[i].zhong!=fa)dfs1(s[i].zhong,rt); 50     r[rt]=++num,insert(r[rt]+1,t[rt],-1); 51 } 52 inline void intn() 53 { 54     null=new node(),null->size=0,null->ch[0]=null->ch[1]=null; 55     for(int i=0;i<=m;++i)root[i]=null; 56     dfs1(1,0); 57 } 58 inline int LCA(int a,int b) 59 {    60     if(deep[a]
        
         0) 71     { 72         if(opt==1)stacka[++cnta]=root[id]; 73         else stackb[++cntb]=root[id]; 74         id-=lowbit(id); 75     } 76 } 77 inline int query(int le,int ri,int k) 78 { 79     if(le==ri)return le; 80     register int i,mi=le+ri>>1,sum=0; 81     for(i=1;i<=cnta;++i)sum+=stacka[i]->ch[1]->size; 82     for(i=1;i<=cntb;++i)sum-=stackb[i]->ch[1]->size; 83     if(sum>=k) 84     { 85         for(i=1;i<=cnta;++i)stacka[i]=stacka[i]->ch[1]; 86         for(i=1;i<=cntb;++i)stackb[i]=stackb[i]->ch[1]; 87         return query(mi+1,ri,k); 88     } 89     else 90     { 91         for(i=1;i<=cnta;++i)stacka[i]=stacka[i]->ch[0]; 92         for(i=1;i<=cntb;++i)stackb[i]=stackb[i]->ch[0]; 93         return query(le,mi,k-sum); 94     } 95 } 96 inline void get_ans(int le,int ri,int k) 97 { 98     int lca=LCA(le,ri); 99     if(k> deep[le]+deep[ri]- (deep[lca]<<1) +1 ){GG;return;}100     cnta=cntb=0,101     get(l[le],1),get(l[lca],-1),102     get(l[ri],1),get(l[f[lca][0]],-1);103     printf("%d\n",query(0,inf,k));104 }105 inline void change(int pos,int val)106 {107     insert(l[pos],t[pos],-1),insert(r[pos]+1,t[pos],1),t[pos]=val,108     insert(l[pos],val,1),insert(r[pos]+1,val,-1);109 }110 int main()111 {112     register int i,j,q,a,b,opt;113     n=read(),q=read(),m=n<<1;114     for(bin[0]=i=1;i<=20;++i)bin[i]=bin[i-1]<<1;115     while(bin[tp+1]<=n)++tp;116     for(i=1;i<=n;++i)t[i]=read();117     for(i=1;i

BZOJ1146

三.平衡树套权值线段树/平衡树

这大概是比较高端的一种套法？

有的时候我们会发现线段树无法胜任套在外面这个要求，比如一个常见的原因是区间长度固定，无法支持区间内的插入。

那么我们就需要外层的数据结构是平衡树了：平衡树可以在中间插入。

并且这树还不能旋转，由于旋转带来的父子关系改变带来的维护会耗费大量的时间。

那么我们的选择只剩下替罪羊树和无旋Treap了。

我们一般使用替罪羊树而不是无旋Treap，因为无旋Treap常数大，并且在split和merge时的信息维护也很慢……

在实际编程时，我们就正常的插入，在替罪羊的节点对应的内层树中插入新点的权值，后面的查询操作根据题意而定。

只要没有玩脱这些操作的复杂度也都是$O(nlog²n)$的。

这种类型的题目有：

bzoj3065 带插入区间k小值（替罪羊套权值线段树，操作的时候和树状数组套线段树差不多，提取出通过加减可以表达对应区间的根节点组，然后找到答案。）

1 #include 
      
         2 #include 
       
          3 using namespace std;  4 #define N 70010  5 #define MAXN 70000  6 int n,a[N];  7 char B[1<<15],*S=B,*T=B,X=0;  8 #define getc ( S==T && ( T=(S=B)+fread(B,1,1<<15,stdin), S==T) ? 0: *S++ )  9 inline int read() 10 { 11     int x=0; 12     while(X<'0'||X>'9')X=getc; 13     while(X>='0'&&X<='9')x=10*x+(X^48),X=getc; 14     return x; 15 } 16 inline char readc(){
    while(X<'A'||X>'Z')X=getc;return X;} 17 int topa,topb,top,cnta,cntb; 18 struct node 19 { 20     node* ch[2];int size; 21     node(){size=0,ch[0]=ch[1]=NULL;} 22 }*NIL=new node(),mem[(N<<8)+10],*pool[(N<<8)+10],*stacka[510],*stackb[510]; 23 inline void dfs2(node *o) 24 { 25     if(o==NIL)return; 26     if(o->ch[0]!=NIL)dfs2(o->ch[0]); 27     if(o->ch[1]!=NIL)dfs2(o->ch[1]); 28     o->size=0,o->ch[0]=o->ch[1]=NIL,pool[++topa]=o; 29 } 30 inline void insert(node *&o,int l,int r,int pos) 31 { 32     if(o==NIL)o=pool[topa--],o->size=0,o->ch[0]=o->ch[1]=NIL; 33     ++o->size; 34     if(l
        
         >1; 37         if(pos<=mi)insert(o->ch[0],l,mi,pos); 38         else insert(o->ch[1],mi+1,r,pos); 39     } 40 } 41 inline void del(node *&o,int l,int r,int pos) 42 { 43     --o->size; 44     if(l
         
          >1; 47         if(pos<=mi)del(o->ch[0],l,mi,pos); 48         else del(o->ch[1],mi+1,r,pos); 49     } 50     if(o->size==0) 51         pool[++topa]=o,o=NIL; 52 } 53 inline int get_ans(int l,int r,int k) 54 { 55     if(l==r)return l; 56     register int i,sum=0,mi=l+r>>1; 57     for(i=1;i<=cnta;++i) 58         sum+=stacka[i]->ch[0]->size; 59     for(i=1;i<=cntb;++i) 60         sum-=stackb[i]->ch[0]->size; 61     if(sum>=k) 62     { 63         for(i=1;i<=cnta;++i)stacka[i]=stacka[i]->ch[0]; 64         for(i=1;i<=cntb;++i)stackb[i]=stackb[i]->ch[0]; 65         return get_ans(l,mi,k); 66     } 67     else 68     { 69         for(i=1;i<=cnta;++i)stacka[i]=stacka[i]->ch[1]; 70         for(i=1;i<=cntb;++i)stackb[i]=stackb[i]->ch[1]; 71         return get_ans(mi+1,r,k-sum); 72     } 73 } 74 #define alpha 0.755 75 struct Goat 76 { 77     Goat *ch[2];node *tree; 78     int size,val; 79     inline bool bad() 80         {
    return ch[0]->size>=size*alpha+5 ||ch[1]->size>=size*alpha+5;} 81     inline void update() 82         {size=ch[0]->size+1+ch[1]->size;} 83 }*root,*null,memGoat[(N<<2)+10],*poolGoat[(N<<2)+10],*stackc[(N<<2)+10]; 84 inline Goat** insert(Goat *&o,int pos,int val) 85 { 86     int to=(o->ch[0]->size+1 < pos)?1:0; 87     ++o->size,insert(o->tree,0,MAXN,val); 88     if(o->ch[to]==null) 89     { 90         o->ch[to]=poolGoat[topb--]; 91         o->ch[to]->ch[0]=o->ch[to]->ch[1]=null; 92         o->ch[to]->val=val; 93         o->ch[to]->size=1; 94         o->ch[to]->tree=NIL; 95         insert(o->ch[to]->tree,0,MAXN,val); 96         return &null; 97     } 98     Goat **ret=insert(o->ch[to],pos-(o->ch[0]->size+1)*to,val); 99     if(o->bad())ret=&o;100     return ret;101 }102 inline int change(Goat *o,int pos,int val)103 {104     insert(o->tree,0,MAXN,val);105     if(o->ch[0]->size+1==pos)106     {107         int ret=o->val;108         del(o->tree,0,MAXN,o->val),o->val=val;109         return ret;110     }111     int ret;112     if(o->ch[0]->size >= pos)ret=change(o->ch[0],pos,val);113     else ret=change(o->ch[1],pos-o->ch[0]->size-1,val);114     del(o->tree,0,MAXN,ret);return ret;115 }116 inline void get_l(Goat *o,int l)117 {118     if(o==null)return;119     if(o->ch[0]->size>=l)120     {121         stacka[++cnta]=o->tree,stackb[++cntb]=o->ch[0]->tree,122         get_l(o->ch[0],l);123     }124     else if(o->ch[0]->size+1==l)125     {126         stacka[++cnta]=o->tree,stackb[++cntb]=o->ch[0]->tree;127     }128     else129         get_l(o->ch[1],l-o->ch[0]->size-1);130 }131 inline void get_r(Goat *o,int r)132 {133     if(o==null)return;134     if(o->ch[0]->size>=r)135         get_r(o->ch[0],r);136     else if(o->ch[0]->size+1==r)137     {138         stacka[++cnta]=o->tree,stackb[++cntb]=o->ch[1]->tree;139     }140     else141     {142         stacka[++cnta]=o->tree,stackb[++cntb]=o->ch[1]->tree;143         get_r(o->ch[1],r-o->ch[0]->size-1);144     }145 }146 inline void dfs(Goat *o)147 {148     if(o==null)return;149     if(o->ch[0]!=null)dfs(o->ch[0]);150     stackc[++top]=o,dfs2(o->tree);151     if(o->ch[1]!=null)dfs(o->ch[1]);152 }153 inline void onboard(Goat *o,node *&x)154 {155     if(o==null)return;156     if(o->ch[0]!=null)onboard(o->ch[0],x);157     insert(x,0,MAXN,o->val);158     if(o->ch[1]!=null)onboard(o->ch[1],x);159 }160 inline Goat* build(int l,int r)161 {162     if(l>r)return null;163     int mi=l+r>>1;164     stackc[mi]->size=r-l+1;165     stackc[mi]->ch[0]=build(l,mi-1),stackc[mi]->ch[1]=build(mi+1,r);166     stackc[mi]->tree=pool[topa--];stackc[mi]->tree->size=0;167     stackc[mi]->tree->ch[0]=stackc[mi]->tree->ch[1]=NIL;168     onboard(stackc[mi]->ch[0],stackc[mi]->tree);169     onboard(stackc[mi]->ch[1],stackc[mi]->tree);170     insert(stackc[mi]->tree,0,MAXN,stackc[mi]->val);171     return stackc[mi];172 }173 inline void rebuild(Goat *&o)174 {175     top=0;dfs(o);176     o=build(1,top);177 }178 inline void intn()179 {180     NIL->ch[0]=NIL->ch[1]=NIL;NIL->size=0;181     null=new Goat();null->tree=NIL;182     null->size=null->val=0;183     null->ch[0]=null->ch[1]=null;184     topa=topb=0;185     for(topa=0;topa<(N<<8);++topa)186         pool[topa]=mem+topa,pool[topa]->size=0,187         pool[topa]->ch[0]=pool[topa]->ch[1]=NIL;188     for(topb=0;topb<(N<<2);++topb)189         poolGoat[topb]=memGoat+topb,poolGoat[topb]->size=0,190         poolGoat[topb]->ch[0]=poolGoat[topb]->ch[1]=null;191     topa=(N<<8)-1,topb=(N<<2)-1;192     for(int i=1;i<=n;++i)193         stackc[i]=poolGoat[topb--],stackc[i]->val=a[i];194     root=build(1,n);195 }196 int main()197 {198     register int i,j,q,ans=0,l,r,x;char opt;Goat **p7;199     n=read();for(i=1;i<=n;++i)a[i]=read();200     intn(),q=read();201     for(i=1;i<=q;++i)202     {203         opt=readc();204         switch(opt)205         {206             case 'Q':207                 l=read()^ans,r=read()^ans,x=read()^ans;208                 cnta=cntb=0,get_l(root,l),get_r(root,r);209                 stackb[++cntb]=root->tree;210                 printf("%d\n",(ans=get_ans(0,MAXN,x)) );211                 break;212             case 'M':213                 l=read()^ans,x=read()^ans;214                 change(root,l,x);215                 break;216             case 'I':217                 l=read()^ans,x=read()^ans;218                 p7=insert(root,l,x);219                 if(*p7!=null)rebuild(*p7);220                 break;221         }222     }223 }

BZOJ3065

bzoj3217 ALOEXT（替罪羊套Trie树，和上面类似）

（还没打……明天补坑）

*PS:替罪羊树的思想是很好的，这种重建的思想可以优化很多题目的复杂度。

四.树套树在DP题目中的运用

有一些DP题目的转移会涉及到多维的取值关系，因此我们可以用树套树处理这类题目

我们依然用一种数据结构维护一维，在最内层的数据结构中维护对应的DP有关变量。

当然CDQ也可以干这事啦！

这种类型的题目有：

bzoj4553 序列

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 using namespace std; 6 const int N=300000; 7 int n,m,bit[N+100],f[N+100]; 8 struct num{
    int val,maxv,minv;}x[N+100]; 9 struct cdq{
    int x,y,id;}a[N+100];10 inline int lowbit(int a){
    return a&(-a);}11 inline bool mt(const cdq &a,const cdq &b)12 {
    return (a.x==b.x)?a.id
          
           
            >1;32 cdq(l,mi);33 for(int i=l;i<=r;i++)34 {35 if(i<=mi)a[i].x=x[i].val,a[i].y=x[i].maxv;36 else a[i].x=x[i].minv,a[i].y=x[i].val;37 a[i].id=i;38 }39 sort(a+l,a+r+1,mt);40 for(int i=l;i<=r;i++)41 {42 if(a[i].id<=mi)add(a[i].y,f[a[i].id]);43 else f[a[i].id]=max(sum(a[i].y)+1,f[a[i].id]);44 }45 for(int i=l;i<=r;i++)add(a[i].y,0);46 cdq(mi+1,r);47 }48 int main()49 {50 scanf("%d%d",&n,&m);int u,v,ans=0;51 for(int i=1;i<=n;i++)52 scanf("%d",&x[i].val),x[i].minv=x[i].maxv=x[i].val;53 while(m--)54 {55 scanf("%d%d",&u,&v);56 x[u].maxv=max(x[u].maxv,v);57 x[u].minv=min(x[u].minv,v);58 }59 cdq(1,n);60 for(int i=1;i<=n;i++)ans=max(ans,f[i]);61 printf("%d\n",ans);62 }

CDQ打法

bzoj2244 拦截导弹

1 #include 
      
         2 #include 
       
          3 #include 
        
           4 #include 
         
            5 using namespace std;  6 const int N=50010;  7 int n,toth,totv,st[N],top,f[2][N];  8 struct node  9 { 10     int h,v,tim; 11     inline void read(){scanf("%d%d",&h,&v);} 12 }m[N]; 13 inline bool mt1(const node &a,const node &b) 14 { 15     if(a.v==b.v&&a.h==b.h)return a.tim
          
           b)b=bit[a],c=cnt[a]; 38         else if(bit[a]==b)c+=cnt[a]; 39         a-=lowbit(a); 40     } 41 } 42 inline void clear(int a) 43 { 44     while(a<=totv) 45     { 46         if(!bit[a])return; 47         bit[a]=0,cnt[a]=0.0,a+=lowbit(a); 48     } 49 } 50 inline void CDQ(int l,int r,int o) 51 { 52     if(l==r)return; 53     register int i,mi=l+r>>1; 54     CDQ(l,mi,o); 55     sort(m+l,m+r+1,mt1); 56     int x=0;double u=0.0; 57     for(i=l;i<=r;++i) 58     { 59         if(m[i].tim<=mi) 60             add(m[i].v,f[o][m[i].tim],g[o][m[i].tim]); 61         else  62         { 63             query(m[i].v,x,u); 64             if(x+1>f[o][m[i].tim]) 65                 f[o][m[i].tim]=x+1,g[o][m[i].tim]=u; 66             else if(x+1==f[o][m[i].tim]) 67                 g[o][m[i].tim]+=u; 68         } 69     } 70     for(i=l;i<=r;++i) 71         if(m[i].tim<=mi)clear(m[i].v); 72     sort(m+l,m+r+1,mt2); 73     CDQ(mi+1,r,o); 74 } 75 inline void intn() 76 { 77     register int i; 78     for(i=1;i<=n;++i)st[i]=m[i].h; 79     sort(st+1,st+n+1),toth=unique(st+1,st+n+1)-st-1; 80     for(i=1;i<=n;++i) 81         m[i].h=lower_bound(st+1,st+toth+1,m[i].h)-st; 82     for(i=1;i<=n;++i)st[i]=m[i].v; 83     sort(st+1,st+n+1),totv=unique(st+1,st+n+1)-st-1; 84     for(i=1;i<=n;++i) 85         m[i].v=lower_bound(st+1,st+totv+1,m[i].v)-st; 86 } 87 int main() 88 { 89     register int i,j;scanf("%d",&n); 90     for(i=n;i;--i)m[i].read(); 91     intn(); 92     for(i=1;i<=n;++i) 93         m[i].tim=i,f[0][i]=f[1][i]=g[0][i]=g[1][i]=1; 94     CDQ(1,n,0); 95     reverse(m+1,m+n+1); 96     for(i=1;i<=n;++i) 97         m[i].tim=i,m[i].h=toth-m[i].h+1,m[i].v=totv-m[i].v+1; 98     CDQ(1,n,1); 99     int maxn=0;double sum=0;100     for(i=1;i<=n;++i)101     {102         if(maxn