链接：https://www.lydsy.com/JudgeOnline/problem.php?id=3196
题面;
3196: Tyvj 1730 二逼平衡树
Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 6372 Solved: 2406
[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可能为负数
思路;
线段树套个Treap就完事了，ls写成了rs，找了一晚上的错，真实自闭
实现代码:
#include<bits/stdc++.h>
using namespace std;
#define ls t[x].ch[0]
#define rs t[x].ch[1]
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define mid int m = (l + r) >> 1
const int M = 1e5+;
const int inf = ;
int idx,n;
struct node{
int ch[],cnt,siz,val,rd;
}t[M*];
int root[M<<],a[M];
void up(int x){
t[x].siz = t[ls].siz + t[rs].siz+t[x].cnt;
} void rotate(int &x,int d){
int son = t[x].ch[d];
t[x].ch[d] = t[son].ch[d^];
t[son].ch[d^] = x; up(x); up(x=son);
} void ins(int &x,int val){
if(!x){
x = ++idx;
t[x].cnt = t[x].siz = ;
t[x].val = val,t[x].rd = rand();
return ;
}
t[x].siz ++;
if(t[x].val == val){
t[x].cnt++; return ;
}
int d = t[x].val < val; ins(t[x].ch[d],val);
if(t[x].rd > t[t[x].ch[d]].rd) rotate(x,d);
} void del(int &x,int val){
if(!x) return ;
if(t[x].val == val){
if(t[x].cnt > ){
t[x].cnt--,t[x].siz--;return ;
}
bool d = t[ls].rd > t[rs].rd;
if(ls == ||rs == ) x = ls+rs;
else rotate(x,d),del(x,val);
}
else t[x].siz--,del(t[x].ch[t[x].val<val],val);
up(x);
}
int rk(int x,int val){
if(!x) return ;
if(t[x].val == val) return t[ls].siz;
if(t[x].val > val) return rk(ls,val);
return rk(rs,val)+t[ls].siz + t[x].cnt;
} int pre(int x,int val){
if(!x) return -inf;
if(t[x].val >= val) return pre(ls,val);
return max(pre(rs,val),t[x].val);
} int nex(int x,int val){
if(!x) return inf;
if(t[x].val <= val) return nex(rs,val);
return min(nex(ls,val),t[x].val);
} void print(int x){
if(!x) return ;
print(ls);
printf("%d ",t[x].val);
print(rs);
} void update(int p,int l,int r,int rt){
ins(root[rt],a[p]);
if(l == r) return ;
mid;
if(p <= m) update(p,lson);
else update(p,rson);
} int get_rank(int L,int R,int c,int l,int r,int rt){
if(L <= l&&R >= r){
return rk(root[rt],c);
}
int ret = ;
mid;
if(L <= m) ret += get_rank(L,R,c,lson);
if(R > m) ret += get_rank(L,R,c,rson);
return ret;
} int get_val(int x,int y,int k){
int l = ,r = inf,ret ;
while(l < r){
mid;
int ans = get_rank(x,y,m,,n,)+;
if(ans <= k) {
ret = m;l = m+;
}
else r = m;
}
return ret;
} void change(int p,int c,int l,int r,int rt){
del(root[rt],a[p]);
ins(root[rt],c);
if(l == r) return ;
mid;
if(p <= m) change(p,c,lson);
else change(p,c,rson);
} int get_pre(int L,int R,int c,int l,int r,int rt){
if(L <= l&&R >= r){
return pre(root[rt],c);
}
mid;
int ret = -inf;
if(L <= m) ret = max(ret,get_pre(L,R,c,lson));
if(R > m) ret = max(ret,get_pre(L,R,c,rson));
return ret;
} int get_nex(int L,int R,int c,int l,int r,int rt){
if(L <= l&&R >= r){
return nex(root[rt],c);
}
mid;
int ret = inf;
if(L <= m) ret = min(ret,get_nex(L,R,c,lson));
if(R > m) ret = min(ret,get_nex(L,R,c,rson));
return ret;
} void ct(int l,int r,int rt){
cout<<"L R: "<<l<<" "<<r<<endl;
print(root[rt]); cout<<endl;
if( l == r) return ;
mid;
ct(lson); ct(rson);
} int main()
{
// freopen("D:\\1.txt","r",stdin);
//freopen("D:\\2.txt","w",stdout);
int m,op,x,y,z;
scanf("%d%d",&n,&m);
for(int i = ;i <= n;i ++){
scanf("%d",&a[i]);
update(i,,n,);
}
//ct(1,n,1);
while(m--){
scanf("%d",&op);
scanf("%d%d",&x,&y);
if(op!=) scanf("%d",&z);
if(op == )
printf("%d\n",get_rank(x,y,z,,n,)+);
else if(op == )
printf("%d\n",get_val(x,y,z));
else if(op == )
change(x,y,,n,),a[x]=y;
else if(op == )
printf("%d\n",get_pre(x,y,z,,n,));
else if(op==)
printf("%d\n",get_nex(x,y,z,,n,));
}
return ;
}