Day1 T1 集合(set)
容易发现两个序列等价当且仅当，所有数字在序列中出现位置的集合构成集族相等。
考虑哈希，对于一个集合 \(S\)，令它的哈希值为 \(f(S) = (\sum\limits_{x \in S} B^x) \mod P\)，上述条件只需做两遍哈希即可满足。
使用莫队维护所有哈希值，时间复杂度 \(O(q\sqrt n \log n)\)。
注意到我们只需判断 Yes 和 No，并且答案具有单调性。设 \(ans_l\) 表示以 \(l\) 为区间左端点，最大的合法右端点。双指针预处理 \(ans\) 即可。
时间复杂度 \(O(n \log n + q)\)。
Code
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;
using LL = long long;
const int N = 2e5 + 5, M = 6e5 + 5;
const int Base[2] = {int(1e9) + 7, int(1e9) + 9};
const LL Mod = 1e9 + 3;
LL Mul (LL x, LL y) { return x * y % Mod; }
LL Pow (LL x, LL y) {
LL res = 1;
while (y) {
if (y & 1) {
res = Mul(res, x);
}
x = Mul(x, x);
y >>= 1;
}
return res;
}
int n, m, q, ans[N];
struct Array {
int a[N][3];
LL all_val, hval[M];
void Insert (LL &val, LL x, int o) { val = (val + Pow(Base[o], x)) % Mod; }
void Erase (LL &val, LL x, int o) { val = (val - Pow(Base[o], x) + Mod) % Mod; }
LL Add (int i) {
for (int j = 0; j < 3; ++j) {
Erase(all_val, hval[a[i][j]], 1);
Insert(hval[a[i][j]], i, 0);
Insert(all_val, hval[a[i][j]], 1);
}
return all_val;
}
void Remove (int i) {
for (int j = 0; j < 3; ++j) {
Erase(all_val, hval[a[i][j]], 1);
Erase(hval[a[i][j]], i, 0);
Insert(all_val, hval[a[i][j]], 1);
}
}
void Init () {
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < 3; ++j) {
cin >> a[i][j];
}
}
}
} A, B;
int main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m >> q;
A.Init(), B.Init();
for (int i = 1, j = 1; i <= n; ++i) {
for (; j <= n && A.Add(j) == B.Add(j); ++j) {
}
if (j <= n) {
A.Remove(j), B.Remove(j);
}
ans[i] = j;
A.Remove(i), B.Remove(i);
}
for (int l, r; q--; ) {
cin >> l >> r;
cout << (ans[l] > r ? "Yes" : "No") << '\n';
}
return 0;
}
Day1 T2 百万富翁(richest)
\(\text{Case 1}\) 两两询问即可。
\(\text{Case 2}\) 考虑 \(\text{dp}\) 决策点，设 \(f_{i, j}\) 表示我们要找 \(i\) 个人中最有钱的人，可以使用 \(j\) 次请求，最少需要的查询数，转移考虑枚举 \(k\) 表示将这些人平均分为 \(k\) 组（容易证明均分一定是最优的）：
\(f_{i, j} = \min\limits_{k} \{ f(k, j - 1) + \frac{\lfloor \frac{i}{k} \rfloor(\lfloor \frac{i}{k} \rfloor - 1)}{2} \times k + (i \bmod k)\lfloor \frac{i}{k} \rfloor \}\)
直接 \(\text{dp}\) 时间复杂度 \(O(n^2t)\)，但实际上不难发现 \(n = 10^6\) 时前 \(4\) 次最优决策都是 \(k = \frac{n}{2}\)，于是我们可以直接从 \(n = 62500\) 开始跑，打表发现决策点分别为 \(\{ 500000, 250000, 125000, 62500, 20833, 3472, 183, 1 \}\)，于是这道题就做完了。
实际上也可以将枚举组数改为枚举每组人数，这样做的优势是可以快速得到一组解（大概可以获得 \(90\) 分左右），劣势是不一定最优，需要手动调整才能得到满分。
Code
#include "richest.h"
#include <algorithm>
#include <numeric>
#include <cassert>
using namespace std;
vector<int> get_max (vector<vector<int>> vec) {
int t = vec.size();
vector<int> a, b;
for (int k = 0; k < t; ++k) {
int cnt = vec[k].size();
for (int i = 0; i < cnt; ++i) {
for (int j = i + 1; j < cnt; ++j) {
a.push_back(vec[k][i]), b.push_back(vec[k][j]);
}
}
}
vector<int> c = ask(a, b);
vector<int> res;
for (int k = t - 1; ~k; --k) {
int cnt = vec[k].size();
vector<int> win(cnt);
for (int i = cnt - 1; ~i; --i) {
for (int j = cnt - 1; j > i; --j) {
if (c.back() == a[c.size() - 1]) ++win[i];
if (c.back() == b[c.size() - 1]) ++win[j];
c.pop_back();
}
}
res.push_back(vec[k][find(win.begin(), win.end(), cnt - 1) - win.begin()]);
}
reverse(res.begin(), res.end());
return res;
}
int richest (int N, int T, int S) {
if (N == 1000 && T == 1 && S == 499500) {
vector<int> v(N);
iota(v.begin(), v.end(), 0);
return get_max(vector<vector<int>>{v}).back();
}
else {
assert(N == int(1e6) && T == 20 && S == int(2e6));
const vector<int> point{500000, 250000, 125000, 62500, 20833, 3472, 183, 1};
vector<int> now(N);
iota(now.begin(), now.end(), 0);
for (int i = 0; i < point.size(); ++i) {
int cnt = now.size(), p = point[i], low = cnt / p, cur = 0;
vector<vector<int>> des(p);
for (int j = 0; j < p; ++j) {
for (int k = 0; k < low; ++k) {
des[j].push_back(now[cur++]);
}
}
for (int j = 0; cur < cnt; ++j) {
des[j].push_back(now[cur++]);
}
now = get_max(des);
}
assert(now.size() == 1);
return now.back();
}
}
Day1 T3 树的定向(tree)
对于某一时刻，假设已经确定了若干边的方向。对于一个形如“\(a\) 不能到达 \(b\)”的限制 \((a, b)\)，若路径 \(a \rightarrow b\) 上存在一条边已经定向且方向与路径相反，则该限制已经满足，删除即可。若路径 \(a \rightarrow b\) 上只存在一条边未定向，则这条边必须与路径方向相反，我们将这条边加入待处理的边的队列中，并删除这个限制。
考虑如果这两类限制都不存在，我们一定可以任意定向一条边，由于题目要求字典序最小，所以我们会将第一条未定向的边定成 \(0\)。
证明：我们知道任意限制 \((a, b)\) 都满足 \(\text{path}(u, v)\) 上未定向的边不少于 \(2\) 条，所以对所有已定向的边缩点，然后黑白染色，对于未定向的边全部黑点连向白点/白点连向黑点，这给出了两个对偶的合法解，因此任意定向一条边后仍然存在解。
考虑如何动态维护每条限制 \((a, b)\) 上边的情况。由于可重复限制，我们拆成 \(t = O(1)\) 个形如 \((x, k, o = 0/1)\) 的条件，它表示在 \(x\) 的 \(2^k\) 级祖先链上，希望有至少一条边是向上/向下定向。若这 \(t\) 个条件都不满足，说明方案不合法。
对于一个条件 \((x, k, o = 0/1)\)，若某一时刻 \(x\) 的 \(2^k\) 级祖先链上存在一条边和 \(o\) 方向相同，则它所属限制已经得到满足。若 \(x\) 的 \(2^k\) 级祖先链上只有一条未定向边，检查所属限制的其他条件，是否加起来只有一条未定向边，如果是将这条边加入队列，检查次数 \(O(1)\)。
可以维护 \(ed_{i, k} = (true/false, id)\) 表示 \(i\) 的 \(2^k\) 级祖先链上是否只有 \(\le 1\) 条边，如果是且恰好有一条边，记录这条边的编号。\(dir_{i, k, 0/1} = true/false\) 表示 \(i\) 的 \(2^k\) 级祖先链上是否存在向上/向下的边。对于静态的情况，这两个数组容易倍增转移。
容易说明对于一对 \((i, k)\)，\(ed_{i, k}, dir_{i, k}\) 的修改次数都是 \(O(1)\) 的，所以我们考虑只在值发生变动的情况下更新下一层，对于每个状态预处理下一层的所有状态是简单的。这样访问到的状态总数是 \(O(n \log n)\) 的。
时间复杂度 \(O(n \log n)\)。
Code
#include <iostream>
#include <vector>
#include <cassert>
#include <cmath>
#include <set>
#include <queue>
using namespace std;
using Pii = pair<int, int>;
const int N = 5e5 + 5, M = 19;
int cid, n, m;
int eu[N], ev[N], dep[N];
bool vis[N], ans[N];
int la[N], lb[N], icnt[N];
set<pair<int, bool>> sp[N];
bool done[N];
int fa[N][M];
pair<bool, int> ed[N][M];
bool dir[N][M][2];
vector<Pii> e[N];
vector<Pii> stv[N][M];
vector<int> st[N][M][2];
queue<pair<int, bool>> lq;
void Build (int u) {
dep[u] = dep[fa[u][0]] + 1;
for (int k = 1; k < M; ++k) {
fa[u][k] = fa[fa[u][k - 1]][k - 1];
}
for (auto i : e[u]) {
int v = i.first, id = i.second;
if (v != fa[u][0]) {
ed[v][0] = {true, id};
fa[v][0] = u, Build(v);
}
}
}
int Lca (int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int k = M - 1; ~k; --k) {
if (dep[u] - dep[v] >= (1 << k)) {
u = fa[u][k];
}
}
if (u == v) return u;
for (int k = M - 1; ~k; --k) {
if (fa[u][k] != fa[v][k]) {
u = fa[u][k], v = fa[v][k];
}
}
return fa[u][0];
}
int Kth_fa (int u, int x) {
assert(x >= 0);
for (int k = M - 1; ~k; --k) {
if ((x >> k) & 1) {
u = fa[u][k];
}
}
return u;
}
void Check_limit (int i) {
if (!icnt[i] && sp[i].size() == 1) {
pair<int, bool> req = *sp[i].begin();
if (!vis[req.first]) {
vis[req.first] = 1;
lq.push(req);
}
done[i] = true;
}
}
void Update (int x, int k, int o = -1) {
pair<bool, int> _ed;
bool _dir[2];
if (k == 0) {
_ed = {true, 0};
_dir[o] = 1, _dir[o ^ 1] = 0;
}
else {
if (ed[x][k - 1].first == true && ed[fa[x][k - 1]][k - 1].first == true && (!ed[x][k - 1].second || !ed[fa[x][k - 1]][k - 1].second)) {
_ed = {true, ed[x][k - 1].second | ed[fa[x][k - 1]][k - 1].second};
}
else {
_ed = {false, 0};
}
_dir[0] = dir[x][k - 1][0] || dir[fa[x][k - 1]][k - 1][0];
_dir[1] = dir[x][k - 1][1] || dir[fa[x][k - 1]][k - 1][1];
}
if (_ed != ed[x][k] || _dir[0] != dir[x][k][0] || _dir[1] != dir[x][k][1]) {
for (int o = 0; o < 2; ++o) {
for (auto i : st[x][k][o]) {
if (_dir[o]) done[i] = true;
if (done[i] == true) continue;
if (ed[x][k].first == false && _ed.first == true) {
--icnt[i];
sp[i].insert({_ed.second, o});
Check_limit(i);
}
else if (ed[x][k].second && !_ed.second) {
sp[i].erase({ed[x][k].second, o});
Check_limit(i);
}
}
}
ed[x][k] = _ed, dir[x][k][0] = _dir[0], dir[x][k][1] = _dir[1];
for (auto s : stv[x][k]) {
Update(s.first, s.second);
}
}
}
int main () {
cin.tie(0)->sync_with_stdio(0);
cin >> cid >> n >> m;
for (int i = 1, u, v; i < n; ++i) {
cin >> eu[i] >> ev[i];
e[eu[i]].push_back({ev[i], i});
e[ev[i]].push_back({eu[i], i});
}
for (int i = 1; i <= m; ++i) {
cin >> la[i] >> lb[i];
}
Build(1);
for (int i = 1; i <= m; ++i) {
int tp = Lca(la[i], lb[i]);
auto Add_limit = [&](int x, int k, int o) -> void {
st[x][k][o].push_back(i);
if (ed[x][k].first == true) {
sp[i].insert({ed[x][k].second, o});
}
else {
++icnt[i];
}
};
auto Add = [&](int x, int y, int o) -> void {
if (x == y) return;
int k = int(log2(dep[x] - dep[y]));
Add_limit(x, k, o);
if (dep[x] - dep[y] == (1 << k)) return;
Add_limit(Kth_fa(x, dep[x] - dep[y] - (1 << k)), k, o);
};
Add(la[i], tp, 1);
Add(lb[i], tp, 0);
Check_limit(i);
}
for (int k = 1; k < M; ++k) {
for (int i = 1; i <= n; ++i) {
if (!fa[i][k]) continue;
stv[i][k - 1].push_back({i, k});
stv[fa[i][k - 1]][k - 1].push_back({i, k});
}
}
int cur = 1;
for (int i = 1; i < n; ++i, lq.pop()) {
if (lq.empty()) {
while (vis[cur]) ++cur;
assert(cur < n);
lq.push({cur, eu[cur] == fa[ev[cur]][0]});
cur++;
}
pair<int, bool> tp = lq.front();
int id = tp.first;
bool o = tp.second;
ans[id] = o ^ (eu[id] == fa[ev[id]][0]);
int u = (ev[id] == fa[eu[id]][0] ? eu[id] : ev[id]);
Update(u, 0, o);
}
for (int i = 1; i < n; ++i) {
cout << ans[i];
}
cout << '\n';
return 0;
}
Day2 T1 分数(fraction)
令 \(n \le m\)，题意等价于我们有初始状态 \((p, q) = (0, 1)\)，我们可以进行如下操作若干次（其中 \(u\) 为任意正整数）：
- \((p, q) \gets (q, 2uq + p)\)
问能到达的状态总数，在这过程中始终要求 \(p \le n, q \le m\)。考虑模拟这一过程，注意到无需判重，并且能够到达的状态数较少，可以得到一个 \(O(ans)\) 的做法，可以获得 \(90 \sim 95\) 分。
我们可以将最终状态 \((p, q)\) 所代表分数 \(\frac{p}{q}\) 写成连分数形式 \([2u_1, 2u_2, \ldots, 2u_m]\)，容易发现这个序列从后往前与搜索时给出的参数 \(u\) 是相同的。
考虑序列中最大的一项 \(x = \max u_i\)，如有多项取靠后的，我们将这一项待定，最终状态可以表示为 \((ax+b, cx + d)\)，我们在此时可以 \(O(1)\) 确定 \(x\) 的取值有多少个。这样我们一次就搜出了多个解。
具体而言我们维护当前可能的最小 \(x\)，并且记录 \((p, q) / (a, b, c, d)\)，如果当前位置填一个最小 \(x\) 都不满足要求就剪掉。
这样状态数大大减少，在 \(n,m \le 3 \times 10^7\) 时状态数约为 \(8 \times 10^7\)。
Code
#include <iostream>
using namespace std;
using LL = long long;
const int Inf = 1e9;
int n, m;
LL ans;
int divi (int x, int y) { return !y ? Inf : x / y; }
bool Dfs2 (int a, int b, int c, int d, int low) {
LL cnt = max(0, min(divi(n - b, a), divi(m - d, c)) - low + 1);
cnt += max(0, min(divi(n - b, a), divi(n - d, c)) - low + 1);
if (!cnt) return 0;
ans += cnt;
for (int u = 1; ; ++u) {
bool t = Dfs2(c, d, 2 * u * c + a, 2 * u * d + b, max(low, u));
if (!t) {
break;
}
}
return 1;
}
bool Dfs (int p, int q, int low) {
if (!Dfs2(0, q, 2 * q, p, low)) return 0;
for (int u = 1; ; ++u) {
if (!Dfs(q, 2 * u * q + p, max(low, u + 1))) {
break;
}
}
return 1;
}
int main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
if (n > m) swap(n, m);
Dfs(0, 1, 1);
cout << ans << '\n';
return 0;
}
Day2 T2 登山(mountain)
设 \([tl_i, tr_i]\) 为从 \(i\) 点开始冲刺，允许的终点深度范围。\(lim_i\) 表示到达 \(i\) 点之后所有冲刺点深度 \(\le lim_i\)，\(v_{i \rightarrow j}\) 表示从 \(i\) 滑落到点 \(j\) 时，经过点的最严格 \(lim\) 限制，即 \(v_{i \rightarrow j} = \min\limits_{u \in \text{path}(i, j)} lim_u\)。
设 \(f_i\) 表示冲刺到 \(i\) 点的方案数，答案为 \(f_{2 \sim n}\)。考虑暴力从上往下转移，假设当前 \(\text{dfs}\) 到点 \(u\)，且我们已经算出 \(f_u\) 的值，在 \(u\) 子树内枚举上一个冲刺到的点 \(i\)，在 \(i\) 子树内枚举从 \(i\) 滑落到的点 \(j\)，若 \(dep_u \in [l_r, \min(v_{i \rightarrow j}, r_j)]\)，则 \(f_i \gets f_i + f_u\)，时间复杂度 \(O(n^3)\)。
考虑优先枚举 \(j\)，对于一个 \(i\)，它能冲刺到一段深度区间为 \([l_j, \min(v_{i \rightarrow j}, r_j)]\) 的祖先链。做前缀和，设 \(j\) 所在祖先链上深度为 \(i\) 的点到根的权值和为 \(s_i\)，那么贡献就是 \(s_{\min(v_{i \rightarrow j}, r_j)} - s_{l_j - 1}\)（并且我们要求 \(l_j - 1 \le v_{i \rightarrow j}\)），即可做到 \(O(n^2)\)。
观察到 \(i\) 不断往上跳时，按照 \(\min(v_{i \rightarrow j}, r_j)\) 不同划分成若干段。一方面 \(\min\) 取 \(r_j\) 的段数显然是 \(O(n)\) 的，另一方面我们让 \(v_{i \rightarrow j}\) 对应一个深度最大的 \(x\) 使得 \(lim_x = v_{i \rightarrow j}\)，从 \(x\) 继续往上跳段数 \(O(n)\)，此时 \(j \rightarrow x\) 的路径长什么样无关，只需对于 \(x\) 预处理即可。这启发我们拆贡献并扩散转移。
具体而言，我们还是枚举 \(u\)，并且我们已经知道了 \(s_{dep_u}\)，这对 \(u\) 子树内所有点都有效。分别考虑 \(l_j - 1 = dep_u\) 和 \(\min(v_{i \rightarrow j}, r_j) = dep_u\) 的贡献怎么算。
-
对于 \(l_j - 1 = dep_u\) 的贡献，在 \(u\) 子树内枚举所有 \(l_j - 1 = dep_u\) 的 \(j\)，枚举总量线性（下同）。在 \(j\) 的祖先链上倍增求出一段 \(i\)（要求 \(v_{i \rightarrow j} \ge l_j - 1\)），树状数组维护链加即可。
-
对于 \(\min(v_{i \rightarrow j}, r_j) = dep_u\) 的贡献，我们继续分类讨论：
-
若 \(r_j < v_{i \rightarrow j}\)，贡献就是 \(s_{r_j}\)，在 \(u\) 子树内枚举所有 \(r_j = dep_u\) 的 \(j\)，要求 \(v_{i \rightarrow j} \ge r_j + 1\)，其他和上面差不多。
-
若 \(v_{i \rightarrow j} \le r_j\)，根据前面所述，我们知道存在一个深度最大的 \(x\) 使得 \(lim_x = v_{i \rightarrow j}\)，枚举 \(x\)，此时 \(i\) 的范围已经与 \(j\) 无关了，我们只需对于每个 \(x\) 预处理 \(j\) 的数量 \(w_x\)，对于 \(i\) 我们只要求 \(v_{i \rightarrow x} \ge lim_x\)，和前面差不多，两部分乘起来即可。
-
考虑如何预处理 \(w_x\)，特判 \(j = x\) 的情况，我们要求 \(\forall u(u \neq x) \in \text{path}(j, x), lim_u > lim_x\)，且 \(lim_x \in [l_j - 1, r_j]\)，注意到对于一个 \(j\)，合法的 \(x\) 一定是 \(j\) 所在祖先链上的后缀最小值，因此对于每个点向第一个 \(lim\) 小于自己的祖先连边，构成一棵新树，在新树上的祖先链与满足第一个限制的点一一对应。
枚举 \(j\)，只需考虑第二个限制，由于在新树上 \(lim\) 具有单调性，所以合法的 \(x\) 构成新树上的一条链，差分即可。
时间复杂度 \(O(n \log n)\)。
Code
#include <iostream>
#include <vector>
#include <cassert>
using namespace std;
const int N = 1e5 + 5, M = 17;
const int Mod = 998244353;
int n;
int fa[N][M], tl[N], tr[N], lim[N][M], dep[N];
int f[N], s[N], w[N], virt_fa[N];
int dfn[N], now, siz[N], c[N];
vector<int> e[N], vec[N][3], vt[N];
int Kth_fa (int x, int y) {
assert(y >= 0);
for (int k = M - 1; ~k; --k) {
if ((y >> k) & 1) {
x = fa[x][k];
}
}
return x;
}
int Jump (int x, int y, int limit = -1) {
if (lim[x][0] < y || dep[x] <= limit) return -1;
for (int k = M - 1; ~k; --k) {
if (lim[fa[x][0]][k] >= y && dep[x] > limit - (1 << k)) {
x = fa[x][k];
}
}
return x;
}
void Init (int u) {
dfn[u] = ++now, siz[u] = 1;
for (auto v : e[u]) {
Init(v);
siz[u] += siz[v];
}
}
void Bit_add (int x, int y) {
if (!x) return;
for (; x <= n; x += (x & -x)) {
c[x] = (c[x] + y) % Mod;
}
}
int Bit_query (int l, int r) {
int res = 0;
for (--l; l; l -= (l & -l)) {
res = (res - c[l] + Mod) % Mod;
}
for (; r; r -= (r & -r)) {
res = (res + c[r]) % Mod;
}
return res;
}
void Dfs (int u) {
if (u != 1) {
f[u] = Bit_query(dfn[u], dfn[u] + siz[u] - 1);
}
s[u] = (s[fa[u][0]] + f[u]) % Mod;
auto Add_list = [&](int u, int v, int val) -> void {
Bit_add(dfn[fa[u][0]], (Mod - val) % Mod);
Bit_add(dfn[v], val);
};
for (auto j : vec[u][0]) {
int topi = Jump(j, tl[j] - 1, dep[u]);
if (topi != -1) {
Add_list(topi, j, 1ll * (Mod - 1) * s[u] % Mod);
}
}
for (auto j : vec[u][1]) {
int topi = Jump(j, tr[j] + 1, dep[u]);
if (topi != -1) {
Add_list(topi, j, s[u]);
}
}
for (auto x : vec[u][2]) {
int val = 1ll * w[x] * s[u] % Mod;
int topi = Jump(x, lim[x][0], dep[u]);
if (topi != -1) {
Add_list(topi, x, val);
}
}
for (auto v : e[u]) {
Dfs(v);
}
}
void Calc (int u) {
for (auto v : vt[u]) {
Calc(v);
w[u] = (w[u] + w[v]) % Mod;
}
}
int main () {
cin.tie(0)->sync_with_stdio(0);
int tid, T;
cin >> tid >> T;
while (T--) {
cin >> n;
fill(e + 1, e + n + 1, vector<int>());
for (int i = 2, l, r, h; i <= n; ++i) {
cin >> fa[i][0] >> l >> r >> h;
e[fa[i][0]].push_back(i);
dep[i] = dep[fa[i][0]] + 1;
tl[i] = dep[i] - r, tr[i] = dep[i] - l;
lim[i][0] = dep[i] - h - 1;
}
lim[1][0] = -1;
for (int k = 1; k < M; ++k) {
for (int i = 1; i <= n; ++i) {
fa[i][k] = fa[fa[i][k - 1]][k - 1];
lim[i][k] = min(lim[i][k - 1], lim[fa[i][k - 1]][k - 1]);
}
}
fill(vec[1], vec[n] + 3, vector<int>());
for (int i = 2; i <= n; ++i) {
int ned[3] = {tl[i] - 1, tr[i], lim[i][0]};
for (int o = 0; o < 3; ++o) {
int kthf = Kth_fa(i, dep[i] - ned[o]);
if (kthf) {
vec[kthf][o].push_back(i);
}
}
}
now = 0, Init(1);
fill(c + 1, c + n + 1, 0);
fill(f + 1, f + n + 1, 0);
fill(s + 1, s + n + 1, 0);
fill(vt + 1, vt + n + 1, vector<int>());
fill(w + 1, w + n + 1, 0);
for (int i = 2; i <= n; ++i) {
virt_fa[i] = fa[Jump(i, lim[i][0])][0];
vt[virt_fa[i]].push_back(i);
}
for (int i = 2; i <= n; ++i) {
auto Add_limit = [&](int limit, int v) -> void {
int top = (lim[virt_fa[i]][0] <= limit ? virt_fa[i] : fa[Jump(virt_fa[i], limit + 1)][0]);
w[top] = (w[top] + v) % Mod;
};
Add_limit(min(tr[i], lim[i][0] + 1), 1);
Add_limit(tl[i] - 2, Mod - 1);
}
Calc(1);
for (int i = 2; i <= n; ++i) {
w[i] += (tl[i] - 1 <= lim[i][0] && lim[i][0] <= tr[i]);
}
f[1] = 1, Dfs(1);
for (int i = 2; i <= n; ++i) {
cout << f[i] << ' ';
}
cout << '\n';
}
return 0;
}
Day2 T3 树形图(graphee)
首先用 Tarjan 找到能够到达所有点的 SCC，其他 SCC 中的点一定是三类点。没有这样的 SCC 则全是三类点，特判即可。
容易发现一个点是一类点，当且仅当以它为根的 \(\text{dfs}\) 树，只有树边和反祖边。枚举每一个点线性 \(\text{check}\) 可做到 \(O(n^2)\) 找到所有一类点。
注意到特殊性质 C 给出了一个一类点，这启示我们用一个一类点去找其他一类点。对于给出的一类点建 \(\text{dfs}\) 树，我们猜测：
- 一个点是一类点当且仅当它子树内恰好有一条出子树边（一定是反祖边），且该反祖边指向一个一类点。
必要性：若一个点子树内无出子树边，或有多于一条，显然不合法。若指向的不是一类点，则手玩容易发现使指向的点不合法的边仍是前向/横叉边。充分性：换根相当于替换了一条树边和反祖边，对其他边没有影响。
用树状数组动态维护出子树边状态，时间复杂度 \(O((n + m) \log n)\)。
接着考虑找二类点，特判掉没有一类点的情况，此时所有在能够到达所有点的 SCC 中的全是二类点，否则我们在删边时需要使一类点仍然是一类点，相当于钦定若干反祖边和全部树边无法删除，我们称为必要边，判断一条边是否是必要边容易树形 \(\text{dp}\)，我们猜测：
- 若一个点子树内恰好有一条必要出子树边（该边一定连向一个一类点），则该点一定是二类点（删除所有非必要边即可，换根也相当于替换了一条树边和反祖边，对其他边没有影响）。
- 若一个点子树内恰好无必要出子树边，则该点是二类点当且仅当，存在一条非必要出子树边连向一个一/二类点（考虑如果是一类点和前面类似，如果是二类点，将这必要条出子树边保留，其一定为树边，并且会增加一条反祖边，不影响合法性，继续考虑上面的二类点，归纳即可）。
- 其他情况一定是三类点（有超过一条必要出子树边显然不合法，没有出子树边显然不合法，所有出子树边连向三类点，相当于在本来不合法的基础上又加了一条边，当然也不合法）。
这样我们就完成了找剩下一类点和二类点的操作，现在我们的瓶颈在于需要 \(O(n^2)\) 找到第一个一类点。
考虑如果一个点是一类点，建出 \(\text{dfs}\) 树后只有树边和反祖边，这告诉我们可以通过不断缩叶子的操作使这棵树只有一个点。我们模拟这一过程，若某一时刻没有叶子，且还剩下至少 \(2\) 个点说明没有一类点，否则最后剩下的一定是一个一类点。
具体而言，我们不断处理入度为 \(1\) 的点 \(u\)，这个点对应某一以一类点为根的 \(\text{dfs}\) 树上的叶子，假设有边 \(u \rightarrow v\)，我们将 \(u\) 和 \(v\) 用并查集合并在一起，并检查 \(v\) 的入边，因为此时可能成为新叶子的点只有 \(v\)。若 \(v\) 有一条入边 \(w \rightarrow v\)，并且 \(w\) 和 \(v\) 已经合并，则我们可以删除这一条边。
我们发现我们无需一次检查 \(v\) 的所有入边，只需知道是否还至少存在两条即可。我们用 \(\text{std::deque}\) 维护，每次只需检查第一条和最后一条，注意到一共只会检查 \(O(n)\) 个点，每一条边只会删除一次，时间复杂度 \(O((n + m) \alpha(n))\)。
总时间复杂度 \(O((n + m) \log n)\)。
Code
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <numeric>
using namespace std;
const int N = 1e5 + 5;
int n, m, tot;
int tans[N];
vector<int> e[N];
namespace Graph {
int dfn[N], now, low[N], deg[N], srt, block[N];
vector<int> vec[N];
bool ins[N];
stack<int> st;
void Tarjan (int u) {
dfn[u] = low[u] = ++now, ins[u] = 1;
st.push(u);
for (auto v : e[u]) {
if (!dfn[v]) {
Tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (ins[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (low[u] == dfn[u]) {
vec[++tot].clear();
for (int v = 0; v != u; ins[v] = 0, st.pop()) {
v = st.top();
vec[tot].push_back(v);
block[v] = tot;
}
}
}
int Init () {
fill(dfn + 1, dfn + n + 1, 0), now = tot = 0;
for (int i = 1; i <= n; ++i) {
if (!dfn[i]) Tarjan(i);
}
fill(deg + 1, deg + tot + 1, 0);
for (int i = 1; i <= n; ++i) {
for (auto j : e[i]) {
if (block[i] != block[j]) {
++deg[block[j]];
}
}
}
srt = 0;
for (int i = 1; i <= tot; ++i) {
if (deg[i] == 0) {
if (!srt) srt = i;
else {
for (int i = 1; i <= n; ++i) {
cout << 3;
}
cout << '\n';
return 1;
}
}
else {
for (auto j : vec[i]) {
tans[j] = 3;
}
}
}
return 0;
}
}
namespace Find_one {
deque<int> r[N];
int fa[N];
int Find (int x) {
if (fa[x] == x) return x;
return fa[x] = Find(fa[x]);
}
int Solve () {
fill(r + 1, r + n + 1, deque<int>());
for (int i = 1; i <= n; ++i) {
for (auto j : ::e[i]) {
r[j].push_back(i);
}
}
queue<int> q;
for (int i = 1; i <= n; ++i) {
if (r[i].size() == 1) {
q.push(i);
}
}
iota(fa + 1, fa + n + 1, 1);
for (; !q.empty(); q.pop()) {
int u = q.front(), v = Find(r[u].back());
fa[u] = v;
for (; !r[v].empty() && Find(r[v].front()) == v; r[v].pop_front());
for (; !r[v].empty() && Find(r[v].back()) == v; r[v].pop_back());
if (r[v].size() == 1) q.push(v);
}
int t = 0;
for (int i = 1; i <= n; ++i) {
if (fa[i] == i) {
if (!t) t = i;
else return 0;
}
}
return t;
}
}
namespace Dfs_tree {
struct Bit {
int c[N];
void Init () { fill(c + 1, c + n + 1, 0); }
void Add (int x, int y) {
for (; x <= n; x += (x & -x)) {
c[x] += y;
}
}
int Query (int l, int r) {
int res = 0;
for (--l; l; l -= (l & -l)) {
res -= c[l];
}
for (; r; r -= (r & -r)) {
res += c[r];
}
return res;
}
} dyn, unec, nec;
int dfn[N], now, siz[N], c[N], root, shal[N], dep[N];
vector<int> vec[N];
void Build (int u) {
dfn[u] = ++now;
siz[u] = 1;
for (auto v : e[u]) {
if (!dfn[v]) {
dep[v] = dep[u] + 1;
Build(v);
siz[u] += siz[v];
}
else {
vec[v].push_back(u);
}
}
}
void Init (int rt) {
root = rt;
fill(dfn + 1, dfn + n + 1, 0);
fill(vec + 1, vec + n + 1, vector<int>());
tans[rt] = 1, now = 0, dep[rt] = 0, Build(rt);
}
namespace Find_other_one {
void Dfs (int u) {
if (dfn[u] != 1) {
if (dyn.Query(dfn[u], dfn[u] + siz[u] - 1) == 1) {
tans[u] = 1;
}
}
if (tans[u] == 1) shal[u] = dep[u];
for (auto v : vec[u]) {
dyn.Add(dfn[v], (tans[u] != 1) + 1);
}
for (auto v : e[u]) {
if (dfn[v] > dfn[u]) {
shal[v] = max(shal[v], shal[u]);
Dfs(v);
}
}
}
void Solve () { fill(shal + 1, shal + n + 1, -1), dyn.Init(), Dfs(root); }
}
namespace Find_two {
void Dfs (int u) {
if (!tans[u]) {
int nec_cnt = nec.Query(dfn[u], dfn[u] + siz[u] - 1);
if (nec_cnt == 1) {
tans[u] = 2;
}
else if (!nec_cnt && unec.Query(dfn[u], dfn[u] + siz[u] - 1)) {
tans[u] = 2;
}
}
for (auto v : vec[u]) {
if (tans[u] == 1 && shal[v] > dep[u]) {
nec.Add(dfn[v], 1);
}
else if (tans[u] == 1 || tans[u] == 2) {
unec.Add(dfn[v], 1);
}
}
for (auto v : e[u]) {
if (dfn[v] > dfn[u]) {
Dfs(v);
}
}
}
void Solve () {
nec.Init(), unec.Init();
Dfs(root);
}
}
}
int main () {
cin.tie(0)->sync_with_stdio(0);
int tid, T;
cin >> tid >> T;
while (T--) {
cin >> n >> m;
fill(e + 1, e + n + 1, vector<int>());
for (int i = 1, u, v; i <= m; ++i) {
cin >> u >> v;
e[u].push_back(v);
}
fill(tans + 1, tans + n + 1, 0);
if (Graph::Init()) continue;
int rt = Find_one::Solve();
if (!rt) {
for (int i = 1; i <= n; ++i) {
cout << (!tans[i] ? 2 : 3);
}
cout << '\n';
continue;
}
Dfs_tree::Init(rt);
Dfs_tree::Find_other_one::Solve();
Dfs_tree::Find_two::Solve();
for (int i = 1; i <= n; ++i) {
cout << (!tans[i] ? 3 : tans[i]);
}
cout << '\n';
}
return 0;
}