树套树
Orz zyf
学(co)习(py)了一下树套树的写法，嗯……就是线段树套平衡树。
具体实现思路就是：外部查询用的都是线段树，查询内部自己调用平衡树的操作。
抄抄代码有助理解= =
八中挂了……话说tyvj上最后两组ex数据好恶心……
1 /************************************************************** 2 Problem: 3196 3 User: Tunix 4 Language: C++ 5 Result: Accepted 6 Time:6240 ms 7 Memory:50692 kb 8 ****************************************************************/ 9 10 //BZOJ 3196 11 #include<cmath> 12 #include<vector> 13 #include<cstdio> 14 #include<cstring> 15 #include<cstdlib> 16 #include<iostream> 17 #include<algorithm> 18 #define rep(i,n) for(int i=0;i<n;++i) 19 #define F(i,j,n) for(int i=j;i<=n;++i) 20 #define D(i,j,n) for(int i=j;i>=n;--i) 21 #define pb push_back 22 #define CC(a,b) memset(a,b,sizeof(a)) 23 using namespace std; 24 int getint(){ 25 int v=0,sign=1; char ch=getchar(); 26 while(!isdigit(ch)) {if(ch=='-') sign=-1; ch=getchar();} 27 while(isdigit(ch)) {v=v*10+ch-'0'; ch=getchar();} 28 return v*sign; 29 } 30 const int N=50010,M=2000000,INF=~0u>>2; 31 const double eps=1e-8; 32 /*******************template********************/ 33 34 int n,m,tot,a[N],l[M],r[M],s[M],rnd[M],w[M],v[M]; 35 #define L l[x] 36 #define R r[x] 37 struct tree{ 38 int l,r,rt; 39 }t[4*N]; 40 inline void Push_up(int x){ 41 s[x]=s[L]+s[R]+w[x]; 42 } 43 inline void zig(int &x){ 44 int t=L; L=r[t]; r[t]=x; s[t]=s[x]; Push_up(x); x=t; 45 } 46 inline void zag(int &x){ 47 int t=R; R=l[t]; l[t]=x; s[t]=s[x]; Push_up(x); x=t; 48 } 49 void ins(int &x,int num){ 50 if (!x){ 51 x=++tot; v[x]=num; s[x]=w[x]=1; L=R=0; rnd[x]=rand(); return; 52 } 53 s[x]++; 54 if (v[x]==num) w[x]++; 55 else if(num<v[x]){ 56 ins(L,num); if(rnd[L]<rnd[x]) zig(x); 57 }else{ 58 ins(R,num); if(rnd[R]<rnd[x]) zag(x); 59 } 60 } 61 void del(int &x,int num){ 62 if (v[x]==num){ 63 if (w[x]>1){w[x]--; s[x]--;} 64 else if(L*R==0) x=L+R; 65 else if(rnd[L]<rnd[R]){ 66 zig(x); del(x,num); 67 }else{ 68 zag(x); del(x,num); 69 } 70 return; 71 } 72 s[x]--; 73 if (num<v[x]) del(L,num); 74 else del(R,num); 75 } 76 int rank(int x,int num){ 77 if (!x) return 0; 78 if (v[x]==num) return s[L]; 79 else if(num<v[x]) return rank(L,num); 80 else return s[L]+w[x]+rank(R,num); 81 } 82 int pre(int x,int num){ 83 if (!x) return -INF; 84 if (num<=v[x]) return pre(L,num); 85 else{ 86 int t=pre(R,num); 87 return t==-INF? v[x] : t; 88 } 89 } 90 int suc(int x,int num){ 91 if (!x) return INF; 92 if (num>=v[x]) return suc(R,num); 93 else{ 94 int t=suc(L,num); 95 return t==INF?v[x]:t; 96 } 97 } 98 #undef L 99 #undef R 100 /******************Treap************************/ 101 #define L (o<<1) 102 #define R (o<<1|1) 103 void build(int o,int x,int y){ 104 int l=t[o].l=x,r=t[o].r=y,mid=l+r>>1; 105 F(i,l,r) ins(t[o].rt,a[i]); 106 if (l==r) return; 107 build(L,l,mid); build(R,mid+1,r); 108 } 109 void update(int o,int x,int y){//update a[x]=y 110 int l=t[o].l,r=t[o].r,mid=l+r>>1; 111 del(t[o].rt,a[x]); ins(t[o].rt,y); 112 if (l==r) return; 113 if (x<=mid) update(L,x,y); 114 else update(R,x,y); 115 } 116 int query(int o,int x,int y,int k){ 117 int l=t[o].l,r=t[o].r,mid=l+r>>1; 118 if (l==x && r==y) return rank(t[o].rt,k); 119 if (y<=mid) return query(L,x,y,k); 120 else if (x>mid) return query(R,x,y,k); 121 else return (query(L,x,mid,k)+query(R,mid+1,y,k)); 122 } 123 int getpre(int o,int x,int y,int k){ 124 int l=t[o].l,r=t[o].r,mid=l+r>>1; 125 if (l==x && r==y) return pre(t[o].rt,k); 126 if (y<=mid) return getpre(L,x,y,k); 127 else if(x>mid) return getpre(R,x,y,k); 128 else return max(getpre(L,x,mid,k),getpre(R,mid+1,y,k)); 129 } 130 int getsuc(int o,int x,int y,int k){ 131 int l=t[o].l,r=t[o].r,mid=l+r>>1; 132 if (l==x && r==y) return suc(t[o].rt,k); 133 if (y<=mid) return getsuc(L,x,y,k); 134 else if(x>mid) return getsuc(R,x,y,k); 135 else return min(getsuc(L,x,mid,k),getsuc(R,mid+1,y,k)); 136 } 137 138 int main(){ 139 #ifndef ONLINE_JUDGE 140 freopen("input.txt","r",stdin); 141 // freopen("output.txt","w",stdout); 142 #endif 143 n=getint(); m=getint(); 144 F(i,1,n) a[i]=getint(); 145 build(1,1,n); 146 int x,y,z,ch; 147 while(m--){ 148 ch=getint(); 149 if (ch==3){ x=getint(); y=getint(); update(1,x,y); a[x]=y;} 150 else{ 151 x=getint(); y=getint(); z=getint(); 152 if (ch==2){ 153 int l=0,r=INF; 154 while(l<=r){ 155 int mid=l+r>>1; 156 if (query(1,x,y,mid)+1>z) r=mid-1; 157 else l=mid+1; 158 } 159 printf("%d ",r); 160 } 161 if (ch==1) printf("%d ",query(1,x,y,z)+1); 162 if (ch==4) printf("%d ",getpre(1,x,y,z)); 163 if (ch==5) printf("%d ",getsuc(1,x,y,z)); 164 } 165 } 166 return 0; 167 }