写的两只log的算法

结果不开O270分,开O2最慢点948ms,不知道为什么这么慢

#include<bits/stdc++.h>
#define pii pair<int,int>
#define pu(x) qz[x].sz=qz[qz[x].ls].sz+qz[qz[x].rs].sz+1
using namespace std;
const int inf=2147483647;
int n,m,cnt,a[50001];
struct Node
{
    int qz;
    int ls;
    int rs;
    int sz;
    int rn;
    Node()
    {
        ls=rs=qz=0,sz=1,rn=rand();
    }
};
struct fhq_treap
{
    int rt;
    vector<Node>qz;
    int merg(int rt1,int rt2)
    {
        if(!rt1||!rt2)return rt1+rt2;
        else if(qz[rt1].rn<qz[rt2].rn)
        {
            qz[rt1].rs=merg(qz[rt1].rs,rt2);
            pu(rt1);
            return rt1;
        }
        else
        {
            qz[rt2].ls=merg(rt1,qz[rt2].ls);
            pu(rt2);
            return rt2;
        }
    }
    pii split_qz(int x,int now)//同样的划在左边
    {
        if(now==0)return make_pair(0,0);
        else if(qz[now].qz<=x)
        {
            pii a=split_qz(x,qz[now].rs);
            qz[now].rs=a.first;
            pu(now);
            return make_pair(now,a.second);
        }
        else
        {
            pii a=split_qz(x,qz[now].ls);
            qz[now].ls=a.second;
            pu(now);
            return make_pair(a.first,now);
        }
    }
    pii split_pm(int p,int now)//1-p名划
    {
        if(now==0)return make_pair(0,0);
        else if(qz[qz[now].ls].sz+1<=p)
        {
            pii a=split_pm(p-qz[qz[now].ls].sz-1,qz[now].rs);
            qz[now].rs=a.first;
            pu(now);
            return make_pair(now,a.second);
        }
        else
        {
            pii a=split_pm(p,qz[now].ls);
            qz[now].ls=a.second;
            pu(now);
            return make_pair(a.first,now);
        }
    }
    void ins(int x)
    {
        Node aa;
        aa.qz=x;
        qz.push_back(aa);
        if(!rt)
        {
            rt=qz.size()-1;
            return;
        }
        pii a=split_qz(x,rt);
        rt=merg(a.first,qz.size()-1);
        rt=merg(rt,a.second);
    }
    void del(int x)
    {
        if(qz[rt].sz==1)
        {
            rt=0;
            return;
        }
        pii a=split_qz(x-1,rt);
        pii b=split_pm(1,a.second);
        rt=merg(a.first,b.second);
    }
    int sm(int l,int r)
    {
        pii a=split_qz(r,rt);
        pii b=split_qz(l-1,a.first);
        int ans=qz[b.second].sz;
        rt=merg(b.first,b.second);
        rt=merg(rt,a.second);
        return ans;
    }
};
struct N
{
    fhq_treap ft;
    int ls,rs,l,r;
} p[500001];
int qzs_newnode(int l,int r)
{
    p[++cnt].l=l,p[cnt].r=r;
    Node aaa;
    aaa.sz=0;
    p[cnt].ft.qz.push_back(aaa);
    return cnt;
}
void ins(int qz,int wz,int now)
{
    //cout<<qz<<' '<<wz<<' '<<now<<' '<<p[now].l<<' '<<p[now].r<<endl;
    int ll=p[now].l,rr=p[now].r,mid=(ll+rr)/2;
    p[now].ft.ins(wz);
    if(ll==rr)return;
    if(qz<=mid)
    {
        if(!p[now].ls)p[now].ls=qzs_newnode(ll,mid);
        ins(qz,wz,p[now].ls);
    }
    else
    {
        if(!p[now].rs)p[now].rs=qzs_newnode(mid+1,rr);
        ins(qz,wz,p[now].rs);
    }
}
int qu_pm(int l,int r,int x,int m)
{
    if(p[m].r<x)
        return p[m].ft.sm(l,r);
    if(p[m].l>=x)
        return 0;
    int ans=0;
    if(p[m].ls)ans+=qu_pm(l,r,x,p[m].ls);
    if(p[m].rs) ans+=qu_pm(l,r,x,p[m].rs);
    return ans;
}
int qu_qz(int l,int r,int x,int m)
{
    //cout<<l<<' '<<r<<' '<<x<<' '<<p[m].l<<' '<<p[m].r<<endl;
    if(p[m].l==p[m].r)return p[m].l;
    if(!p[m].ls)return qu_qz(l,r,x,p[m].rs);
    int tt=p[p[m].ls].ft.sm(l,r);
    //cout<<p[m].l<<' '<<p[m].r<<' '<<tt<<endl;
    if(x<=tt)return qu_qz(l,r,x,p[m].ls);
    else return qu_qz(l,r,x-tt,p[m].rs);
}
void xg1(int wz,int la,int now)
{
    //cout<<p[now].l<<' '<<p[now].r<<' '<<la<<endl;
    p[now].ft.del(wz);
    if(p[now].l==p[now].r)return;
    if(la<=(p[now].l+p[now].r)/2)
        xg1(wz,la,p[now].ls);
    else
        xg1(wz,la,p[now].rs);
}
int main()
{
    //freopen("tt.out","w",stdout);
    qzs_newnode(0,2e8);
    scanf("%d%d",&n,&m);
    for(int i=1; i<=n; ++i)
    {
        scanf("%d",a+i);
        ins(a[i],i,1);
    }
    for(int i=1; i<=m; ++i)
    {
        int opt,l,r,x;
        scanf("%d",&opt);
        if(opt==1)
        {
            scanf("%d%d%d",&l,&r,&x);
            int pp=qu_pm(l,r,x,1);
            printf("%d\n",pp+1);
        }
        else if(opt==2)
        {
            scanf("%d%d%d",&l,&r,&x);
            int pp=qu_qz(l,r,x,1);
            printf("%d\n",pp);
        }
        else if(opt==3)
        {
            scanf("%d%d",&l,&x);
            xg1(l,a[l],1);
            a[l]=x;
            ins(a[l],l,1);
        }
        else if(opt==4)
        {
            scanf("%d%d%d",&l,&r,&x);
            int pm=qu_pm(l,r,x,1);
            if(!pm)
            {
                printf("-2147483647\n");
                continue;
            }
            int pp=qu_qz(l,r,pm,1);
            printf("%d\n",pp);
        }
        else if(opt==5)
        {
            scanf("%d%d%d",&l,&r,&x);
            int pm=qu_pm(l,r,x+1,1)+1;
            if(pm>r-l+1)
            {
                printf("2147483647\n");
                continue;
            }
            int pp=qu_qz(l,r,pm,1);
            printf("%d\n",pp);
        }
    }
}