BZOJ3065

本题是在BZOJ上的处女A，实在不应该拿这样一道题来开头

平衡树套线段树应该是树套树问题里比较难的一种了，当然我记得还有一个替罪羊树套Trie树的题，我是不信自己能写出来的。

外层的平衡树来实现区间值得插入和修改，其实如果外层的插入是只在中间插入的话，可以不用平衡树的

为了避免旋转对内层数据结构的影响，这里的外层平衡树是不能够旋转的，像这种外层平衡树的题，外层的树一般都是替罪羊树，像无旋Treap一般是用来实现可持久化平衡树的

总的来说，各种树有各种树的用途，我如果只是一道单纯的平衡树的题，就根本没有必要用裸的替罪羊树维护了是不是

下面我来完整地解析一下实现过程：

const int maxn=70005;const float alpha=0.75;int n,m,root,gtmp,sz,lastans;int v[maxn],dfn[maxn],rt[maxn],lch[maxn],rch[maxn];//rt是替罪羊节点存的每一个线段树的根节点 struct seg{
   int l,r,sum;}a[10000005];vector
     
       rec,t,p;
     

先来看声明部分，alpha是替罪羊平衡因子，记住如果是常数一定不要用int，会崩的

区间长度为n，m个询问，替罪羊树的根节点咱们叫root，gtmp是和重构子树有关的临时变量，sz是线段树节点个数，lastans是跟题目有关的一个变量

这里的替罪羊树是SOA，v是节点的值，dfn是节点的ID用来节省空间，rt是每一个替罪羊节点对应的权值线段树的根节点，lch和rch是替罪羊左右子树的ID

权值线段树是AOS，l存左子树ID，r存右子树ID，sum在这里就是子树的节点个数了，因为有这个sum在替罪羊树中的size就不必了

这里的权值线段树虽然是完全二叉树但是存的时候是存成数组链的，不支持完全二叉树的2n,2n+1的操作，其实主要原因是空间不够

rec用来存回收来的线段树节点，为了省空间，t是用来存替罪羊子树（或者说一个区间）所有的权值线段树节点，p用来存这个区间每一个节点的值

t和p是在查询的时候二分查询权值线段树的时候用的，因为这个线段树是用链存的，所以查询部分还是不太会，只是大概理解了个思路

void build(int &k,int l,int r){    //cout<<"###5"<
     
      r) return;    if(l==r)    {        k=dfn[l];        insert(rt[k],0,70000,v[k],1);  //在替罪羊树的叶子节点插入权值线段树         return;    }    int mid=(l+r)>>1;k=dfn[mid];    build(lch[k],l,mid-1);build(rch[k],mid+1,r);    for(int i=l;i<=r;i++) insert(rt[k],0,70000,v[dfn[i]],1); }
     

这是建树操作，建替罪羊树，在建的过程中每一个节点都插入了一个权值线段树，这个线段树是一个一个插出来的，其中insert的最后一个参数就是所谓的权值

然后我们立刻看一下权值线段树怎么建的

void insert(int &k,int l,int r,int val,int f)  //每一个替罪羊节点插入权值线段树 {    //cout<<"###4"<
     
      >1;    if(val<=mid) insert(a[k].l,l,mid,val,f);    else insert(a[k].r,mid+1,r,val,f);    a[k].sum=a[a[k].l].sum+a[a[k].r].sum;    if(a[k].sum==0) reclaim(k); }
     

可以很明显看出来是线段树递归建树了，如果插完之后发现没有权值，直接回收

inline int newnode(){    //cout<<"###2"<

向（回收站）申请一个线段树节点空间

看一下怎么拆掉没用的线段树的

void reclaim(int &k)  //回收叶子的线段树空间{    //cout<<"###3"<

查询就比较恶心了

void query(int k,int l,int r)  //提取出要查询的权值线段树?{    //cout<<"###8"<
     
      =L+1) p.push_back(v[k]);  //当前根节点在要查询的区间里     if(r<=L) query(lch[k],l,r);    else if(l>L+1) query(rch[k],l-L-1,r-L-1);    else    {        if(l<=L) query(lch[k],l,L);        if(R>L+1) query(rch[k],1,r-L-1);    }}int solve_query(int L,int R,int K) //二分权值线段树查询区间第k大 ?{    //cout<<"###9"<
      
       >1,sum=0;        for(int i=0;i
       
        =l&&p[i]<=mid) sum++;        if(K
       
      
     

上面那个查询是用来把替罪羊子树对应的权值线段树都翟出来的，底下这个函数就是二分这个翟出来的权值线段树然后二分求第k大的

说到这里我可能知道了多颗权值线段树能够维护静态第k大，或者说，线段树套权值线段树？一会儿去试试，感觉比这个要简单一些

接下来说修改

int modify(int k,int x,int val){    //cout<<"###8"<
     
      =x) t=modify(lch[k],x,val);    else t=modify(rch[k],x-L-1,val);    insert(rt[k],0,70000,t,-1);    return t; }
     

