有人用线段树+Treap/FHQ Treap卡过去吗

我的TLE 50pts，怎么卡都没用

//树套树
#include<bits/stdc++.h>
#define mid ((l+r)>>1)
using namespace std;
const int N=1e8+5,M=5e5+5;
const int inf=2147483647;
int n,m,f[M],cnt,root[M<<2];
struct FHQ_Treap{int pri,l,r,size,x;}a[N];
inline int read(){
    int x=0,s=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){
        if(ch=='-') s=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+ch-'0',ch=getchar();
    return x*s;
}
inline void write(int x){
    if(abs(x)>=10) write(x/10);
    if(x<0&&abs(x)<=9) putchar('-');
    putchar(abs(x)%10+48);
}
inline void pushup(int now){
    a[now].size=a[a[now].l].size+a[a[now].r].size+1;
    return;
}
inline int new_node(int k){
    a[++cnt].pri=rand();
    a[cnt].size=1;
    a[cnt].x=k;
    return cnt;
}
inline void split(int now,int k,int &x,int &y){
    if(!now){
        x=y=0;
        return;
    }
    if(a[now].x<=k){
        x=now;
        split(a[now].r,k,a[now].r,y);
    }else{
        y=now;
        split(a[now].l,k,x,a[now].l);
    }
    pushup(now);
}
inline int merge(int x,int y){
    if(!x||!y) return x+y;
    if(a[x].pri<a[y].pri){
        a[x].r=merge(a[x].r,y);
        pushup(x);
        return x;
    }else{
        a[y].l=merge(x,a[y].l);
        pushup(y);
        return y;
    }
}
inline void insert(int now,int k){
    int x,y;
    split(root[now],k-1,x,y);
    root[now]=merge(merge(x,new_node(k)),y);
}
inline void remove(int now,int k){
    int x,y,z;
    split(root[now],k-1,x,y);
    split(y,k,y,z);
    y=merge(a[y].l,a[y].r);
    root[now]=merge(merge(x,y),z);
}
inline int Rank(int p,int k){
    int x,y;
    split(root[p],k-1,x,y);
    int ans=a[x].size;
    root[p]=merge(x,y);
    return ans;
}
// inline int kth(int now,int x){
//     while(1){
//         if(x<=a[a[now].l].size) now=a[now].l;
//         else if(x==a[a[now].l].size+1) return now;
//         else x-=a[a[now].l].size+1,now=a[now].r;
//     }
// }
// inline int FHQ_find_l(int now,int k){
//     int x,y,ans;
//     split(root[now],k-1,x,y);
//     if(a[x].size==0) ans=-inf;
//     else ans=a[kth(x,a[x].size)].x;
//     root[now]=merge(x,y);
//     return ans;
// }
// inline int FHQ_find_r(int now,int k){
//     int x,y,ans;
//     split(root[now],k,x,y);
//     if(a[y].size==0) ans=inf;
//     else ans=a[kth(y,1)].x;
//     root[now]=merge(x,y);
//     return ans;
// }
inline void build(int p,int l,int r){
    root[p]=0;
    for(register int i=l;i<=r;i++) insert(p,f[i]);
    if(l==r) return;
    build(p<<1,l,mid);
    build(p<<1|1,mid+1,r);
}
inline int ask_kth(int p,int l,int r,int x,int y,int k){
    if(y<l||x>r) return 0;
    if(x<=l&&r<=y) return Rank(p,k);
    return ask_kth(p<<1,l,mid,x,y,k)+ask_kth(p<<1|1,mid+1,r,x,y,k);
}
inline int ask_rank(int x,int y,int k){
    int l=0,r=2e9,ans=-1;
    while(l<=r){
        if(ask_kth(1,1,n,x,y,mid)+1<=k) ans=mid,l=mid+1;
        else r=mid-1;
    }
    return ans;
}
inline void change(int p,int l,int r,int x,int k){
    remove(p,f[x]);
    insert(p,k);
    if(l==r) return;
    if(x<=mid) change(p<<1,l,mid,x,k);
    else change(p<<1|1,mid+1,r,x,k);
}
// inline int find_l(int p,int l,int r,int x,int y,int k){
//     if(l>y||x>r) return -inf;
//     if(x<=l&&r<=y) return FHQ_find_l(p,k);
//     return max(find_l(p<<1,l,mid,x,y,k),find_l(p<<1|1,mid+1,r,x,y,k));
// }
// inline int find_r(int p,int l,int r,int x,int y,int k){
//     if(l>y||x>r) return inf;
//     if(x<=l&&r<=y) return FHQ_find_r(p,k);
//     return min(find_r(p<<1,l,mid,x,y,k),find_r(p<<1|1,mid+1,r,x,y,k));
// }
int main(){
    n=read(),m=read();
    for(register int i=1;i<=n;i++) f[i]=read();
    build(1,1,n);
    for(register int i=1;i<=m;i++){
        int x,y,k;
        char op=getchar();
        while(op<'A'||op>'Z') op=getchar();
        if(op=='Q') x=read(),y=read(),k=read(),write(ask_rank(x,y,k)),puts("");
        else x=read(),y=read(),change(1,1,n,x,y),f[x]=y;
        // op=read(),x=read(),y=read();
        // if(op==1) k=read(),write(ask_kth(1,1,n,x,y,k)+1);
        // if(op==2) k=read(),write(ask_rank(x,y,k));
        // if(op==3) change(1,1,n,x,y),f[x]=y;
        // if(op==4) k=read(),write(find_l(1,1,n,x,y,k));
        // if(op==5) k=read(),write(find_r(1,1,n,x,y,k));
        // if(op!=3) puts("");
    }
}