自动搬运

查看原文

来自洛谷，原作者为

	disangan233 ディストピア

搬运于2025-08-24 22:12:27，当前版本为作者最后更新于2019-10-28 13:04:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

瞎扯

月赛上肝了一个多小时这个题的具体实现，细节爆炸啊 qaq

做法

做法：线段树+set

考虑一种巧妙的维护：对于每一个 $a_i$，维护 $b_i=\max j<i$，使得 $a_i$ 与 $a_j$ 发生关系（可互逆），且 $\forall j<k<i,a_k \not =a_i$。

那么对于一个询问区间 $l,r$，因为每一个相同的 $a_i$ 只有第一个对 $b_i$ 有贡献，所以答案即为 $\max \{q_i|l\leq i\leq r\}$，使用线段树维护，这样就可以通过只有询问的点了。

考虑修改操作，维护 $p_i$ 的逆数组 $ap_i$，因为是单点修改，只需要更新修改位置后的所有 $a_i,p_{a_i},ap_{a_i}$ 即可，用对每一个值开 set 维护，值的修改使用 .insert()，.erase()，.lower_bound()。更新结束后按照预处理的方法更新即可，时间复杂度 $O(n\log n)$。

具体细节见代码实现。

强烈建议：一定要写函数！！！！

代码实现

#pragma GCC optimize(2,3,"Ofast","unroll-loops")
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define re register int
#define db double
#define in inline
namespace fast_io
{
	char buf[1<<12],*p1=buf,*p2=buf,sr[1<<23],z[23],nc;int C=-1,Z=0,Bi=0;
	in char gc() {return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++;}
	in ll read()
	{
		ll x=0,y=1;while(nc=gc(),(nc<48||nc>57)&&nc!=-1)if(nc==45)y=-1;Bi=1;
		x=nc-48;while(nc=gc(),47<nc&&nc<58)x=(x<<3)+(x<<1)+(nc^48),Bi++;return x*y;
	}
	in db gf() {re a=read(),b=(nc!='.')?0:read();return (b?a+(db)b/pow(10,Bi):a);}
	in int gs(char *s) {char c,*t=s;while(c=gc(),c<32);*s++=c;while(c=gc(),c>32)*s++=c;return s-t;}
	in void ot() {fwrite(sr,1,C+1,stdout);C=-1;}
	in void flush() {if(C>1<<22) ot();}
	template <typename T>
	in void write(T x,char t)
	{
		re y=0;if(x<0)y=1,x=-x;while(z[++Z]=x%10+48,x/=10);
		if(y)z[++Z]='-';while(sr[++C]=z[Z],--Z);sr[++C]=t;flush();
	}
	in void write(char *s) {re l=strlen(s);for(re i=0;i<l;i++)sr[++C]=*s++;sr[++C]='\n';flush();}
};
using namespace fast_io;
const int N=5e5+5;
int n,m,a[N],b[N],ab[N],c[N],p[N],ap[N],mx[N<<2],lst[N];
set<int>s[N];
#define ls(x) (x<<1)
#define rs(x) (x<<1|1)
#define mid ((l+r)>>1)
in void push_up(re x) {mx[x]=max(mx[ls(x)],mx[rs(x)]);}
void build(re p,re l,re r)
{
	if(l==r) return mx[p]=b[l],void();
	build(ls(p),l,mid);build(rs(p),mid+1,r);push_up(p);
}
void update(re p,re l,re r,re x,re y)
{
	if(l==r) return mx[p]=y,void();
	(x<=mid)?update(ls(p),l,mid,x,y):update(rs(p),mid+1,r,x,y);push_up(p);
}
int query(re p,re l,re r,re ql,re qr)
{
	if(ql<=l&&r<=qr) return mx[p];
	if(ql>mid) return query(rs(p),mid+1,r,ql,qr);
	if(qr<=mid) return query(ls(p),l,mid,ql,qr);
	return max(query(rs(p),mid+1,r,ql,qr),query(ls(p),l,mid,ql,qr));
}
#define lb lower_bound
in void update(re x,re y) {update(1,1,n,x,y);}
in int get(re x)
{
	auto it=s[a[x]].lb(x);re pre=0,pp=0,v=p[a[x]],av=ap[a[x]];
	if(it!=s[a[x]].begin()) pre=*--it;
	if((it=s[v].lb(x))!=s[v].begin()) pp=*--it;
	if((it=s[av].lb(x))!=s[av].begin()) pp=max(pp,*--it);
	return pp>pre?pp:0;
}
in void upd(set<int>::iterator it) {update(*it,b[*it]=get(*it));}
in void erase(re x)
{
	s[a[x]].erase(x),b[x]=0;auto it=s[a[x]].lb(x);re v=p[a[x]],av=ap[a[x]];
	if(it!=s[a[x]].end()) upd(it);
	if((it=s[v].lb(x))!=s[v].end()) upd(it);
	if((it=s[av].lb(x))!=s[av].end()) upd(it);
}
in void add(re x,re y)
{
	a[x]=y,s[a[x]].insert(x);auto it=s[a[x]].lb(x);
	re v=p[a[x]],av=ap[a[x]];upd(it);it++;
	if(it!=s[a[x]].end()) upd(it);
	if((it=s[v].lb(x))!=s[v].end()) upd(it);
	if((it=s[av].lb(x))!=s[av].end()) upd(it);
}
int main()
{
	n=read(),m=read();
	for(re i=1;i<=n;i++) p[i]=read(),ap[p[i]]=i;
	for(re i=1;i<=n;i++) a[i]=read();
	for(re i=1;i<=n;i++) 
	{
		s[a[i]].insert(i);re v=p[a[i]],pp=max(lst[v],lst[ap[a[i]]]);
		if(pp>lst[a[i]]) update(1,1,n,i,b[i]=pp);lst[a[i]]=i;
	}
	build(1,1,n);
	while(m--)
	{
		re op=read(),x=read(),y=read();
		if(op==2) (query(1,1,n,x,y)>=x)?write("Yes"):write("No");
		else erase(x),add(x,y);
	}
	return ot(),0;
}
//Author: disangan233
//In my dream's scene,I can see the everything that in Cyaegha.