修改就是把从根节点到这个修改点所影响的所有线段树进行统一的，插新数，删旧数

最后就是迷之插入了

void insert(int &k,int x,int val){    //cout<<"###10"<
     
      =x) insert(lch[k],x,val);    else insert(rch[k],x-L-1,val);    if(a[rt[k]].sum*alpha>max(a[rt[lch[k]]].sum,a[rt[rch[k]]].sum))    {        if(gtmp)        {            if(lch[k]==gtmp) rebuild(lch[k]);            else rebuild(rch[k]);            gtmp=0;        }    }    else gtmp=k;}
     

这就是往平衡树里插东西了，插完之后通过权值线段树的sum来看有没有平衡啊，如果没有平衡的话，就重构把

重构的时候不是把替罪羊树变成完全二叉树就完了，还得把里面套的线段树维护好，这里的话

void del(int &k)  //回收替罪羊树 {    //cout<<"###6"<

线段树直接暴力插进去了，如果要是线段树合并的话，可能还要学一学了，线段树合并是O（logn）的

感谢黄学长

附完整代码：

1 #include
     
        2 #include
      
         3 #include
       
          4 #include
        
           5 using namespace std;  6 const int maxn=70005;  7 const float alpha=0.75;  8 int n,m,root,gtmp,sz,lastans;  9 int v[maxn],dfn[maxn],rt[maxn],lch[maxn],rch[maxn]; 10 //rt是替罪羊节点存的每一个线段树的根节点  11 struct seg{
   int l,r,sum;}a[10000005]; 12 vector
         
           rec,t,p; 13 inline int read() 14 { 15     //cout<<"###1"<
          
           '9') ch=getchar(); 19 while(ch>='0'&&ch<='9') {x=x*10+ch-'0';ch=getchar();} 20 return x; 21 } 22 inline int newnode() 23 { 24 //cout<<"###2"<
           
            >1; 47 if(val<=mid) insert(a[k].l,l,mid,val,f); 48 else insert(a[k].r,mid+1,r,val,f); 49 a[k].sum=a[a[k].l].sum+a[a[k].r].sum; 50 if(a[k].sum==0) reclaim(k); 51 } 52 void build(int &k,int l,int r) 53 { 54 //cout<<"###5"<
            
             r) return; 56 if(l==r) 57 { 58 k=dfn[l]; 59 insert(rt[k],0,70000,v[k],1); //在替罪羊树的叶子节点插入权值线段树 60 return; 61 } 62 int mid=(l+r)>>1;k=dfn[mid]; 63 build(lch[k],l,mid-1);build(rch[k],mid+1,r); 64 for(int i=l;i<=r;i++) insert(rt[k],0,70000,v[dfn[i]],1); 65 } 66 void del(int &k) //回收替罪羊树 67 { 68 //cout<<"###6"<
             
              =x) t=modify(lch[k],x,val); 90 else t=modify(rch[k],x-L-1,val); 91 insert(rt[k],0,70000,t,-1); 92 return t; 93 } 94 void query(int k,int l,int r) //提取出要查询的权值线段树? 95 { 96 //cout<<"###8"<
              
               =L+1) p.push_back(v[k]); //当前根节点在要查询的区间里 100 if(r<=L) query(lch[k],l,r);101 else if(l>L+1) query(rch[k],l-L-1,r-L-1);102 else103 {104 if(l<=L) query(lch[k],l,L);105 if(R>L+1) query(rch[k],1,r-L-1);106 }107 }108 int solve_query(int L,int R,int K) //二分权值线段树查询区间第k大 ?109 {110 //cout<<"###9"<
               
                >1,sum=0;116 for(int i=0;i
                
                 =l&&p[i]<=mid) sum++;119 if(K
                 
                  =x) insert(lch[k],x,val);146 else insert(rch[k],x-L-1,val);147 if(a[rt[k]].sum*alpha>max(a[rt[lch[k]]].sum,a[rt[rch[k]]].sum))148 {149 if(gtmp)150 {151 if(lch[k]==gtmp) rebuild(lch[k]);152 else rebuild(rch[k]);153 gtmp=0;154 }155 }156 else gtmp=k;157 }158 int main()159 {160 n=read();161 for(int i=1;i<=n;i++) v[i]=read();162 for(int i=1;i<=n;i++) dfn[i]=i;163 build(root,1,n);164 m=read();165 int x,y,k;166 char tmp[5];167 while(m--)168 {169 scanf("%s",tmp);170 x=read();y=read();x^=lastans;y^=lastans;171 switch(tmp[0])172 {173 case 'Q':k=read();k^=lastans;lastans=solve_query(x,y,k);printf("%d\n",lastans);break;174 case 'M':modify(root,x,y);break;175 case 'I':gtmp=0;insert(root,x-1,y);176 if(gtmp) {gtmp=0;rebuild(root);}177 break;178 }179 }180 return 0;181 }