地址：http://www.lydsy.com/JudgeOnline/problem.php?id=3196
题目：
3196: Tyvj 1730 二逼平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 4320 Solved: 1662
[Submit][Status][Discuss]
Description
您需要写一种数据结构（可参考题目标题），来维护一个有序数列，其中需要提供以下操作：
1.查询k在区间内的排名
2.查询区间内排名为k的值
3.修改某一位值上的数值
4.查询k在区间内的前驱(前驱定义为小于x，且最大的数)
5.查询k在区间内的后继(后继定义为大于x，且最小的数)
Input
第一行两个数 n,m 表示长度为n的有序序列和m个操作
第二行有n个数，表示有序序列
下面有m行，opt表示操作标号
若opt=1 则为操作1，之后有三个数l,r,k 表示查询k在区间[l,r]的排名
若opt=2 则为操作2，之后有三个数l,r,k 表示查询区间[l,r]内排名为k的数
若opt=3 则为操作3，之后有两个数pos,k 表示将pos位置的数修改为k
若opt=4 则为操作4，之后有三个数l,r,k 表示查询区间[l,r]内k的前驱
若opt=5 则为操作5，之后有三个数l,r,k 表示查询区间[l,r]内k的后继
Output
对于操作1,2,4,5各输出一行，表示查询结果
Sample Input
9 6
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5
4 2 2 1 9 4 0 1 1
2 1 4 3
3 4 10
2 1 4 3
1 2 5 9
4 3 9 5
5 2 8 5
Sample Output
2
4
3
4
9
4
3
4
9
HINT
1.n和m的数据范围：n,m<=50000
2.序列中每个数的数据范围：[0,1e8]
3.虽然原题没有，但事实上5操作的k可能为负数
思路：
第一次写树套树，以前一直觉得树套树是很可怕的东西，写了后发现思想很简单
就是。。。。代码好长！debug麻烦！
写了两小时，debug三小时。。
不过1A了，美滋滋！
代码跑了快九秒，好气哦，一定是姿势不对
/**************************************************************
Problem: 3196
User: weeping
Language: C++
Result: Accepted
Time:8668 ms
Memory:83520 kb
****************************************************************/ #include <bits/stdc++.h> using namespace std; #define lc ch[x][0]
#define rc ch[x][1]
#define pr fa[x] inline int read()
{
int a=,f=; char c=getchar();
while (c<''||c>'') {if (c=='-') f=-; c=getchar();}
while (c>=''&&c<='') {a=a*+c-''; c=getchar();}
return a*f;
} const int N = 5e4+;
const int M = 3e6; int n, m, ans, val[N];
int tot, rt[M], ch[M][], fa[M], key[M], sz[M], cnt[M]; inline int wh(int x) { return ch[pr][] == x;} inline void init(int x,int ls,int ky)
{
lc=rc=,sz[x]=cnt[x]=,key[x]=ky,pr=ls;
}
inline void push_up(int x)
{
sz[x]=sz[lc]+sz[rc]+cnt[x];
}
void rotate(int x)
{
int f = fa[x], gf = fa[f], t1 = wh(x);
if( gf ) ch[gf][wh(f)] = x;
fa[x] = gf, ch[f][t1] = ch[x][^t1], fa[ch[f][t1]] = f;
ch[x][t1^] = f, fa[f] = x;
push_up( f ), push_up( x );
}
void splay(int o,int x,int tar)
{
for(;pr!=tar;rotate(x))
if(fa[pr]!=tar) rotate(wh(x)==wh(pr)?pr:x);
if(!tar) rt[o]=x;
}
//void debug(int x)
//{
// if(!x) return;
// if(lc) debug(lc);
// for(int i=1;i<=cnt[x];i++)
// printf("%d ",key[x]);
// if(rc) debug(rc);
//}
void insert(int o,int ky)
{
int x=rt[o],ls=rt[o];
while(x)
{
if(key[x]==ky)
{
sz[x]++,cnt[x]++,splay(o,x,);return;
}
ls=x,x=ch[x][ky>key[x]];
}
init(++tot,ls,ky);
if(!rt[o]) { rt[o]=tot; return ;}
x=ls, ch[x][ky>key[x]]=tot;
splay(o,tot,);
}
int find(int o,int ky)
{
int x=rt[o];
//debug(rt[o]);printf("\n");
while(x)
{
if(key[x]==ky) break;
x=ch[x][ky>key[x]];
}
if(x) splay(o,x,);
else x=-;
return x;
}
void merge(int o,int x,int y)
{
if(!x){rt[o]=y;return;}
if(!y) {rt[o]=x;return;}
while(rc) x=rc;
splay(o,x,);
rc=y,fa[y]=x;
push_up(x);
}
void del(int o,int ky)
{
if(!rt[o]) return;
int x=find(o,ky);
if(cnt[x]>) {cnt[x]--,sz[x]--;return;}
int tl=lc,tr=rc;
fa[tl]=fa[tr]=cnt[x]=sz[x]=lc=rc=;
if(sz[x]==) {rt[o]=;return;}
merge(o,tl,tr);
}
void getpre(int x,int ky)
{
if(!x)return;
if(key[x]<ky) ans=max(ans,key[x]),getpre(rc,ky);
else getpre(lc,ky);
}
void getnext(int x,int ky)
{
if(!x) return;
if(key[x]>ky) ans=min(ans,key[x]),getnext(lc,ky);
else getnext(rc,ky);
}
int getsz(int o,int ky)
{
int x=rt[o],ret=;
while(x)
{
if(key[x]==ky) return ret+sz[lc];
if(key[x]<ky) ret+=sz[lc]+cnt[x],x=rc;
else x=lc;
}
return ret;
} void update(int o,int l,int r,int pos,int x,int op=)
{
if(op) del(o,val[pos]);
insert(o,x);
//debug(rt[o]);printf("\n");
if(l==r) return ;
int mid=l+r>>;
if(pos<=mid) update(o<<,l,mid,pos,x,op);
else update(o<<|,mid+,r,pos,x,op);
}
int get_rank(int o,int l,int r,int nl,int nr,int ky)
{
//debug(rt[o]);printf("\n");
if(nl==l&&r==nr) return getsz(o,ky);
int mid=l+r>>;
if(nr<=mid) return get_rank(o<<,l,mid,nl,nr,ky);
else if(nl>mid) return get_rank(o<<|,mid+,r,nl,nr,ky);
return get_rank(o<<,l,mid,nl,mid,ky)+get_rank(o<<|,mid+,r,mid+,nr,ky);
}
void get_pre(int o,int l,int r,int nl,int nr,int ky)
{
if(nl==l&&r==nr) return getpre(rt[o],ky);
int mid=l+r>>;
if(nr<=mid) return get_pre(o<<,l,mid,nl,nr,ky);
else if(nl>mid) return get_pre(o<<|,mid+,r,nl,nr,ky);
get_pre(o<<,l,mid,nl,mid,ky),get_pre(o<<|,mid+,r,mid+,nr,ky);
}
void get_next(int o,int l,int r,int nl,int nr,int ky)
{
//debug(rt[o]);printf("\n");
if(nl==l&&r==nr) return getnext(rt[o],ky);
int mid=l+r>>;
if(nr<=mid) return get_next(o<<,l,mid,nl,nr,ky);
else if(nl>mid) return get_next(o<<|,mid+,r,nl,nr,ky);
get_next(o<<,l,mid,nl,mid,ky),get_next(o<<|,mid+,r,mid+,nr,ky);
}
int get_kth(int nl,int nr,int k)
{
int l=,r=1e8+,ans=;
while(l<=r)
{
int mid=l+r>>;
if(get_rank(,,n,nl,nr,mid)+<=k) l=mid+,ans=mid;
else r=mid-;
}
return ans;
}
int main(void)
{
n=read(),m=read();
for(int i=;i<=n;i++)
val[i]=read(),update(,,n,i,val[i]);
int op,l,r,x;
while(m--)
{
op=read(),l=read(),r=read();
if(op==)
{update(,,n,l,r,);val[l]=r;continue;}
x=read();
if(op==)
ans=get_rank(,,n,l,r,x)+;
else if(op==)
ans=get_kth(l,r,x);
else if(op==)
ans=-0x3f3f3f3f,get_pre(,,n,l,r,x);
else
ans=0x3f3f3f3f,get_next(,,n,l,r,x);
printf("%d\n",ans);
}
}