自动搬运

查看原文

来自洛谷，原作者为

	Inui_Sana ばか！へんたい！うるさい！⠀

搬运于2025-08-24 22:27:55，当前版本为作者最后更新于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();
	}
}