题解：P11831 [省选联考 2025] 追忆

解法

首先发现

a

和

b

的范围都不超过

n

，非常果断地对

a

和

b

的值域分块，分别维护每个值在序列中的出现位置。这样就能做到

O(1)

修改了。

接着看询问操作，维护一个点集

S

表示能够成为答案的点。

为了保证

l \leq a_y \leq r

，先将满足条件的点通过分块

O(n)

加入点集，再考虑可达性。这个可达性目前最优秀的做法是用 bitset 优化

O(\frac{n^2}{w})

算出来。

等等？bitset？忽然想到，我们之前的分块操作以及计算答案的做法都可以用 bitset 优化，于是我们询问操作计算

l \leq a_y \leq r

的点的步骤的时间优化成了

O(\frac{n}{\sqrt w})

。

接下来就简单了，我们枚举答案所在的块，然后

O(\frac{n}{w})

的时间检验，最后在块内暴力算答案即可。

总时间复杂度为

O(\frac{nq}{\sqrt w})

，块长实测后感觉

7000

跑得最快。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
#define endl '\n' 
const int N=1e5+5,key=7000,sqN=120;
int n,m,q,tot,a[N],b[N],posa[N],posb[N];
int pos[N],lm[sqN],rm[sqN],op,x,y,l,r,res;
bitset<N> d[N],sa[sqN],sb[sqN],ans,emy;
vector<int> e[N];
inline int read(){
	int x=0,f=1;char ch=getchar();
	for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
	for(;isdigit(ch);ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
	return x*f;}
inline void slove(){
	n=read(),m=read(),q=read(),tot=(n-1)/key+1;
	for(int i=1;i<=n;i++) pos[i]=(i-1)/key+1,e[i].clear();
	for(int i=1;i<=tot;i++) lm[i]=rm[i-1]+1,rm[i]=min(n,i*key),sa[i]=sb[i]=emy;
	for(int i=1,u,v;i<=m;i++) u=read(),v=read(),e[u].push_back(v);
	for(int i=n;i>=1;i--){ d[i]=emy,d[i][i]=1; for(int v:e[i]) d[i]|=d[v];}
	for(int i=1;i<=n;i++) a[i]=read(),posa[a[i]]=i,sa[pos[a[i]]][i]=1;
	for(int i=1;i<=n;i++) b[i]=read(),posb[b[i]]=i,sb[pos[b[i]]][i]=1;
	for(;q--;){ op=read();
		if(op==1){ x=read(),y=read();
			sa[pos[a[x]]][x]=sa[pos[a[y]]][y]=0,
			swap(a[x],a[y]),posa[a[x]]=x,posa[a[y]]=y,
			sa[pos[a[x]]][x]=sa[pos[a[y]]][y]=1;}
		else if(op==2){ x=read(),y=read();
			sb[pos[b[x]]][x]=sb[pos[b[y]]][y]=0,
			swap(b[x],b[y]),posb[b[x]]=x,posb[b[y]]=y,
			sb[pos[b[x]]][x]=sb[pos[b[y]]][y]=1;}
		else if(op==3){ x=read(),l=read(),r=read(),res=0,ans=emy;
			if(pos[l]==pos[r]) for(int i=l;i<=r;i++) ans[posa[i]]=1;
			else{ for(int i=l;i<=rm[pos[l]];i++) ans[posa[i]]=1;
				for(int i=lm[pos[r]];i<=r;i++) ans[posa[i]]=1;
				for(int i=pos[l]+1;i<=pos[r]-1;i++) ans|=sa[i];
			} ans&=d[x];for(int i=tot;i>=1;i--)
				if((sb[i]&ans).any()){res=i;break;}
			if(!res){cout<<0<<endl;continue;}
			for(int i=rm[res];i>=lm[res];i--)
				if(ans[posb[i]]) {cout<<i<<endl;break;}
		}
	}
}
int main(){
	for(int c=read(),t=read();t--;) slove();
	return 0;
}

希望能对大家有所帮助。

题解：P11831 [省选联考 2025] 追忆

文章操作

解法

代码

相关推荐

评论

题解：P11831 [省选联考 2025] 追忆