树套树


  Orz zyf

  学(co)习(py)了一下树套树的写法,嗯……就是线段树套平衡树。

  具体实现思路就是:外部查询用的都是线段树,查询内部自己调用平衡树的操作。

  抄抄代码有助理解= =

八中挂了……话说tyvj上最后两组ex数据好恶心……

 /**************************************************************
Problem: 3196
User: Tunix
Language: C++
Result: Accepted
Time:6240 ms
Memory:50692 kb
****************************************************************/ //BZOJ 3196
#include<cmath>
#include<vector>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
#define rep(i,n) for(int i=0;i<n;++i)
#define F(i,j,n) for(int i=j;i<=n;++i)
#define D(i,j,n) for(int i=j;i>=n;--i)
#define pb push_back
#define CC(a,b) memset(a,b,sizeof(a))
using namespace std;
int getint(){
int v=,sign=; char ch=getchar();
while(!isdigit(ch)) {if(ch=='-') sign=-; ch=getchar();}
while(isdigit(ch)) {v=v*+ch-''; ch=getchar();}
return v*sign;
}
const int N=,M=,INF=~0u>>;
const double eps=1e-;
/*******************template********************/ int n,m,tot,a[N],l[M],r[M],s[M],rnd[M],w[M],v[M];
#define L l[x]
#define R r[x]
struct tree{
int l,r,rt;
}t[*N];
inline void Push_up(int x){
s[x]=s[L]+s[R]+w[x];
}
inline void zig(int &x){
int t=L; L=r[t]; r[t]=x; s[t]=s[x]; Push_up(x); x=t;
}
inline void zag(int &x){
int t=R; R=l[t]; l[t]=x; s[t]=s[x]; Push_up(x); x=t;
}
void ins(int &x,int num){
if (!x){
x=++tot; v[x]=num; s[x]=w[x]=; L=R=; rnd[x]=rand(); return;
}
s[x]++;
if (v[x]==num) w[x]++;
else if(num<v[x]){
ins(L,num); if(rnd[L]<rnd[x]) zig(x);
}else{
ins(R,num); if(rnd[R]<rnd[x]) zag(x);
}
}
void del(int &x,int num){
if (v[x]==num){
if (w[x]>){w[x]--; s[x]--;}
else if(L*R==) x=L+R;
else if(rnd[L]<rnd[R]){
zig(x); del(x,num);
}else{
zag(x); del(x,num);
}
return;
}
s[x]--;
if (num<v[x]) del(L,num);
else del(R,num);
}
int rank(int x,int num){
if (!x) return ;
if (v[x]==num) return s[L];
else if(num<v[x]) return rank(L,num);
else return s[L]+w[x]+rank(R,num);
}
int pre(int x,int num){
if (!x) return -INF;
if (num<=v[x]) return pre(L,num);
else{
int t=pre(R,num);
return t==-INF? v[x] : t;
}
}
int suc(int x,int num){
if (!x) return INF;
if (num>=v[x]) return suc(R,num);
else{
int t=suc(L,num);
return t==INF?v[x]:t;
}
}
#undef L
#undef R
/******************Treap************************/
#define L (o<<1)
#define R (o<<1|1)
void build(int o,int x,int y){
int l=t[o].l=x,r=t[o].r=y,mid=l+r>>;
F(i,l,r) ins(t[o].rt,a[i]);
if (l==r) return;
build(L,l,mid); build(R,mid+,r);
}
void update(int o,int x,int y){//update a[x]=y
int l=t[o].l,r=t[o].r,mid=l+r>>;
del(t[o].rt,a[x]); ins(t[o].rt,y);
if (l==r) return;
if (x<=mid) update(L,x,y);
else update(R,x,y);
}
int query(int o,int x,int y,int k){
int l=t[o].l,r=t[o].r,mid=l+r>>;
if (l==x && r==y) return rank(t[o].rt,k);
if (y<=mid) return query(L,x,y,k);
else if (x>mid) return query(R,x,y,k);
else return (query(L,x,mid,k)+query(R,mid+,y,k));
}
int getpre(int o,int x,int y,int k){
int l=t[o].l,r=t[o].r,mid=l+r>>;
if (l==x && r==y) return pre(t[o].rt,k);
if (y<=mid) return getpre(L,x,y,k);
else if(x>mid) return getpre(R,x,y,k);
else return max(getpre(L,x,mid,k),getpre(R,mid+,y,k));
}
int getsuc(int o,int x,int y,int k){
int l=t[o].l,r=t[o].r,mid=l+r>>;
if (l==x && r==y) return suc(t[o].rt,k);
if (y<=mid) return getsuc(L,x,y,k);
else if(x>mid) return getsuc(R,x,y,k);
else return min(getsuc(L,x,mid,k),getsuc(R,mid+,y,k));
} int main(){
#ifndef ONLINE_JUDGE
freopen("input.txt","r",stdin);
// freopen("output.txt","w",stdout);
#endif
n=getint(); m=getint();
F(i,,n) a[i]=getint();
build(,,n);
int x,y,z,ch;
while(m--){
ch=getint();
if (ch==){ x=getint(); y=getint(); update(,x,y); a[x]=y;}
else{
x=getint(); y=getint(); z=getint();
if (ch==){
int l=,r=INF;
while(l<=r){
int mid=l+r>>;
if (query(,x,y,mid)+>z) r=mid-;
else l=mid+;
}
printf("%d\n",r);
}
if (ch==) printf("%d\n",query(,x,y,z)+);
if (ch==) printf("%d\n",getpre(,x,y,z));
if (ch==) printf("%d\n",getsuc(,x,y,z));
}
}
return ;
}
04-21 07:30
查看更多