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

介绍一个坨的算法，，

注意到空间很大，时间很大，dag，所以 bitset 逃不开了。

又注意到每次询问两个条件互不干扰，考虑每个单独求满足条件的点再求两者交，最后再处理最大值。所以接下来的部分都是离线处理。

对于条件二，直接求可达性即可，这一部分

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

。

对于条件一，可以改为求

a_i\le r

的点集合去掉

a_i < l

的点集合。扫一遍操作序列，维护一个序列

c

，满足处理完之前的操作后

a_{c_i}=i

，那么现在就要能做到求出一个

c

的前缀的点的集合。这一坨我只会用树状数组加上 bitset 维护，复杂度

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

。

求出来哪些点满足条件后现在要求最大值，这一部分可以参考对条件一的处理方法。同样维护序列

c

，只不过这次条件换成

b_{c_i}=i

，每次二分最大值，看后缀是否和满足条件的点有交即可。使用树状数组二分，复杂度可做到

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

，但是常数比较大。

总复杂度

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

，时间稳定，极限卡常能搞到 88 分。

说下关于空间的，对于

n\le 8\times 10^4

的部分，开两个二维 bitset，一个用来计算，另一个存结果即可。对于最后一个 subtask，存结果的只开一半，一次处理一半的询问就行，但是跑太慢过不了。

赛时 STL 版本要跑 10s，最后手写 bitset 挂了只能交破烂 STL 版本的 bitset 上去，于是特殊性质全没动，也没进一步优化，遗憾离场，，，

（剩下部分是赛后的）

注意到树状数组查询时到一些节点时其集合包含的元素不多，但合并还是

O(\frac n w)

，二分也同理。于是设置一个阈值

B

，对于第二部分当节点代表区间长度小于

B

时直接暴力合并，第三部分二分时节点长度小于

B

直接判交，可以优化到

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

，还能剔除掉一些节点优化空间，至此可以通过。

但是正解懒得写了，赛后 88 分代码：

CPP

#include<bits/stdc++.h>
using namespace std;
const int MaxN=80000;
int C,n,m,q,a[MaxN+1],b[MaxN+1];
struct Bitset{
	static const int Size=MaxN/64+1;
	unsigned long long arr[Size];
	Bitset(){clear();}
	int count()const{
		for(int i=0;i<Size;i++)if(arr[i])return 1;
		return 0;
	}
	void clear(){
		for(int i=0;i<Size;i++)arr[i]=0;
	}
	bool spfunc1(const Bitset&b)const{
		for(int i=0;i<Size;i++)if(arr[i]&b.arr[i])return true;
		return false;
	}
	void rev(int x){arr[x/64]^=(1ull<<(x%64));}
	void set(int x,bool b){if(((arr[x/64]>>(x%64))&1)!=b)arr[x/64]^=(1ull<<(x%64));}
	Bitset&operator&=(const Bitset&b){
		for(int i=0;i<Size;i++)arr[i]&=b.arr[i];
		return *this;
	}
	Bitset&operator|=(const Bitset&b){
		for(int i=0;i<Size;i++)arr[i]|=b.arr[i];
		return *this;
	}
	Bitset&operator^=(const Bitset&b){
		for(int i=0;i<Size;i++)arr[i]^=b.arr[i];
		return *this;
	}
	Bitset operator&(const Bitset&b)const{return Bitset(*this)&=b;}
	Bitset operator^(const Bitset&b)const{return Bitset(*this)^=b;}
}bt[MaxN+1],rs[MaxN+1];
vector<int>g[MaxN+1];
bool vst[MaxN+1];
int que[MaxN+1][4];
int LowBit(int x){return(x)&(-x);}
void Modify(int u,int x,int y){for(;u<=n;u+=LowBit(u))bt[u].rev(x),bt[u].rev(y);}
void Modifyo(int u,int x){for(;u<=n;u+=LowBit(u))bt[u].rev(x);}
Bitset Ask(int u){
	Bitset res;
	for(;u;u-=LowBit(u))res|=bt[u];
	return res;
}
void DFS(int u){
	if(vst[u])return;
	vst[u]=true;
	bt[u].set(u,true);
	for(int v:g[u])DFS(v),bt[u]|=bt[v];
}
int Check(int x){
	if(!rs[x].count())return 0;
	int p=__lg(n),u=(1<<p),ans=INT_MAX;
	while(p>=0){
		if(bt[u].spfunc1(rs[x])){
			ans=min(ans,u);
			u^=(1<<p);
		}
		if(p==0)return n-ans+1;
		do{p--;}while((u^(1<<p))>n);
		u^=(1<<p);
	}
	return n-ans+1;
}
void Solve(){
	cin>>n>>m>>q;
	for(int i=1;i<=n;i++)g[i].clear();
	for(int i=1,u,v;i<=m;i++){
		cin>>u>>v;
		g[u].push_back(v);
	}
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<=n;i++)cin>>b[i];
	for(int i=1;i<=n;i++)bt[i].clear();
	for(int i=1;i<=q;i++){
		cin>>que[i][0]>>que[i][1]>>que[i][2];
		if(que[i][0]==3)cin>>que[i][3];
	}
	for(int i=1;i<=n;i++)Modifyo(a[i],i);
	for(int i=1,c=0;i<=q;i++){
		if(que[i][0]==1){
			int x=que[i][1],y=que[i][2];
			Modify(a[x],x,y);
			Modify(a[y],x,y);
			swap(a[x],a[y]);
		}
		if(que[i][0]==3){
			++c;
			rs[c]=Ask(que[i][3])^Ask(que[i][2]-1);
		}
	}
	for(int i=1;i<=n;i++)vst[i]=false,bt[i].clear();
	for(int i=1;i<=n;i++)DFS(i);
	for(int i=1,c=0;i<=q;i++){
		if(que[i][0]==3){
			++c;
			rs[c]&=bt[que[i][1]];
		}
	}
	for(int i=1;i<=n;i++)bt[i].clear();
	for(int i=1;i<=n;i++)Modifyo(n-b[i]+1,i);
	for(int i=1,c=0;i<=q;i++){
		if(que[i][0]==2){
			int x=que[i][1],y=que[i][2];
			Modify(n-b[x]+1,x,y);
			Modify(n-b[y]+1,x,y);
			swap(b[x],b[y]);
		}
		if(que[i][0]==3){
			++c;
			cout<<Check(c)<<'\n';
		}
	}
}
int main(){
	cin.tie(0)->sync_with_stdio(false);
	int T;
	cin>>C>>T;
	while(T--)
		Solve();
	return 0;
}

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

文章操作

相关推荐

评论

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