「CSP-S 2019」括号树plus
CLYZ 学长学姐们留下来的题,感谢+膜拜。
给出一棵有 n 个节点的数,根节点为 1。每个节点上恰有一个括号,要么为左括号 ( 要么为右括号 )。
记 s_i 表示从根到 i 的路径上,依次将各个节点的括号拼接而成的字符串。设 k_i 表示 s_i 中本质不同的合法括号子串的数量。求
数据范围:1 \leq n \leq 5 \times 10^5。
时空限制:5s / 512MiB。
Solution
采用增量法。对树进行 DFS,每次计算以 u 为最低点时的答案。
由于要求本质不同,对于一个串 s[u : t_u],如果其在 s[\mathrm{Fa}_u : 1] 中作为子串出现,则这样的串是不能计入答案的。
求一个深度最小的 t_u,相当于是在 \mathrm{Fa}_u 到 1 的路径上选一个点 v,使得 \mathrm{LCP}(s[u : 1], s[v : 1]) 最大。
在树上做一遍 SA,这相当于是在 \mathrm{Fa}_u 到 1 的路径上,找 \mathrm{rk}_u 的前驱后继。用 std::set 维护即可。
考虑求在 \mathrm{Fa}_{t_u} 到 1 的路径上,有多少个点 v 使得 s[u : v] 是一个合法括号串。
将左右括号转换为 \pm 1 做一个前缀和。用倍增找出可行范围后,在 std::vector 上二分维护即可。
时间复杂度 \mathcal{O}(n \log n)。
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include <vector>
typedef long long s64;
using std::set;
typedef set<int>::iterator iter;
using std::vector;
template <class T>
inline void read(T &x) {
static char s;
while (s = getchar(), s < '0' || s > '9');
x = s - '0';
while (s = getchar(), s >= '0' && s <= '9') x = x * 10 + s - '0';
}
void tense(int &x, const int &y) {
if (x < y) x = y;
}
void relax(int &x, const int &y) {
if (x > y) x = y;
}
const int N = 500100;
int n;
char s[N];
int anc[19][N];
int tot, head[N], ver[N], Next[N];
void add_edge(int u, int v) {
ver[++ tot] = v; Next[tot] = head[u]; head[u] = tot;
}
int pre[N];
int dep[N];
int g[19][N];
void dfs1(int u) {
pre[u] = pre[anc[0][u]] + (s[u] == '(' ? -1 : 1);
dep[u] = dep[anc[0][u]] + 1;
for (int i = 1; i <= 18; i ++) anc[i][u] = anc[i - 1][anc[i - 1][u]];
g[0][u] = pre[anc[0][u]];
for (int i = 1; i <= 18; i ++) tense(g[i][u] = g[i - 1][u], g[i - 1][anc[i - 1][u]]);
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i];
dfs1(v);
}
}
namespace SA {
int m = 2;
int sa[N], rk[N], height[N];
int cnt[N], id[N], px[N];
int anc_rk[19][N];
int get_LCP(int x, int y) {
int cur = 0;
for (int i = 18; i >= 0; i --) {
if (std::min(dep[x], dep[y]) < (1 << i)) continue;
if (anc_rk[i][x] ^ anc_rk[i][y]) continue;
x = anc[i][x], y = anc[i][y], cur ^= (1 << i);
}
return cur;
}
bool same(int x, int y, int k) {
int p = anc[k][x] ? anc_rk[k][anc[k][x]] : -1;
int q = anc[k][y] ? anc_rk[k][anc[k][y]] : -1;
return anc_rk[k][x] == anc_rk[k][y] && p == q;
}
void build() {
for (int i = 1; i <= n; i ++) rk[i] = (s[i] == '(' ? 1 : 2);
for (int i = 1; i <= n; i ++) cnt[rk[i]] ++;
for (int i = 1; i <= m; i ++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i --) sa[cnt[rk[i]] --] = i;
for (int k = 0, p = 0; (1 << k) < n; k ++, m = p) {
for (int i = 0; i <= m; i ++) cnt[i] = 0;
for (int i = 1; i <= n; i ++) cnt[px[i] = rk[anc[k][i]]] ++;
for (int i = 1; i <= m; i ++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i --) id[cnt[px[i]] --] = i;
for (int i = 0; i <= m; i ++) cnt[i] = 0;
for (int i = 1; i <= n; i ++) cnt[px[i] = rk[id[i]]] ++;
for (int i = 1; i <= m; i ++) cnt[i] += cnt[i - 1];
for (int i = n; i >= 1; i --) sa[cnt[px[i]] --] = id[i];
for (int i = 1; i <= n; i ++) anc_rk[k][i] = rk[i];
p = 0;
for (int i = 1; i <= n; i ++) rk[sa[i]] = same(sa[i - 1], sa[i], k) ? p : ++ p;
}
for (int i = 1; i <= n; i ++) rk[sa[i]] = i;
for (int i = 2; i <= n; i ++) height[i] = get_LCP(sa[i - 1], sa[i]);
}
}
namespace ST {
int logx[N];
int f[19][N];
void build() {
logx[0] = -1;
for (int i = 1; i <= n; i ++) logx[i] = logx[i >> 1] + 1;
for (int i = 1; i <= n; i ++) f[0][i] = SA::height[i];
for (int j = 1; j <= 18; j ++)
for (int i = 1; i <= n - (1 << j) + 1; i ++)
relax(f[j][i] = f[j - 1][i], f[j - 1][i + (1 << (j - 1))]);
}
int query(int l, int r) {
int k = logx[r - l + 1];
return std::min(f[k][l], f[k][r - (1 << k) + 1]);
}
}
set<int> G;
int find_h(int x) {
iter w = G.lower_bound(x);
int cur = 0;
if (w != G.end())
tense(cur, ST::query(x + 1, *w));
if (w != G.begin())
tense(cur, ST::query(*(-- w) + 1, x));
return cur;
}
int find_m(int u) {
int x = u;
for (int i = 18; i >= 0; i --)
if (dep[x] >= (1 << i) && pre[u] >= g[i][x]) x = anc[i][x];
return x;
}
vector<int> pos[N * 2];
s64 ans[N];
void dfs2(int u) {
int l = dep[find_m(u)] + 1, r = dep[u] - find_h(SA::rk[u]);
pos[n + pre[anc[0][u]]].push_back(dep[u]);
G.insert(SA::rk[u]);
ans[u] = ans[anc[0][u]];
if (s[u] == ')') {
if (l <= r) {
vector<int> &V = pos[n + pre[u]];
ans[u] += upper_bound(V.begin(), V.end(), r) - lower_bound(V.begin(), V.end(), l);
}
}
for (int i = head[u]; i; i = Next[i]) {
int v = ver[i];
dfs2(v);
}
pos[n + pre[anc[0][u]]].pop_back();
G.erase(SA::rk[u]);
}
int main() {
read(n);
scanf("%s", s + 1);
for (int i = 2; i <= n; i ++)
read(anc[0][i]), add_edge(anc[0][i], i);
dfs1(1);
SA::build();
ST::build();
dfs2(1);
s64 res = 0;
for (int i = 1; i <= n; i ++) res ^= (ans[i] * i);
printf("%lld\n", res);
return 0;
}