样例过不了qwq 救救孩子

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N=15000010,INF=2147483647;
int n,m,op,a,b,k,pos,idx;
int L[N],R[N],T[N];//Segment tree 
int w[N];
struct node
{
    int val,p,s[2];
    int sz,cnt;
}tr[N];// bst 

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

inline void pushup(int u)
{
    tr[u].sz=tr[tr[u].s[0]].sz+tr[tr[u].s[1]].sz+tr[u].cnt;
}

void add(int u,int v,int p)
{
	tr[u].sz=tr[u].cnt=1;
	tr[u].val=v,tr[u].p=p;
}

inline void rotate(int x)
{
    int y=tr[x].p,z=tr[y].p;
    int k= (tr[y].s[1]==x);
    tr[tr[x].s[k^1]].p=y,tr[y].s[k]=tr[x].s[k^1];
    tr[y].p=x,tr[x].s[k^1]=y;
    tr[x].p=z,tr[z].s[y==tr[z].s[1]]=x;
    pushup(y),pushup(x);
}

inline void splay(int &root,int x,int k)
{
	while(tr[x].p!=k)
	{
		int y=tr[x].p,z=tr[y].p;
		if(z!=k)
			if((x==tr[y].s[1])^(y==tr[z].s[1]))rotate(x);
			else rotate(y);
		rotate(x);
	}
	if(!k)root=x;
}

inline int find(int &root,int x)//找到val=x的节点
{
	int u=root;
	while(u&&tr[u].val!=x)
	{
		u=tr[u].s[x>tr[u].val];
	}
	return u;
}

void insert(int &root,int v)//平衡树插入 
{
	int u=root,p=0;
	while(u&&tr[u].val!=v)
	{
		p=u,u=tr[u].s[v>tr[u].val];
	}
	if(u)tr[u].cnt++;
	else
	{
		u=++idx;
		if(p)tr[p].s[v>tr[p].val]=u;
		add(u,v,p);
	}
	pushup(u);
	splay(root,u,0);
	return;
}

int get_prev(int &root,int x)//平衡树前驱 
{
	int k=find(root,x);splay(root,k,0);
	int u=tr[root].s[0];
	while(tr[u].s[1])u=tr[u].s[1];
	return u;
}

int get_next(int &root,int x)//平衡树后继 
{
	int k=find(root,x);splay(root,k,0);
	int u=tr[root].s[1];
	while(tr[u].s[0])u=tr[u].s[0];
	return u;
}

void remove(int &root,int x)//平衡树删除 
{
	int k=find(root,x);splay(root,k,0);
	if(tr[k].cnt>1)
	{
		tr[k].cnt--;
		pushup(k);
		return;
	}
	int l=get_prev(root,x),r=get_next(root,x);
	splay(root,l,0),splay(root,r,l);
	tr[r].s[0]=0;
	pushup(r),pushup(l);
	return;
}

int get_rank(int &root,int k)//平衡树查找排名
{
	int u=root,ans=0;
	while(u)
	{
		if(tr[u].val>k)u=tr[u].s[0];
		else
		{
			ans+=tr[tr[u].s[0]].sz;
			if(tr[u].val==k)
			{
				splay(root,u,0);
				return ans;
			}
			ans+=tr[u].cnt;
			u=tr[u].s[1];
		}
	}
	return ans;
}

void build(int u,int l,int r)//线段树建树 
{
    L[u]=l,R[u]=r;
    insert(T[u],INF),insert(T[u],-INF);
    for(int i=l;i<=r;i++)
        insert(T[u],w[i]);
    if(l==r)return;
    int mid=l+r>>1;
    build(u<<1,l,mid);
    build(u<<1|1,mid+1,r);
}

int query(int u,int l,int r,int k)//查询排名
{
    if(L[u]>=l&&R[u]<=r)return get_rank(T[u],k);
    int mid=L[u]+R[u]>>1,res=0;
    if(l<=mid)res+=query(u<<1,l,r,k);
    if(r>mid)res+=query(u<<1|1,l,r,k);
    return res;
}

void change(int u,int p,int k)//修改 
{
    remove(T[u],w[p]),insert(T[u],k);
    if(L[u]==R[u])return;
    int mid=L[u]+R[u]>>1;
    if(p<=mid)change(u<<1,p,k);
    else change(u<<1|1,p,k);
}

int get_prefix(int u,int l,int r,int x)
{
	if(L[u]>=l&&R[u]<=r)return tr[get_prev(T[u],x)].val;
	int res=-INF,mid=L[u]+R[u]>>1;
	if(l<=mid)res=max(res,get_prefix(u<<1,l,r,x));
	if(r>mid)res=max(res,get_prefix(u<<1|1,l,r,x));
	return res;
}

int get_suffix(int u,int l,int r,int x)
{
	if(L[u]>=l&&R[u]<=r)return tr[get_next(T[u],x)].val;
	int res=INF,mid=L[u]+R[u]>>1;
	if(l<=mid)res=min(res,get_suffix(u<<1,l,r,x));
	if(r>mid)res=min(res,get_suffix(u<<1|1,l,r,x));
	return res;
}

//void print_tree(int u)
//{
//	if(tr[u].s[0])print_tree(tr[u].s[0]);
//	printf("%d(*%d) ",tr[u].val,tr[u].cnt);
//	if(tr[u].s[1])print_tree(tr[u].s[1]);
//}

//void print()
//{
//	for(int i=1;i<=7;i++)
//   	printf("l=%d,r=%d\n",L[i],R[i]),print_tree(T[i]),puts("");
//    puts("");
//}

int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;i++)
        w[i]=read();
    build(1,1,n);
    while(m--)
    {
    	print();
        op=read();
        switch(op)
        {
            case 1:
            {
                a=read(),b=read(),k=read();
                printf("%d\n",query(1,a,b,k)+1);
                break;
            }
            case 2:
            {
                a=read(),b=read(),k=read();
                int l=0,r=1e8;
                while(l<r)
                {
                    int mid=l+r+1>>1;
                    if(query(1,a,b,mid)+1<=k)l=mid;
                    else r=mid-1;
                }
                printf("%d\n",r);
                break;
            }
            case 3:
            {
                pos=read(),k=read();
                change(1,pos,k);
                w[pos]=k;
                break;
            }
            case 4:
            {
                a=read(),b=read(),k=read();
                printf("%d\n",get_prefix(1,a,b,k));
                break;
            }
            case 5:
            {
                a=read(),b=read(),k=read();
                printf("%d\n",get_suffix(1,a,b,k));
                break; 
            }
            default:
            {
                puts("input_error");
                break;
            }
        }
    }
    return 0;
}