P9150 邮箱题

· · 题解

P9150 邮箱题

好久没见到这么小清新的图论题了。上次见到还是在 上次。

首先，因为进入一个点时必然有该点的钥匙，而钥匙的数量不会超过进入的点的数量 +1，所以在任意时刻，接下来新进入的点是固定的，且该点的钥匙在上一个新进入的点内。因此，如果从 i 号点出发，只需在已经进入的点的基础上，依次考虑 k_i, k_{k_i}, \cdots 是否可达。

考虑当前点 j 以及从 i 不断跳 k_i 到 j 的序列 a = \{i, k_i, k_{k_i},\cdots, j\}。我们探究 k_j 可达的充要条件：

如何判定条件二呢？因为 a_i 可达 a_{i + 1}，所以只需在每次往序列中加入 a_p = j，即新进入点 j 时，考虑其所有 “返祖边” a_p\to a_q（p > q），则 a_q\sim a_p 之间所有点强连通。枚举 k_j 的入边 u\to k_j，若 u\in a 且 u 和 j 强连通，则 k_j 可达。

用并查集维护强连通分量的合并过程，我们得到了 \mathcal{O}(n ^ 2\alpha) 的做法。

因为 k 形成排列，所以我们将 k 上的所有环拎出来单独考虑。

首先断环成链，将环复制两份得到序列 c。我们认为一个点的 k 值为其后继，则每个点的前一份复制品在链上的答案就是它在环上的答案。因为从后面的点出发，不会到达前面的点，所以我们从后往前加入计算每个点的答案。

若从 x 出发可达 y，从 y 出发可达 z，则从 x 出发可达 z，因为从 x 出发到达 y 之后，一定拥有 y 号点的钥匙。因此，可达性具有传递性，可以用若干条链描述。

设 c_{i + 1}\sim c_{L} 的答案已知，计算 c_i 的答案，则整个过程相当于不断尝试合并第一条链和第二条链。设第一条链的末尾为 c_p，第二条链的开头为 c_{p + 1}，根据朴素做法中的判定条件，考虑 c_{p + 1} 的最靠近 c_p 且落在 c_i\sim c_p 上的入边 c_u\to c_{p + 1}（i\leq u\leq p 且 u 最大），若 c_u 存在且和 c_p 强连通，则可以合并，否则无法合并。

用两个并查集分别维护可达链和强连通分量，预处理每个点在链上最靠近它且在它前方的入点的位置即可。

问题来了，合并两条可达链的时候，强连通分量该怎么合并？虽然产生贡献的返祖边数量总数只有 \mathcal{O}(m)，但我们不能直接枚举第二条链上的所有返祖边，因为这样无法跳过不产生贡献的返祖边。一个解决方案是，对每个可达链，维护所有终点编号不小于 i 且 还没考虑过 的返祖边。合并两条链时，统计第二条链维护的所有返祖边的影响，并将它们全部删除。这样，新链的返祖边集合就等于第一条链的返祖边集合，不需要启发式合并。

至此已经得到 \mathcal{O}(n\alpha) 的做法，但是不优美。

我们注意到，如果两条链可以合并，那么第一条链的开头，即当前的 c_i 一定产生了贡献，否则在加入 c_i 之前这两条链就已经可以合并了。而如果 c_i 要产生贡献，一定将第一条链的末尾 c_p 所在的强连通分量扩大了，这说明 c_i 和 c_p 在同一强连通分量，即 第一条链整体是一个强连通分量。这样，对于每条链，只需维护编号最大的有还未统计过的返祖边的节点，因为这些返祖边具体指向哪些点是不重要的，反正它们在同一个强连通分量，而每个起始点都相当于将 c_i 到该起始点的强连通分量全部合并，所以我们只关心编号最大的起始点。

此外，有了该性质，在判定是否可以合并两条链时，也可以维护每个点 c_{p + 1} 是否被之前 c_i\sim c_p 的某个点指向，代替计算每个点的最近前驱的位置，但这样就要存正向边了。

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

bool Mbe;
constexpr int N = 3e6 + 5;
void cmax(int &x, int y) {x = x > y ? x : y;}

int n, m, k[N], a1[N], a2[N];
bool vis[N]; // vis 表示是否被访问过
int c, cyc[N], in[N], val[N], pre[N]; // in 表示结点在环上的编号，val 表示结构编号最大的有返祖边的分量，pre 表示结点的最近前驱入边位置
vector<int> e[N];
struct dsu {
  int fa[N];
  int find(int x) {return fa[x] == x ? x : fa[x] = find(fa[x]);}
  void merge(int a, int b) {fa[find(b)] = find(a);}
} cy, ch; // 维护环（强连通分量）和链的并查集

void solve() {
  cin >> n >> m;
  for(int i = 1; i <= n; i++) e[i].clear();
  memset(vis, 0, n + 2);

  for(int i = 1; i <= n; i++) cin >> k[i];
  for(int i = 1; i <= m; i++) {
    int u, v;
    cin >> u >> v;
    e[v].push_back(u);
  }

  for(int i = 1; i <= n; i++) {
    if(vis[i]) continue;
    int p = i;
    while(!in[p]) cyc[++c] = p, in[p] = c, p = k[p];
    for(int j = c * 2; j; j--) {
      cy.fa[j] = ch.fa[j] = j, val[j] = pre[j] = 0;
      int id = cyc[j > c ? j - c : j];
      for(int it : e[id]) {
        if(!in[it]) continue;
        it = in[it];
        if(it + c < j) it += c;
        if(it > j) it -= c;
        pre[j] = max(pre[j], it);
        if(it < j) it += c;
        if(it <= c * 2) cmax(val[ch.find(it)], cy.find(it));
      }
      while(1) {
        while(1) {
          int cyid = cy.find(j), chid = ch.find(j);
          if(cyid < val[chid]) cy.merge(cyid + 1, cyid);
          else break;
        }
        int cyid = cy.find(j), chid = ch.find(j);
        val[chid] = 0;
        if(chid == c * 2 || cyid != chid || pre[chid + 1] < j) break;
        ch.merge(chid + 1, chid);
      }
      a1[id] = min(c, ch.find(j) - j + 1);
      a2[id] = min(c, cy.find(j) - j + 1);
    }
    for(int i = 1; i <= c; i++) in[cyc[i]] = 0, vis[cyc[i]] = 1;
    c = 0;
  }
  for(int i = 1; i <= n; i++) cout << a1[i] << " " << a2[i] << "\n";
}

bool Med;
int main() {
  fprintf(stderr, "%.3lf MB\n", (&Mbe - &Med) / 1048576.0);
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  #ifdef ALEX_WEI
    FILE* IN = freopen("1.in", "r", stdin); 
    FILE* OUT = freopen("1.out", "w", stdout);
  #endif
  int T;
  cin >> T;
  while(T--) solve();
  cerr << 1e3 * clock() / CLOCKS_PER_SEC << " ms\n";
  return 0;
}