http://www.lydsy.com/JudgeOnline/problem.php?id=3196
线段树套treap，似乎splay也可以但是抄的hzwer学长的代码。。就写了treap，算是比较需要注意细节的题。需要注意的地方都在注释里。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#include<cctype>
using namespace std;
#define lc 2*x
#define rc 2*x+1
const int maxn=;
const int inf=;
int n,m;
int root[maxn*];
struct tre{
int v,ls,rs,w;
int rd,siz;
}t[maxn*];
struct seg{
int l,r,mid;
}e[maxn*];
int a[maxn]={},tot=,ans;
int read(){
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x*=;x+=ch-'';ch=getchar();}
return x*f;
}
inline void update(int x){t[x].siz=t[t[x].ls].siz+t[t[x].rs].siz+t[x].w;}
inline void rturn(int &x){//左儿子成为根
int y=t[x].ls;
t[x].ls=t[y].rs; t[y].rs=x;
update(x); x=y;
}
inline void lturn(int &x){//右儿子成为根
int y=t[x].rs;
t[x].rs=t[y].ls; t[y].ls=x;
update(x); x=y;
}
void insert(int &x,int v){//把一个值放进去
if(!x){x=++tot;t[x].siz=t[x].w=;t[x].v=v;t[x].rd=rand();return;}
t[x].siz++;
if(t[x].v==v)t[x].w++;
else if(v<t[x].v){ insert(t[x].ls,v);if(t[x].rd>t[t[x].ls].rd)rturn(x);}
else {insert(t[x].rs,v);if(t[x].rd>t[t[x].rs].rd)lturn(x);}
update(x);
}
void del(int &x,int v){//把一个值去掉
if(t[x].v==v){
if(t[x].w>){t[x].w--;t[x].siz--;return;}
if(t[x].ls*t[x].rs==)x=t[x].ls+t[x].rs;//使该位置成为其儿子
else if(t[t[x].ls].rd<t[t[x].rs].rd){rturn(x);del(t[x].rs,v);}
//我觉得此时delx是没有必要的可以直接delx的儿子，标注出来如果ac不了再改回去。
else {lturn(x);del(t[x].ls,v);}
}
else if(v<t[x].v)del(t[x].ls,v);
else del(t[x].rs,v);
update(x);
}
void build(int x,int l,int r){//线段树结构
for(int i=l;i<=r;i++)insert(root[x],a[i]);
e[x].l=l;e[x].r=r;
if(l==r)return;
int mid=(l+r)/;e[x].mid=mid;
build(lc,l,mid);
build(rc,mid+,r);
}
int getrank2(int x,int v){
if(!x)return ;
if(t[x].v==v)return t[t[x].ls].siz;
else if(t[x].v>v)return getrank2(t[x].ls,v);
else return t[t[x].ls].siz+t[x].w+getrank2(t[x].rs,v);
}
int getrank(int x,int l,int r,int v){//线段树结构
if(l<=e[x].l&&r>=e[x].r){
return getrank2(root[x],v);
}int pai=;
if(l<=e[x].mid)pai+=getrank(lc,l,r,v);
if(e[x].mid<r)pai+=getrank(rc,l,r,v);
return pai;
}
void getnum(int x,int y,int k){//二分
int l=,r=inf,cnt=;
while(l<=r){//注意二分答案的储存方法，如何避免取到不存在的值
int mid=(l+r)/;
int w=getrank(,x,y,mid)+;
if(w<=k){l=mid+;cnt=mid;}
else r=mid-;
}printf("%d\n",cnt);
}
void change(int x,int z,int v){//线段树结构
del(root[x],a[z]);
insert(root[x],v);
if(e[x].l==e[x].r)return;
if(z<=e[x].mid)change(lc,z,v);
else change(rc,z,v);
}
void befo(int x,int num){
if(!x)return;
if(t[x].v<num){ans=max(t[x].v,ans);befo(t[x].rs,num);}
else befo(t[x].ls,num);
}
void afte(int x,int num){
if(!x)return;
if(t[x].v>num){ans=min(t[x].v,ans);afte(t[x].ls,num);}
else afte(t[x].rs,num);
}
void fir(int x,int l,int r,int num){//线段树结构
if(l<=e[x].l&&e[x].r<=r){
befo(root[x],num);
return;
}
if(l<=e[x].mid)fir(lc,l,r,num);
if(e[x].mid<r)fir(rc,l,r,num);
}
void las(int x,int l,int r,int num){//线段树结构
if(l<=e[x].l&&e[x].r<=r){
afte(root[x],num);
return;
}
if(l<=e[x].mid)las(lc,l,r,num);
if(e[x].mid<r)las(rc,l,r,num);
}
int main(){
//freopen("wtf.in","r",stdin);
n=read();m=read();
for(int i=;i<=n;i++)a[i]=read();
build(,,n);int x,y,z,f;
for(int i=;i<=m;i++){
scanf("%d",&f);
if(f==){scanf("%d%d%d",&x,&y,&z);printf("%d\n",getrank(,x,y,z)+);}
else if(f==){scanf("%d%d%d",&x,&y,&z);getnum(x,y,z);}
else if(f==){scanf("%d%d",&x,&y);change(,x,y);a[x]=y;}//记得把数组也改了。。一直re，大概因为这样导致del出现不存在的数无限递归
else if(f==){scanf("%d%d%d",&x,&y,&z);ans=;fir(,x,y,z);printf("%d\n",ans);}
else{scanf("%d%d%d",&x,&y,&z);ans=inf;las(,x,y,z);printf("%d\n",ans);}
}
return ;
}