[数据结构与算法][APIO2022] 游戏 题解

Description

传送门

Solution

注意到，原问题等价于加边，查询是否存在一个包含前 $k$ 个点（令其为关键点）的环，并强制在线。

算法一

令 $L_u$ 表示节点 $u$ 可达的编号最大的关键点，$R_u$ 表示可达节点 $u$ 的编号最小的关键点。那么，答案为 $1$ 当且仅当存在 $u$ 使 $L_u\ge R_u$。

每当加入一条边 $(u,v)$ 后，我们从 $u$ 出发往外 dfs，不断尝试用 $R_u$ 来更新其他的 $R$；同理，我们也从 $v$ 在反图上往外 dfs，不断尝试用 $L_v$ 来更新其他的 $L$。

一般实现的复杂度是 $O(m(n+m))$ 的，但如果我们加一个剪枝：无法更新就返回，那么每走一条边就会使一个节点的 $L,R$ 之一产生变化。而根据势能分析，每个节点的 $L,R$ 的变化次数总和是 $O(nk)$ 的，所以总复杂度其实是 $O((n+m)k)$ 的。

期望得分 $60$ 分。

算法二

既然关键点数量不多时算法一优秀，那么我们考虑将关键点变少。具体来说，我们分块，对于每个节点 $u$ 维护 $L_u,R_u$ 所在的块。当块长为 $\sqrt{k}$ 时，复杂度就是 $O((n+m)\sqrt{k})$ 的。

特别的，若 $L_u,R_u$ 属于同一个块，那么暴力更新。由于块长不大，所以这一部分的复杂度也是 $O((n+m)\sqrt{k})$ 的。

总时间复杂度 $O((n+m)\sqrt{k})$，期望得分 $[60,100]$ 分。

算法三

首先你要注意到，分块本质上就是线段树的退化版，将线段树的层数压缩到了 $2$。然而，本题并不需要依赖分块的特殊结构，于是我们考虑转而用线段树来维护。

具体来说，以 $[?1,k]$ 为值域建立线段树，将每个点 $u$ 记录在极小的包含 $[L_u,R_u]$ 的线段树节点处。我们不断地尝试用下层更新上层的点，使各个节点被记录的位置不断变深。在实现方面，我们并不需要建立线段树，只需对各个 $u$ 维护其在虚拟的线段树上对应的区间即可。

由于线段树只有 $O(\log k)$ 层，所以总复杂度 $O((n+m)\log k)$，完美解决本题。

Summary

看到本题，非常容易想到维护 $L,R$。

首先考虑 $60$ 分怎么做，根据势能分析，发现 dfs 一下的复杂度就是对的。

再考虑 $100$ 分怎么做。由于关键点的数量较少可以做，那么我们可以分块，这样就能做到较为优秀的 $O((n+m)\sqrt{k})$。

最后发现做法并不依赖分块结构的特殊性，于是转而用线段树大力维护，就能做到完美的 $O((n+m)\log k)$ 了。

本题关键在于挖掘出转移的特殊性，并考察了对分块，分治等结构的清楚认识，是一道不可多得的好题。

Code

略微压行，代码很短，只有 700 多 B。

#include <bits/stdc++.h>
using namespace std;
const int maxn=3e5+5;

int n,k,l[maxn],r[maxn];vector<int> GA[maxn],rev[maxn];
void init(int _n,int _k){
	n=_n,k=_k;
	for (int i=0;i<k;i++)  l[i]=r[i]=i;
	for (int i=k;i<n;i++)  l[i]=-1,r[i]=k;
}
bool upd(int u);
bool chk(int u,int v){
	if (l[u]>=r[v])  return true;
	int midu=(l[u]+r[u])>>1,midv=(l[v]+r[v])>>1;
	if (l[u]>midv) {l[v]=midv+1;return upd(v);}
	if (r[v]<=midu) {r[u]=midu;return upd(u);}
	return false;
}
bool upd(int u){
	for (auto v:GA[u]) {if(chk(u,v))return true;}
	for (auto v:rev[u]) {if (chk(v,u))return true;}
	return false;
}
int add_teleporter(int u,int v){GA[u].push_back(v),rev[v].push_back(u);return chk(u,v);}