树套树板子，但是带修莫队+值域分块

\(\text{Link - Luogu Blog}\)

原题传送门

没啥重要的事情，就是终于过了这题非常开心，发现自己是莫队的时间戳部分写错了调了 114514 年我也只能说是十分趣味。

以及今天深刻地认识到了带修莫队应该 len=pow(n,0.66);。

就是裸的带修莫队+值域分块，就不说了，直接放代码了昂。

如果有人写这个做法的话或许这可以带来一点帮助？

加了光读，用的普通 cout，总用时 945ms，每个测试点用时不超过 150ms！说实话跑得真的很快啊！重铸根号荣光！ 我不是根号批。

\(\text{record}\)

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define re register
#define getchar()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
char buf[1<<21],*p1=buf,*p2=buf;
const int N=5e4+113,V=1e5+113,sq=360,Zi_Gao=2147483647;
int n,m,a[N],cnt_que,cnt_upd,ans[N],idx;
int id[V],bl[sq],br[sq],len,vmax,b[V],sum[sq],cnt[V];
il int read(){
    re 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<<3)+(x<<1)+(c^48),c=getchar();
    return x*f;
}
struct query{
    int op,l,r,x,t,id;
}q[N];
il bool cmp(query x,query y){
    if(id[x.l]^id[y.l])return x.l<y.l;
    if(id[x.r]^id[y.r])return x.r<y.r;
    return x.t<y.t;
}
struct update{
    int place,x;
}u[N];
il void init(){
    for(re int i=1;i<=cnt_upd;i++)b[++idx]=u[i].x;
    for(re int i=1;i<=cnt_que;i++)
        if(q[i].op!=2)b[++idx]=q[i].x;
    vmax=idx;
    sort(b+1,b+1+vmax);
    vmax=unique(b+1,b+1+vmax)-b-1;
    len=sqrt(vmax);
    for(re int i=1;i<=vmax;i++)id[i]=(i-1)/len+1;
    for(re int i=1;i<=id[vmax];i++)
        bl[i]=br[i-1]+1,br[i]=i*len;
    br[id[vmax]]=vmax;
    for(re int i=1;i<=n;i++)
        a[i]=lower_bound(b+1,b+1+vmax,a[i])-b;
    for(re int i=1;i<=cnt_upd;i++)
        u[i].x=lower_bound(b+1,b+1+vmax,u[i].x)-b;
    for(re int i=1;i<=cnt_que;i++)
        if(q[i].op!=2)q[i].x=lower_bound(b+1,b+1+vmax,q[i].x)-b;
}
#define Add(x) cnt[x]++,sum[id[x]]++
#define Del(x) cnt[x]--,sum[id[x]]--
il int solve_1(int x){
    int res=0;
    for(re int i=1;i<id[x];i++)res+=sum[i];
    for(re int i=bl[id[x]];i<x;i++)res+=cnt[i];
    return res+1;
}
il int solve_2(int x){
    int tot=0;
    for(re int i=1;i<=id[vmax];i++){
        tot+=sum[i];
        if(tot>=x){
            tot-=sum[i];
            for(re int j=bl[i];j<=br[i];j++){
                tot+=cnt[j];
                if(tot>=x)return b[j];
            }
        }
    }
    return Zi_Gao;
}
il int solve_4(int x){
    for(re int i=x-1;i>=bl[id[x]];i--)
        if(cnt[i])return b[i];
    for(re int i=id[x]-1;i;i--)
        if(sum[i])
            for(re int j=br[i];j>=bl[i];j--)
                if(cnt[j])return b[j];
    return -Zi_Gao;
}
il int solve_5(int x){
    for(re int i=x+1;i<=br[id[x]];i++)
        if(cnt[i])return b[i];
    for(re int i=id[x]+1;i<=id[vmax];i++)
        if(sum[i])
            for(re int j=bl[i];j<=br[i];j++)
                if(cnt[j])return b[j];
    return Zi_Gao;
}
int main(){
    n=read(),m=read();
    len=pow(n,0.66);
    for(re int i=1;i<=n;i++)
        a[i]=read(),id[i]=(i-1)/len+1,b[++idx]=a[i];
    for(re int i=1;i<=m;i++){
        int op=read();
        if(op==3){
            cnt_upd++;
            u[cnt_upd].place=read(),u[cnt_upd].x=read();
            continue;
        }
        cnt_que++;
        q[cnt_que].op=op,q[cnt_que].l=read(),q[cnt_que].r=read(),q[cnt_que].x=read();
        q[cnt_que].t=cnt_upd,q[cnt_que].id=cnt_que;
    }
    sort(q+1,q+1+cnt_que,cmp);
    init();
    re int L=1,R=0,T=0;
    for(re int i=1;i<=cnt_que;i++){
        re int l=q[i].l,r=q[i].r,x=q[i].x,op=q[i].op;
        while(R<r)R++,Add(a[R]);
        while(L>l)L--,Add(a[L]);
        while(R>r)Del(a[R]),R--;
        while(L<l)Del(a[L]),L++;
        while(T<q[i].t){
            T++;
            int pla=u[T].place;
            if(pla>=l&&pla<=r)Del(a[pla]),Add(u[T].x);
            swap(u[T].x,a[pla]);
        }
        while(T>q[i].t){
            int pla=u[T].place;
            if(pla>=l&&pla<=r)Del(a[pla]),Add(u[T].x);
            swap(u[T].x,a[pla]);
            T--;
        }
        if(op==1)ans[q[i].id]=solve_1(x);
        if(op==2)ans[q[i].id]=solve_2(x);
        if(op==4)ans[q[i].id]=solve_4(x);
        if(op==5)ans[q[i].id]=solve_5(x);
    }
    for(re int i=1;i<=cnt_que;i++)cout<<ans[i]<<'\n';
    return 0;
}