专栏文章

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

__determination_
P11831题解参与者 7已保存评论 6

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
6 条
当前快照
1 份
快照标识符
@miq2n0w6
此快照首次捕获于
2025/12/03 21:57
3 个月前
此快照最后确认于
2025/12/03 21:57
3 个月前
查看原文
首先谴责一下这个民间数据啊，O(nq)O(nq) 给我跑了 76pts。然后块长调错复杂度烂完给过了。
O(n2w)O(\frac{n^2}{w}) 求传递闭包（图是拓扑图！），然后我们首先要求出 ai∈[l,r]a_i \in [l,r] 的 ii 的 bitset。
考虑分块。每个块维护这个块及以后所有点的 bitset，即 f[l,r]f_{[l,r]} 是所有满足 ai≥la_i\ge l 的 ii 构成的 bitset。内部则维护块内点的后缀并。
对于修改操作，由于 aa 是排列，直接暴力修改即可做到 O(n)O(\sqrt{n})。查询操作是直接合并整块的 bitset 并插入散块，是 O(nw+n)O(\frac{n}{w}+\sqrt{n}) 的。
这个部分的时间复杂度是 O(q(n+nw))O(q(\sqrt{n}+\frac{n}{w}))。
那么现在，我们就可以求出每个查询的有效点集合了。现在的问题是怎样求其中的 max⁡b\max b。
对于 bb 我们类似的分块，g[l,r]g_{[l,r]} 是所有满足 bi≥lb_i\ge l 的 ii 构成的 bitset。查询的求最大的 xx 使得 bi≥xb_i \ge x 的 ii 构成的 bitset 与有效点有交。O(nnw)O(\frac{n\sqrt{n}}{w})。
注意到我们散块和整块的复杂度极度不平衡，仔细分析一下：
  • 对于整块，复杂度 O(n2Bw)O(\frac{n^2}{Bw})。修改复杂度为 O(nB)O(\frac{n}{B})。
  • 对于散块，修改和查询都是 O(B)O(B)。
取 B=10000B=10000，随便跑啊。
AC Link.
更新：官方数据不是出来了吗，太恐怖了，给我原来的代码干 T 了，加一点小卡常就好了（甚至可以说是一些常识？）
  1. 去掉 #define int long long。
  2. #define endl '\n'。
AC Link. 也就 2k 出头，不长的。
update:感谢hepp指出了原题解的错误。在上面的代码中我使用 .size() 来判断这个 bitset 里是否有 1，但是事实上 .size() 返回的是大小而非 1 的个数。导致复杂度退化。但是这玩意能给过了也是神了。应当改为 .count() 或 .any()。
新的提交记录。
新的代码：
CPP
#include<bits/stdc++.h>
// #define int long long
#define endl '\n'
using namespace std;
const int mod=998244353,inf=0x3f3f3f3f3f3f3f3f;
const int N=1e5+10,M=2e5+10;
bitset<N>to[N];
vector<int>e[N];
int n,m,q;
const int B1=400,B2=10000;
bitset<N>f[N/B1+10];
bitset<N>g[N/B2+10];
int fid[N],gid[N];
int a[N],b[N],br[N],ar[N];
void solve()
{
	cin >> n >> m >> q;
	for ( int i = 1 ; i <= n ; i++ )
		e[i].clear(),to[i]=0;
	for ( int i = 1 ; i <= n ; i++ )
		to[i][i]=1;
	while(m--)
	{
		int u,v;cin >> u >> v;
		e[u].push_back(v);
	}
	for ( int i = 1 ; i <= n ; i++ ){
		cin >> a[i];ar[a[i]]=i;
	}
	for ( int i = 1 ; i <= n ; i++ ){
		cin >> b[i];br[b[i]]=i;
	}
	for ( int i = n ; i >= 1 ; i-- )
		for ( auto v:e[i] )to[i]|=to[v];
	for ( int i = 1 ; i <= n+1 ; i++ )
		fid[i]=(i+B1-1)/B1,
		gid[i]=(i+B2-1)/B2;
	for ( int i = 1 ; i <= fid[n]+1 ; i++ )f[i]=0;
	for ( int i = 1 ; i <= gid[n]+1 ; i++ )g[i]=0;
	for ( int i = 1 ; i <= n ; i++ )
		f[fid[a[i]]][i]=1,
		g[gid[b[i]]][i]=1;
	for ( int i = fid[n]-1 ; i >= 1 ; i-- )
		f[i]|=f[i+1];
	for ( int i = gid[n]-1 ; i >= 1 ; i-- )
		g[i]|=g[i+1];
	while(q--)
	{
		int op,x,y,l,r;
		cin >> op;
		if(op==1)
		{
			cin >> x >> y;
			for ( int i = 1 ; i <= fid[a[x]] ; i++ )f[i][x]=0;
			for ( int i = 1 ; i <= fid[a[y]] ; i++ )f[i][x]=1;
			for ( int i = 1 ; i <= fid[a[y]] ; i++ )f[i][y]=0;
			for ( int i = 1 ; i <= fid[a[x]] ; i++ )f[i][y]=1;
			swap(a[x],a[y]);
			swap(ar[a[x]],ar[a[y]]);
		}else if(op==2){
			cin >> x >> y;
			for ( int i = 1 ; i <= gid[b[x]] ; i++ )g[i][x]=0;
			for ( int i = 1 ; i <= gid[b[y]] ; i++ )g[i][x]=1;
			for ( int i = 1 ; i <= gid[b[y]] ; i++ )g[i][y]=0;
			for ( int i = 1 ; i <= gid[b[x]] ; i++ )g[i][y]=1;
			swap(b[x],b[y]);
			swap(br[b[x]],br[b[y]]);
		}else{
			cin >> x >> l >> r;
			bitset<N>toa;toa=0;
			toa=f[fid[l]+1];
			for ( int i = l ; i <= min(n,fid[l]*B1) ; i++ )
				toa[ar[i]]=1;
			toa^=f[fid[r+1]+1];
			for ( int i = r+1 ; i <= min(n,fid[r+1]*B1) ; i++ )
				toa[ar[i]]=1-toa[ar[i]];
			toa&=to[x];
			int flg=0;
			for ( int i = gid[n] ; i >= 1 ; i-- )
			{
				if((g[i]&toa).any())
				{
					for ( int j = min(n,i*B2) ; j >= (i-1)*B2+1 ; j-- )
						if(toa[br[j]])
						{
							flg=1;
							cout << j << endl;
							break;
						}
				}
				if(flg)break;
			}
			if(!flg)cout << 0 << endl;
		}
	}
}
signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int c,T;cin >> c >> T;
	while(T--)solve();
	return 0;
}

评论

共 6 条评论，欢迎与作者交流。

正在加载评论...