P7230

Inui_Sana · 2024-09-09 18:17:38 · 题解

模拟赛搬了这题的 k=10^5 加强版。于是有了一个复杂度和 k 无关的做法。感觉学到了。

设 f_i 为左端点为 i 时，最小的可行右端点。考虑维护这个东西。但是你发现修改一个位置的值很难维护。

你又发现每次只修改一个数，考虑线段树分治。但是你又发现你连插入都不会做。但是删除非常简单。设删了 p 位置的一个 x，左右第一个 x 分别在 l,r，就只要 \forall i\in[l+1,p],f_i\to \max(f_i,r) 就行。于是还是线段树分治，但是对删除操作进行。

具体地，把修改操作视作一次删除一次插入。先默认进行所有插入，再在某一些时间区间上进行删除。再来看看我们要维护什么：

• 找一个数的前驱后继，删除/插入一个数。

使用 multiset 维护即可。

• 区间对 x 取 \max。

一般需要吉司机，但是发现这题 f_i 一定单调递增，于是转化成一段区间赋值 x。使用线段树，支持区间赋值以及线段树上二分。

同时注意到将一个区间 [l,r] 赋值成 x 的时候，区间 [l,r] 内的答案一定是 x-r+1，于是可以同时维护答案。

至于线段树分治上的撤销操作，只需要每次这棵线段树上维护的值改变（包括 tag），就将原来的值压进一个栈里，撤销时直接修改即可。

时间复杂度 O(q\log q\log n) 解决。

code：

int n,m,q,top,a[N],f[N],ans[N];
bool vis[N];
multiset<int> st[N];
vector<int> g[N];
struct node{
    int l,r,k;
    node(int _l=0,int _r=0,int _k=0):l(_l),r(_r),k(_k){}
    bool operator<(const node &rhs)const{
        return k<rhs.k;
    }
};
struct Node{
    int o,x,y,z;
}d[N*400];
struct Sgt{
    int tr[N<<2],tag[N<<2],mn[N<<2];
    il void pushup(int o){
        d[++top]={o,tr[o],tag[o],mn[o]};
        tr[o]=max(tr[o<<1],tr[o<<1|1]);
        mn[o]=min(mn[o<<1],mn[o<<1|1]);
    }
    il void reset(int l,int r,int o,int k){
        d[++top]={o,tr[o],tag[o],mn[o]};
        tr[o]=k,tag[o]=k;
        mn[o]=k-r+1;
    }
    il void pushdown(int l,int r,int o){
        if(tag[o]){
            int mid=(l+r)>>1;
            reset(l,mid,o<<1,tag[o]);
            reset(mid+1,r,o<<1|1,tag[o]);
            d[++top]={o,tr[o],tag[o],mn[o]};
            tag[o]=0;
        }
    }
    void update(int l,int r,int o,int x,int y,int k){
        if(l>=x&&r<=y){
            reset(l,r,o,k);
            return;
        }
        pushdown(l,r,o);
        int mid=(l+r)>>1;
        if(x<=mid){
            update(l,mid,o<<1,x,y,k);
        }
        if(y>mid){
            update(mid+1,r,o<<1|1,x,y,k);
        }
        pushup(o);
    }
    int find(int l,int r,int o,int k){
        if(l==r){
            return tr[o]>=k?l:n+1;
        }
        pushdown(l,r,o);
        int mid=(l+r)>>1;
        if(tr[o<<1]<k){
            return find(mid+1,r,o<<1|1,k);
        }
        return find(l,mid,o<<1,k);
    }
    int query(int l,int r,int o,int x){
        if(l==r){
            return tr[o];
        }
        pushdown(l,r,o);
        int mid=(l+r)>>1;
        if(x<=mid){
            return query(l,mid,o<<1,x);
        }
        return query(mid+1,r,o<<1|1,x);
    }
}R;
il void upd(int l,int r,int k){
    l=max(l,1),r=min(r,R.find(1,n,1,k)-1);
    if(l>r){
        return;
    }
    R.update(1,n,1,l,r,k);
}
struct SGT{
    vector<pii> tr[N<<2];
    void delet(int o,int tmp){
        while(top>tmp){
            Node u=d[top--];
            R.tr[u.o]=u.x,R.tag[u.o]=u.y,R.mn[u.o]=u.z;
        }
        for(auto [i,j]:tr[o]){
            st[j].insert(i);
        }
    }
    void update(int l,int r,int o,int x,int y,int a,int b){
        if(x<0||y>q||x>y){
            return;
        }
        if(l>=x&&r<=y){
            tr[o].eb(a,b);
            return;
        }
        int mid=(l+r)>>1;
        if(x<=mid){
            update(l,mid,o<<1,x,y,a,b);
        }
        if(y>mid){
            update(mid+1,r,o<<1|1,x,y,a,b);
        }
    }
    void solve(int l,int r,int o){
        int tmp=top;
        for(auto [i,j]:tr[o]){
            st[j].erase(st[j].find(i));
            if(st[j].find(i)!=st[j].end()){
                continue;
            }
            auto it=st[j].lower_bound(i);
            int x=*prev(it),y=*it;
            upd(x+1,i,y);
        }
        if(l==r){
            ans[l]=R.mn[1];
            return delet(o,tmp);
        }
        int mid=(l+r)>>1;
        solve(l,mid,o<<1),solve(mid+1,r,o<<1|1);
        return delet(o,tmp);
    }
}T;
void Yorushika(){
    read(n,m,q);
    rep(i,1,m){
        st[i].insert(-inf),st[i].insert(inf);
    }
    rep(i,1,n){
        read(a[i]),st[a[i]].insert(i);
        g[i].eb(a[i]);
    }
    rep(i,1,q){
        int op,x,y;read(op);
        if(op==1){
            read(x,y);
            st[y].insert(x);
            g[x].eb(y);
            T.update(1,q,1,1,i-1,x,y);
            T.update(1,q,1,i,q,x,a[x]);
            a[x]=y;
        }else{
            vis[i]=1;
        }
    }
    rep(i,1,m){
        f[1]=max(f[1],*st[i].lower_bound(1));
    }
    rep(i,2,n){
        f[i]=f[i-1];
        for(int j:g[i-1]){
            f[i]=max(f[i],*st[j].lower_bound(i));
        }
    }
    rep(i,1,n){
        R.update(1,n,1,i,i,f[i]);
    }
    top=0;
    T.solve(1,q,1);
    rep(i,1,q){
        if(vis[i]){
            printf("%d\n",ans[i]>1e9?-1:ans[i]);
        }
    }
}
signed main(){
    int t=1;
    //read(t);
    while(t--){
        Yorushika();
    }
}