线段树套pb_ds里的平衡树，在洛谷OJ上测试，后三个测试点TLE
#include<cstdio>
#include<algorithm>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define N 50010
#define INF 2147483647
using namespace std;
using namespace __gnu_pbds;
typedef pair<int,int> Point;
typedef tree<Point,null_type,less<Point>,rb_tree_tag,tree_order_statistics_node_update> rb_tree;
typedef rb_tree::iterator ITER;
rb_tree T[N<<2];
int a[N],tags[N],tag,n,m;
void buildtree(int rt,int l,int r)
{
if(l==r)
{
T[rt].insert(Point(a[l],l));
return;
}
int m=(l+r>>1);
buildtree(rt<<1,l,m);
buildtree(rt<<1|1,m+1,r);
T[rt]=T[rt<<1];
for(ITER it=T[rt<<1|1].begin();it!=T[rt<<1|1].end();++it)
T[rt].insert(*it);
}
int Rank(int v,int TAG,int ql,int qr,int rt,int l,int r)
{
if(ql<=l&&r<=qr)
return T[rt].order_of_key(Point(v,TAG));
int m=(l+r>>1),res=0;
if(ql<=m) res+=Rank(v,TAG,ql,qr,rt<<1,l,m);
if(m<qr) res+=Rank(v,TAG,ql,qr,rt<<1|1,m+1,r);
return res;
}
int Pre(int v,int ql,int qr,int rt,int l,int r)
{
if(ql<=l&&r<=qr)
{
ITER it=T[rt].lower_bound(Point(v,0));
if(it==T[rt].begin()) return -INF;
--it;
return (*it).first;
}
int m=(l+r>>1),res=-INF;
if(ql<=m) res=max(res,Pre(v,ql,qr,rt<<1,l,m));
if(m<qr) res=max(res,Pre(v,ql,qr,rt<<1|1,m+1,r));
return res;
}
int Nex(int v,int ql,int qr,int rt,int l,int r)
{
if(ql<=l&&r<=qr)
{
ITER it=T[rt].upper_bound(Point(v,INF));
if(it==T[rt].end())
return INF;
return (*it).first;
}
int m=(l+r>>1),res=INF;
if(ql<=m) res=min(res,Nex(v,ql,qr,rt<<1,l,m));
if(m<qr) res=min(res,Nex(v,ql,qr,rt<<1|1,m+1,r));
return res;
}
void Update(int p,int v,int rt,int l,int r)
{
T[rt].erase(Point(a[p],tags[p]));
T[rt].insert(Point(v,tag));
if(l==r) return;
int m=(l+r>>1);
if(p<=m) Update(p,v,rt<<1,l,m);
else Update(p,v,rt<<1|1,m+1,r);
}
int Kth(int K,int ql,int qr)
{
int l=0,r=100000000;
while(l<r)
{
int m=(l+r>>1);
if(Rank(m,INF,ql,qr,1,1,n)>=K)
r=m;
else
l=m+1;
}
return l;
}
int main()
{
// freopen("bzoj3196.in","r",stdin);
int op,x,y,z;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;++i)
{
scanf("%d",&a[i]);
tags[i]=i;
}
tag=n;
buildtree(1,1,n);
// for(int i=1;i<=n*4;++i)
// printf("%d ",(*T[i].begin()).second);
// puts("");
for(;m;--m)
{
scanf("%d%d%d",&op,&x,&y);
if(op==1)
{
scanf("%d",&z);
printf("%d\n",Rank(z,0,x,y,1,1,n)+1);
}
else if(op==2)
{
scanf("%d",&z);
printf("%d\n",Kth(z,x,y));
}
else if(op==3)
{
++tag;
Update(x,y,1,1,n);
a[x]=y;
tags[x]=tag;
}
else if(op==4)
{
scanf("%d",&z);
printf("%d\n",Pre(z,x,y,1,1,n));
}
else
{
scanf("%d",&z);
printf("%d\n",Nex(z,x,y,1,1,n));
}
}
return 0;
}