竞选本题最唐代码

#include<bits/stdc++.h>
using namespace std;
#define int long long
inline int read(){
    int s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    return s*w;
}
inline void write(int x){
    if(x==0){putchar('0');return;}
    int len=0,k1=x,c[10005];
    if(k1<0)k1=-k1,putchar('-');
    while(k1)c[len++]=k1%10+'0',k1/=10;
    while(len--)putchar(c[len]);
}
mt19937 rnd(time(0));
const int N=1e5+5,M=5e6+5,INF=2e9+9;
int rt,top,n,m,q;array<int,4>st[M];int vifhq[N],g[N];
struct FHQ_Treap{
    struct Tr{int ls,rs,pri,key,siz;};vector<Tr>tr;int sz=0,rt=0;
    void push_up(int x){tr[x].siz=tr[tr[x].ls].siz+tr[tr[x].rs].siz+1;}
    void newnode(int x){tr.push_back({0,0,rnd(),x,1});sz++;}
    void split(int x,int y,int &L,int &R){
        if(x==0){L=R=0;return ;}
        if(tr[x].key<=y)L=x,split(tr[x].rs,y,tr[x].rs,R);
        else R=x,split(tr[x].ls,y,L,tr[x].ls);
        push_up(x);return ;
    }int merge(int L,int R){
        if(L==0||R==0)return L+R;
        if(tr[L].pri>tr[R].pri){
            tr[L].rs=merge(tr[L].rs, R);
            push_up(L);return L;
        }else{
            tr[R].ls=merge(L, tr[R].ls);
            push_up(R);return R;
        }
    }int insert(int x){
        int L,R;split(rt,x,L,R);
        newnode(x);rt=merge(merge(L, sz), R);
        return sz;
    }int del(int x){
        int L,M,R;
        split(rt,x,L,R);split(L,x-1,L,M);
        M=merge(tr[M].ls,tr[M].rs);
        rt=merge(merge(L,M),R);
        return rt;
    }int getrank(int x){
        int L,R,ans;
        split(rt,x-1,L,R);
        ans=tr[L].siz+1;rt=merge(L,R);
        return ans;
    }int kth(int x,int k){
        if(k==tr[tr[x].ls].siz+1)return x;
        if(k<=tr[tr[x].ls].siz)return kth(tr[x].ls,k);
        return kth(tr[x].rs,k-tr[tr[x].ls].siz-1);
    }int pre(int x){
        int L,R,ans;
        split(rt,x-1,L,R);
        if(L==0)ans=-INF;else ans=tr[kth(L,tr[L].siz)].key;
        rt=merge(L,R);
        return ans;
    }int suc(int x){
        int L,R,ans;
        split(rt,x,L,R);
        if(R==0)ans=INF;else ans=tr[kth(R,1)].key;
        rt=merge(L,R);
        return ans;
    }int count_val(int x){
        int L,R,M;
        split(rt,x-1,L,R); split(R,x,M,R);
        int ans=(M==0?0:tr[M].siz);
        R=merge(M,R);rt=merge(L,R);
        return ans;
    }int lower_bound(int x){
        int L,R,ans;
        split(rt,x-1,L,R);
        if(R==0) ans=INF;
        else ans=tr[kth(R,1)].key;
        rt=merge(L,R);
        return ans;
    }int prev_before_lb(int x){
        int L,R,ans;
        split(rt,x-1,L,R);
        if(L==0)ans=-INF;
        else ans=tr[kth(L,tr[L].siz)].key;
        rt=merge(L,R);
        return ans;
    }
}fhq[N];
int ans[N],a[N];vector<int>mp[N];
struct Sgt{
    struct Tr{int ls,rs,mx,mn,tag;}tr[N<<1];int cnt=0;
    #define ls(p) tr[p].ls
    #define rs(p) tr[p].rs
    void push_up(int p){
        // st.push({p,tr[p].mx,tr[p].mn,tr[p].tag});
        st[++top]={p,tr[p].mx,tr[p].mn,tr[p].tag};
        tr[p].mn=min(tr[ls(p)].mn,tr[rs(p)].mn);
        tr[p].mx=max(tr[ls(p)].mx,tr[rs(p)].mx);
    }void build(int &p,int pl,int pr){
        p=++cnt;if(pl==pr){tr[p].mx=-INF,tr[p].mn=INF;return ;}
        int mid=pl+pr>>1;
        build(ls(p),pl,mid);build(rs(p),mid+1,pr);push_up(p);
    }void add_tag(int p,int pl,int pr,int k){
        // st.push({p,tr[p].mx,tr[p].mn,tr[p].tag});
        st[++top]={p,tr[p].mx,tr[p].mn,tr[p].tag};
        tr[p].mx=tr[p].tag=k;tr[p].mn=k-pr+1;
    }void push_down(int p,int pl,int pr){
        if(tr[p].tag){
            int mid=pl+pr>>1;
            add_tag(ls(p),pl,mid,tr[p].tag);
            add_tag(rs(p),mid+1,pr,tr[p].tag);
            st[++top]={p,tr[p].mx,tr[p].mn,tr[p].tag};
        }tr[p].tag=0;
    }void upd(int p,int pl,int pr,int l,int r,int k){
        if(pl>=l&&pr<=r){add_tag(p,pl,pr,k);return ;}push_down(p,pl,pr);
        // cout<<l<<" "<<r<<" "<<k<<" "<<p<<" "<<pl<<" "<<pr<<endl;
        int mid=pl+pr>>1;
        if(l<=mid)upd(ls(p),pl,mid,l,r,k);
        if(mid<r)upd(rs(p),mid+1,pr,l,r,k);push_up(p);
    }
    int get(int p,int pl,int pr,int l,int r,int k){
        if(tr[p].mx<k)return INF;if(pl==pr)return pl;
        int mid=pl+pr>>1,ans=INF;push_down(p,pl,pr);
        if(l<=pl&&pr<=r){
            if(tr[ls(p)].mx>=k)return get(ls(p),pl,mid,l,r,k);
            else return get(rs(p),mid+1,pr,l,r,k);
        }if(l<=mid)ans=get(ls(p),pl,mid,l,r,k);
        if(r>mid&&ans==INF)ans=get(rs(p),mid+1,pr,l,r,k);
        return ans;
    }void update(int l,int r,int k){
        l=max(1ll,l),r=min(r,get(rt,1,n,1,n,k)-1);
        // cout<<l<<" "<<r<<endl;
        if(l>r)return ;upd(rt,1,n,l,r,k);
    }int getans(){return tr[1].mn;}
    #undef ls(p) tr[p].ls
    #undef rs(p) tr[p].rs
}SgT;
struct SGT{
    vector<pair<int,int>>tr[N<<2];
    int ls(int p){return p<<1;}
    int rs(int p){return p<<1|1;}
    void delet(int u,int k){
        while(top>k){
            auto [p,mx,mn,tag]=st[top--];
            SgT.tr[p].mx=mx,SgT.tr[p].mn=mn,SgT.tr[p].tag=tag;
        }for(auto [l,r]:tr[u])fhq[r].insert(l);
    }void upd(int p,int pl,int pr,int l,int r,int a,int b){
        if(l>r)return ;if(pl>=l&&pr<=r){tr[p].push_back({a,b});return ;}
        int mid=pl+pr>>1;
        if(l<=mid)upd(ls(p),pl,mid,l,r,a,b);
        if(mid<r)upd(rs(p),mid+1,pr,l,r,a,b);
    }void solve(int p,int pl,int pr){
        // cout<<p<<" "<<pl<<" "<<pr<<endl;
        int pre=top;
        for(auto [l,r]:tr[p]){
            fhq[r].del(l);
            if(fhq[r].count_val(l))continue;
            int it=fhq[r].lower_bound(l);
            int pv=fhq[r].prev_before_lb(l);
            SgT.update(pv+1,l,it);
        }if(pl==pr){ans[pl]=SgT.getans();delet(p,pre);return ;}
        int mid=pl+pr>>1;
        solve(ls(p),pl,mid);solve(rs(p),mid+1,pr);
        delet(p,pre);return ;
    }
}sgt;

