二逼平衡树的zkw线段树套vector实现
这可能是最容易想和读的做法（重点是不用思考太多，很好调）。
前置知识是vector实现的平衡树和zkw线段树，以及一点点的结构体知识。
先看题目要求：
- 查询k在区间内的排名
- 查询区间内排名为k的值
- 修改某一位值上的数值
- 查询k在区间内的前驱
- 查询k在区间内的后继
发现,欸,这不就是P3369，套了个区间操作吗！
vector 实现的 Treap，我们就叫他 vreap 好了，它能实现什么操作?
它可以实现所有区间的1-5操作。
现在是部分区间的，那就在上面套个线段树（树状数组也行，但我不想打，会吐）。
考虑到全程的修改只有一个3，还是单点修改，果断zkw！
建树的过程就一路maintain，父亲=俩儿子合并起来
void sum(vreap a,vreap b){//定义在结构体中
clear();
vi ai,bi;
ai=a.begin(),bi=b.begin();
while(ai!=a.end()&&bi!=b.end()){
if(*ai<=*bi) push_back(*ai),++ai;
else push_back(*bi),++bi;
}
while(ai!=a.end()) push_back(*ai),++ai;
while(bi!=b.end()) push_back(*bi),++bi;
}先实现1操作，就在沿途区间上查这个数字的rank，累加，加一。
int rank(int s,int t,int x){
int ans=0;
for(s=m+s-1,t=m+t+1;s!=brother(t);s>>=1,t>>=1){
if(isleft(s)) ans+=tree[brother(s)].rank(x)-1;
if(isright(t)) ans+=tree[brother(t)].rank(x)-1;
}
return ans+1;
}然后2，考虑二分，然后对每个mid进行rank，比较。
int ask(int s,int t,int i){
int ans=0,l=0,r=BIG,mid;
while(l<r){
mid=((l+r)>>1)+1;
if(rank(s,t,mid)>i){//就是硬扫,找一个数的排名和给的比较
r=mid-1;
}else l=mid;//我实在不会写二分
}
return l;
}但3操作时，本来我用的是一路maintain上去，果不其然超时了。
借鉴@λᴉʍ大佬的思路，先删除，再重新插入，这样就不会爆了。
void change(int x,int v){
int yuan=tree[x=x+m][0];
int xyuan=x;//蜜汁命名规则
tree[x][0]=v;
while(x=father(x)) tree[x].shanchu(yuan);
x=xyuan;
while(x=father(x)) tree[x].push(v);
}4，5一个意思，max/min一下沿途每个vreap的pre/next
就写完了呗。速度还可以，没开o2 3.49s,开了792ms
最后把树封装一下，变得简洁一点
#include<bits/stdc++.h>
using namespace std;
#define maxn 50001
#define BIG 123456789
#define fu(i,l,r) for(int i=l;i<=r;i++)//个人习惯
#define fd(i,l,r) for(int i=l;i>=r;i--)
#define out(x) printf("%d\n",x)//个人习惯
int n,m;
inline int read(){
char x; int a=0; bool w=0; x=getchar();
while(x<'0'||x>'9')
{ if(x=='-') w=1; x=getchar(); }
while(x>='0'&&x<='9')
{ a=a*10+x-'0'; x=getchar(); }
return w?-a:a; }
struct vreap:vector<int>{//平衡树：vreap=vector+heap 继承vecotr：好写
#define vi vector<int>::iterator
#define erfind(x) lower_bound(begin(),end(),x)
void print(){
for(vi i=begin();i!=end();++i) printf("%d ",*i);
}//带一个输出会带来意想不到的好处
int rank(int x){
vi i=erfind(x);
return i-begin()+1;
}
void push(int x){
insert(erfind(x),x);
}
int previ(int x){
vi i=erfind(x);
if(i==begin()) return -2147483647;
--i;
return *i;
}
int nexti(int x){
vi i=erfind(x+1);
if(i==end()) return 2147483647;
return *i;
}
vi find(int x){
return erfind(x);
}
void sum(vreap a,vreap b){
clear();
vi ai,bi;
ai=a.begin(),bi=b.begin();
while(ai!=a.end()&&bi!=b.end()){
if(*ai<=*bi) push_back(*ai),++ai;
else push_back(*bi),++bi;
}
while(ai!=a.end()) push_back(*ai),++ai;
while(bi!=b.end()) push_back(*bi),++bi;
}
void shanchu(int x){//为什么不是erase呢？因为vector本身就有不能用
erase(find(x));
}
};
class Tree{//zkw线段树,封装成class或许更舒服?
private:
#define lson(x) (x<<1)//zkw树的一些好认的define,加括号有助于身心健康
#define rson(x) (x<<1|1)
#define father(x) (x>>1)
#define brother(x) (x^1)
#define isleft(x) (~x&1)//zkw树的一些好认的define,不用记
#define isright(x) (x&1)
#define INF 2147483647
int m,size;
inline int readi(){
char x; int a=0; bool w=0; x=getchar();
while(x<'0'||x>'9')
{ if(x=='-') w=1; x=getchar(); }
while(x>='0'&&x<='9')
{ a=a*10+x-'0'; x=getchar(); }
return w?-a:a; }
public:
vreap tree[maxn<<2];
void print(int root=1,int blk=0){ //打印树,方便调试
if (root <m) print(lson(root), blk + 1);//是叶节点
if(tree[root].size()){
for (int i = 0; i < blk; i++) printf(" ");
printf("|—<"); tree[root].print(); cout<<">\n";
}
if (root <m) print(rson(root), blk + 1);
}
void maintain(int fa){
tree[fa].sum(tree[lson(fa)],tree[rson(fa)]);//当然也可以从下往上插入,但是或许用归并的方法更快??
}
void build(int n){
for(m=1;m<=n;m<<=1);
for(int i=m+1;i<=m+n;i++){
tree[i].push_back(readi());
}
for(int i=m;i;i--) maintain(i);
}
void change(int x,int v){
int yuan=tree[x=x+m][0];
int xyuan=x;//蜜汁命名规则
tree[x][0]=v;
while(x=father(x)) tree[x].shanchu(yuan);
x=xyuan;
while(x=father(x)) tree[x].push(v);
}
int previ(int s,int t,int x){//前驱
int ans=-INF;
for(s=m+s-1,t=m+t+1;s!=brother(t);s>>=1,t>>=1){
if(isleft(s)) ans=max(ans,tree[brother(s)].previ(x));
if(isright(t)) ans=max(ans,tree[brother(t)].previ(x));
}
return ans;
}
int nexti(int s,int t,int x){//后继
int ans=INF;
for(s=m+s-1,t=m+t+1;s!=brother(t);s>>=1,t>>=1){
if(isleft(s)) ans=min(ans,tree[brother(s)].nexti(x));
if(isright(t)) ans=min(ans,tree[brother(t)].nexti(x));
}
return ans;
}
int rank(int s,int t,int x){
int ans=0;
for(s=m+s-1,t=m+t+1;s!=brother(t);s>>=1,t>>=1){
if(isleft(s)) ans+=tree[brother(s)].rank(x)-1;
if(isright(t)) ans+=tree[brother(t)].rank(x)-1;
}
return ans+1;
}
int ask(int s,int t,int i){
int ans=0,l=0,r=BIG,mid;
while(l<r){
mid=((l+r)>>1)+1;
if(rank(s,t,mid)>i){//就是硬扫,找一个数的排名和给的比较
r=mid-1;
}else l=mid;//我实在不会写二分
}
return l;
}
}tr;
int main()
{
cin>>n>>m;
tr.build(n);
int x,c,l,r,pos;
fu(i,1,m){
c=read();
if(c!=3){
l=read();r=read();x=read();
}else pos=read(),x=read();
switch(c){//很明了的读入/输出
case 1:
out(tr.rank(l,r,x));//封装的好处就是很好读
break;
case 2:
out(tr.ask(l,r,x));
break;
case 3:
tr.change(pos,x);
break;
case 4:
out(tr.previ(l,r,x));
break;
case 5:
out(tr.nexti(l,r,x));
break;
}
}
}