刚了一天的题终于切掉了,数据结构题的代码真**难调,这是我做过的第一道树套树题,做完后感觉对树套树都有阴影了......下面写一下做题记录.

　　Portal Gun:.

　　这道题的题面其实都提醒怎么做了,维护区间k小值用值域线段树,但要维护一个插入操作,树状数组套主席树也用不了,那么这道题还剩下平衡树可以搞,那就上平衡树吧.

　　我这里的做法,因为要维护序列的顺序,所以我这里用到替罪羊树套值域线段树:我们在替罪羊树的每个节点都套一颗值域线段树,记录以该节点为根的子树的值域的 size ,替罪羊树中我们维护每一个数在数列中的序号,在插入一个数时,就用它的值去更新插入时经过的所有点,就可以完成插入操作.至于修改操作,其实也就是插入操作,新值 size++ ,旧值 size-- .

　　关于复杂度:对于每次插入,替罪羊树是 O(logn) ,插入值域线段树是 O(logn) ,复杂度为 O(log^2) .对于每次查询,替罪羊树找区间是 O(logn) , 查询值域线段树是 O(logn) ,复杂度为 O(log^2) ,替罪羊树重构复杂度均摊为 O(log^2) .

　　

#include
     
      #include
      
       #include
       
        #define maxn (70005)#define al 0.75#define il inline#define RG registerusing namespace std;il int gi(){ RG int x=0,q=1; RG char ch=getchar(); while( ( ch<'0' || ch>'9' ) && ch!='-' ) ch=getchar();  if( ch=='-' ) q=-1,ch=getchar(); while(ch>='0' && ch<='9') x=x*10+ch-48,ch=getchar(); return q*x; }struct node{int l,r,size;}t[maxn*200];//值域线段树int n,m,ans,flag,root,cnt,Max=70000;int id[maxn],w[maxn],rt[maxn],ls[maxn],rs[maxn]; //替罪羊树int sta[maxn*100],top;  //存回收节点il int newnode(){ if(!top) return ++cnt; else return sta[top--]; }il bool BALANCE(int x){  return t[ rt[x] ].size*al>t[ rt[ls[x]] ].size    && t[ rt[x] ].size*al>t[ rt[rs[x]] ].size;}il void recycle(int &x){  if(!x) return ; sta[++top]=x;  recycle(t[x].l),recycle(t[x].r);  t[x].size=0,x=0;}il void insert(RG int &x,RG int l,RG int r,RG int val,RG int sum){ //线段树插入  if(!x) x=newnode();  if(l==r){ t[x].size+=sum; return ; }  RG int mid=(l+r)>>1;  if(val<=mid) insert( t[x].l,l,mid,val,sum );  else insert( t[x].r,mid+1,r,val,sum );  t[x].size=t[ t[x].l ].size+t[ t[x].r ].size;  if(!t[x].size) recycle(x);}il void build(RG int &x,RG int l,RG int r){  if(l>r) return ;  if(l==r){ x=id[l]; insert(rt[x],0,Max,w[x],1); return ; }  RG int mid=(l+r)>>1; x=id[mid];  build(ls[x],l,mid-1); build(rs[x],mid+1,r);  for(RG int i=l;i<=r;i++) insert(rt[x],0,Max,w[id[i]],1);}int cur[maxn*100],c_size;il void dfs(RG int &x){  if(!x) return ; recycle(rt[x]);  dfs(ls[x]); cur[++c_size]=x; dfs(rs[x]);  x=0;}il void REBUILD(int &x){  dfs(x);  for(RG int i=1;i<=c_size;i++) id[i]=cur[i];  build(x,1,c_size); c_size=0;}il void INSERT(RG int &x,RG int l,RG int val){  if(!x){      x=++n; w[x]=val;    insert(rt[x],0,Max,val,1);    return ;  }  insert( rt[x],0,Max,val,1 );  int L=t[ rt[ ls[x] ] ].size;  if(l<=L) INSERT(ls[x],l,val);  else INSERT(rs[x],l-L-1,val);  if(BALANCE(x)){ if(flag){      if(ls[x]==flag) REBUILD(ls[x]);      else REBUILD(rs[x]); flag=0;    }  }  else{ flag=x; if(flag==root) REBUILD(root); }}il int modify(RG int x,RG int l,RG int val){  insert(rt[x],0,Max,val,1);  //插入新值  int tt,L=t[ rt[ls[x]] ].size;  if(l==L+1){ tt=w[x]; w[x]=val; }  else if(l<=L) tt=modify(ls[x],l,val);  else tt=modify(rs[x],l-L-1,val);  insert(rt[x],0,Max,tt,-1);  //删除原值  return tt;}int tt[maxn*100],t_size,v[maxn*100],v_size;il void query(int k,int l,int r){  int L=t[ rt[ ls[k] ] ].size,R=t[ rt[k] ].size;  if(l==1 && r==R){ tt[++t_size]=rt[k]; return ; }  if(l<=L+1 && r>=L+1) v[++v_size]=w[k];  if(r<=L) query(ls[k],l,r);  else if(l>L+1) query(rs[k],l-L-1,r-L-1);  else{    if(l<=L) query(ls[k],l,L);    if(R>L+1) query(rs[k],1,r-L-1);  }}il int QUERY(int L,int R,int k){  query(root,L,R); k--;  int l=0,r=Max;  while(l
        
         >1,sum=0;    for(RG int i=1;i<=t_size;i++) sum+=t[ t[ tt[i] ].l ].size;    for(RG int i=1;i<=v_size;i++) if(v[i]>=l && v[i]<=mid) sum++;    if(k