萌新怒码4k ，搞出来一份不开O2就会T的代码。

只会 fhq-treap ，所以就来了一发 线段树套 fhq-treap。

也就调了一个小时

一些注意点

• 调用 fhq-treap 时 root 要传址。
• 寻找排名为 k 的数的时候二分的 check 要 queryrk(k+1) ，因为 queryrk() 找的是小于 k 的数，而 check 的要求是小于等于 k 的数。

Code

#include<bits/stdc++.h>
#define N 100005
#define orz puts("orzwyy332623");//tiaoshi
#define ls(p) p<<1
#define rs(p) p<<1|1
using namespace std;

int read(){
    int x=0,w=1;
    char ch=getchar();
    while(ch>'9'||ch<'0'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x*w;
}

const int inf = 2147483647;
int n,m,cnt;
int a[N];

struct node{
	struct Tree{int l,r,key,val,siz;}tree[N*20];
	int insert(int x){
		tree[++cnt].val=x;tree[cnt].siz=1;tree[cnt].key=rand();
		return cnt;
	}
	void push_up(int p){tree[p].siz=tree[tree[p].l].siz+tree[tree[p].r].siz+1;}
	int merge(int x,int y){
		if(!x||!y) return x+y;
		if(tree[x].key<tree[y].key){
			tree[x].r=merge(tree[x].r,y);
			push_up(x); return x;
		}
		else{
			tree[y].l=merge(x,tree[y].l);
			push_up(y); return y;
		}
	}
	void split(int p,int k,int &x,int &y){
		if(!p){x=y=0;return ;}
		if(tree[p].val<=k)x=p,split(tree[p].r,k,tree[p].r,y);
		else y=p,split(tree[p].l,k,x,tree[p].l);
		push_up(p);
	}
	int kth(int p,int k){
		if(tree[tree[p].l].siz>=k) return kth(tree[p].l,k);
		else if(tree[tree[p].l].siz+1==k) return p;
		else return kth(tree[p].r,k-tree[tree[p].l].siz-1);
	}
	void add(int &root,int x){
		int a,b;
		split(root,x,a,b);
		root=merge(a,merge(insert(x),b));
	}
	void update(int &root,int k,int w){
		int a,b,c;
		split(root,k-1,a,b); split(b,k,b,c);
		b=merge(tree[b].l,tree[b].r);a=merge(a,merge(b,c)); 
		split(a,w,a,b);
		root=merge(a,merge(insert(w),b));
	}
	int queryrk(int &root,int k){
		int a,b;
		split(root,k-1,a,b);
		int x=tree[a].siz;
		root=merge(a,b); 
		return x;
	}
	int querypre(int &root,int k){
		int a,b;
		split(root,k-1,a,b);
		int x=tree[a].siz,y;
		if(x) y=tree[kth(a,tree[a].siz)].val;
		root=merge(a,b);
		if(x==0) return -inf;
		return y;
	}
	int querysuf(int &root,int k){
		int a,b;
		split(root,k,a,b);
		int x=tree[b].siz,y;
		if(x) y=tree[kth(b,1)].val;
		root=merge(a,b);
		if(x==0) return inf;
		return y;
	}
}fhq;

struct Segment{
	int root[N<<4];
	void build(int p,int l,int r){
		for(int i=l;i<=r;++i) fhq.add(root[p],a[i]);
		if(l==r) return ;
		int mid=(l+r)>>1;
		build(ls(p),l,mid);build(rs(p),mid+1,r);
	}
	void update(int p,int l,int r,int k,int w){
		fhq.update(root[p],a[k],w);
		if(l==r) return ;
		int mid=(l+r)>>1;
		if(mid>=k) update(ls(p),l,mid,k,w);
		else update(rs(p),mid+1,r,k,w);
	}
	int queryrk(int p,int l,int r,int k,int L,int R){
		int mid=(l+r)>>1;
		if(l>R||r<L) return 0;
		if(L<=l&&r<=R) return fhq.queryrk(root[p],k);
		else return queryrk(ls(p),l,mid,k,L,R)+queryrk(rs(p),mid+1,r,k,L,R);
	}
	int queryrk1(int L,int R,int k){
		int l=0,r=1e8,ans=0;
		while(l<=r){
			int mid=(l+r)>>1;
			if(queryrk(1,1,n,mid+1,L,R)>=k)ans=mid ,r=mid-1;
			else l=mid+1;
		}
		return ans;
	}
	int querypre(int p,int l,int r,int k,int L,int R){
		int mid=(l+r)>>1;
		if(l>R||r<L) return -inf;
		if(L<=l&&r<=R) return fhq.querypre(root[p],k);
		else return max(querypre(ls(p),l,mid,k,L,R),querypre(rs(p),mid+1,r,k,L,R));
	}
	int querysuf(int p,int l,int r,int k,int L,int R){
		int mid=(l+r)>>1;
		if(l>R||r<L) return inf;
		if(L<=l&&r<=R) return fhq.querysuf(root[p],k);
		else return min(querysuf(ls(p),l,mid,k,L,R),querysuf(rs(p),mid+1,r,k,L,R));
	}
}seg;

signed main(){
	n=read();m=read();
	for(int i=1;i<=n;++i) a[i]=read();
	seg.build(1,1,n);
	for(int i=1;i<=m;++i){
		int opt=read();
		if(opt==1) {
			int l=read(),r=read(),k=read();
			printf("%d\n",seg.queryrk(1,1,n,k,l,r)+1);
		}
		else if(opt==2){
			int l=read(),r=read(),k=read();
			printf("%d\n",seg.queryrk1(l,r,k));
		}
		else if(opt==3){
			int pos=read(),k=read(); 
			seg.update(1,1,n,pos,k);
			a[pos]=k;
		}
		else if(opt==4){
			int l=read(),r=read(),k=read();
			printf("%d\n",seg.querypre(1,1,n,k,l,r));
		}
		else {
			int l=read(),r=read(),k=read();
			printf("%d\n",seg.querysuf(1,1,n,k,l,r));
		}
	}
	return 0;
}