signed main(){
    // freopen("x.in","r",stdin);
    // freopen("x.out","w",stdout);
    n=read(),m=read(),q=read();SgT.build(rt,1,n);
    for(int i=1;i<=m;i++){fhq[i].tr.push_back({0,0,0,0,0});fhq[i].insert(INF);fhq[i].insert(-INF);}
    for(int i=1;i<=n;i++){
        a[i]=read(); fhq[a[i]].insert(i);
        mp[i].push_back(a[i]);
    }for(int i=1;i<=q;i++){
        int op=read();
        if(op==1){
            int x=read(),y=read();
            fhq[y].insert(x);mp[x].push_back(y);
            sgt.upd(1,1,q,1,i-1,x,y);
            sgt.upd(1,1,q,i,q,x,a[x]);a[x]=y;
        }else vifhq[i]=1;
    }for(int i=1;i<=n;i++){
        if(i==1){for(int j=1;j<=m;j++)g[i]=max(g[i],fhq[j].lower_bound(i));continue;}
        g[i]=g[i-1];for(auto j:mp[i-1])g[i]=max(g[i],fhq[j].lower_bound(i));
    }for(int i=1;i<=n;i++)SgT.upd(rt,1,n,i,i,g[i]);
    sgt.solve(1,1,q);
    for(int i=1;i<=q;i++)if(ans[i]>INF/2)ans[i]=-1;
    for(int i=1;i<=q;i++)if(vifhq[i])cout<<ans[i]<<"\n";
    return 0;
}