前言

考场上想到了一个复杂度很不优秀的做法，觉得过不了，没打完就弃了。现在打了一下发现能过洛谷全部民间数据。悲。

做法

我的做法时间复杂度是

O(nq)

，但是会乘上

\frac{1}{\sqrt{w}}

的常数。卡过了所有民间数据，不保证官方数据能过。

首先我们用bitset存一下每个点能到达的点的编号的集合，然后再开两个分块 bitset 数组分别存储一下每个

a_i

和

b_i

在某个范围

B

内的

i

的集合。

对于两类修改，可以非常轻松地

O(1)

改掉。

而对于询问来说，我们先从高到低枚举答案在哪个块里，然后再枚举答案在这个块里的哪里。不规范地表述一下，单次查询复杂度

O(\frac{n^2}{wB}+B)

，所以

B

取

\frac{n}{\sqrt{w}}

最优。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+2;
const int blen=sqrt((long long)N*(long long)N/64)+2;
bitset<N>s[N],clr,sa[114],sb[114],fd;
int bnum;
int a[N],b[N],pa[N],pb[N];
int n,m,q;
int bel[N],belL[N],belR[N],blL[114],blR[114];
vector<int>e[N];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int kkksc03,T;
	cin>>kkksc03>>T;
	while(T--){
		cin>>n>>m>>q;
		bnum=(n-1)/blen+1;
		for(int i=1;i<=n;i++)bel[i]=(i-1)/blen+1;
		for(int i=1;i<=bnum;i++)blL[i]=blR[i-1]+1,blR[i]=blen*i;
		blR[bnum]=n;
		for(int i=1;i<=n;i++)belL[i]=blL[bel[i]],belR[i]=blR[bel[i]];
		for(int i=1;i<=n;i++)e[i].clear();
		for(int i=1;i<=m;i++){
			int u,v;cin>>u>>v;
			e[u].push_back(v);
		}
		for(int i=1;i<=bnum;i++){
			sa[i]=sb[i]=clr;
		}
		for(int x=n;x>=1;x--){
			s[x]=clr;
			s[x].set(x,1);
			for(int y:e[x]){
				s[x]|=s[y];
			}
		}
		for(int i=1;i<=n;i++){
			cin>>a[i];
			pa[a[i]]=i;
			sa[bel[a[i]]].set(i,1);
		}
		for(int i=1;i<=n;i++){
			cin>>b[i];
			pb[b[i]]=i;
			sb[bel[b[i]]].set(i,1);
		}
		while(q--){
			int op;cin>>op;
			if(op==1){
				int x,y;
				cin>>x>>y;
				sa[bel[a[x]]].set(x,0);
				sa[bel[a[y]]].set(y,0);
				swap(a[x],a[y]);
				pa[a[x]]=x;pa[a[y]]=y;
				sa[bel[a[x]]].set(x,1);
				sa[bel[a[y]]].set(y,1);
			}
			if(op==2){
				int x,y;
				cin>>x>>y;
				sb[bel[b[x]]].set(x,0);
				sb[bel[b[y]]].set(y,0);
				swap(b[x],b[y]);
				pb[b[x]]=x;pb[b[y]]=y;
				sb[bel[b[x]]].set(x,1);
				sb[bel[b[y]]].set(y,1);
			}
			if(op==3){
				int x,l,r;
				cin>>x>>l>>r;
				int pos=0,ans=0;
				fd=clr;
				if(bel[l]==bel[r]){
					for(int i=l;i<=r;i++)fd.set(pa[i],1);
				}
				else{
					for(int i=l;i<=belR[l];i++)fd.set(pa[i],1);
					for(int i=belL[r];i<=r;i++)fd.set(pa[i],1);
					for(int i=bel[l]+1;i<=bel[r]-1;i++)fd|=sa[i];
				}
				fd&=s[x];
				for(int i=bnum;i>=1;i--){
					if((sb[i]&fd).any()){
						pos=i;
						break;
					}
				}
				if(!pos){
					cout<<0<<"\n";
					continue;
				}
				for(int i=blR[pos];i>=blL[pos];i--){
					if(fd[pb[i]]){
						ans=i;
						break;
					}
				}
				cout<<ans<<"\n";
			}
		}
	}
	return 0;
}

我考场但凡打一下呢……

题解：P11831 [省选联考 2025] 追忆（民间数据）

文章操作

前言

做法

代码

相关推荐

评论

题解：P11831 [省选联考 2025] 追忆（民间数据）