题解：P16693 Tokitsukaze and Palindrome Border

· · 题解

不禁让人疑惑这个题为啥会有 \omega((S+K)\log S) 的做法。

我们可以根据回文串的性质将 \operatorname{val}(s,t,l) 改写为 s[1:l]=s[1:l]^R=t^R[1:l]，多串之间的公共前缀考虑使用 Trie 刻画，随便用一种你喜欢的方法判定 Trie 上每个点到根的路径是不是回文的，如果是则它会对答案产生深度 \times 子树内 s_i 的数量 \times 子树内 s_i^R 的数量的贡献。

一次查询相当于使若干个点失效了，求出这些点构成的虚树，重算虚树上所有点对答案的贡献即可，时间复杂度 \Theta((S+K)\log S)，瓶颈在 LCA 和建虚树，分别可以用四毛子和离线做到线性。

可惜的是常数有点大，根本打不过根号老哥的做法。

#include <algorithm>
#include <chrono>
#include <iostream>
#include <random>

using namespace std;
using ull = unsigned long long;

mt19937_64 rnd(chrono::steady_clock().now().time_since_epoch().count());

constexpr int kN = 6e5 + 2, kL = __lg(kN) + 1;
const ull kB = rnd() | 1;

struct E {
  int ve, e[26], w, _w, d, s, fa, st0, st1, dt0, dt1;
  ull sw;
} e[kN];
int n, q, a[kN], ar[kN], p[kN];
ull s0[kN], s1[kN], da[kN];
int b[kL][kN], c = 1, dc;
ull ans;

int I(const string& s, int v0, int v1) {
  ull h = 0, hr = 0, b = 1;
  int x = 1;
  for (char i : s) {
    h = h * kB + i, hr = hr + i * b, b *= kB;
    e[x].st0 += v0, e[x].st1 += v1;
    int& y = e[x].e[i - 'a'];
    if (!y) {
      y = ++c, e[x].ve |= 1 << (i - 'a');
      e[y].fa = x, e[y].w = e[x].w + 1, e[y]._w = (h == hr ? e[y].w : 0);
    }
    x = y;
  }
  e[x].st0 += v0, e[x].st1 += v1;
  return x;
}
void D(int x) {
  b[0][e[x].d = ++dc] = e[x].fa;
  for (int i = -1; e[x].ve >> (i + 1);) {
    i += __builtin_ctz(e[x].ve >> (i + 1)) + 1;
    D(e[x].e[i]);
  }
}
bool cmp(int x, int y) { return e[x].d < e[y].d; }
int L(int x, int y) {
  if (x == y) {
    return x;
  }
  if ((x = e[x].d) > (y = e[y].d)) {
    swap(x, y);
  }
  int g = __lg(y - x++);
  return min(b[g][x], b[g][y - (1 << g) + 1], cmp);
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n;
  for (int i = 1; i <= n; ++i) {
    string s;
    cin >> s;
    a[i] = I(s, 1, 0), reverse(s.begin(), s.end()), ar[i] = I(s, 0, 1);
  }
  for (int i = c; i >= 1; --i) {
    e[e[i].fa].s += ++e[i].s;
  }
  for (int i = 1; i <= c; ++i) {
    ans += (ull)e[i]._w * e[i].st0 * e[i].st1;
    e[i].sw = e[e[i].fa].sw + e[i]._w;
    s0[i] = s0[e[i].fa] + (ull)e[i]._w * e[i].st1;
    s1[i] = s1[e[i].fa] + (ull)e[i]._w * e[i].st0;
  }
  for (int i = 1; i <= n; ++i) {
    da[i] = s0[a[i]] + s1[ar[i]];
  }
  D(1);
  for (int i = 0; i < __lg(c); ++i) {
    for (int j = 1; j + (1 << (i + 1)) - 1 <= c; ++j) {
      b[i + 1][j] = min(b[i][j], b[i][j + (1 << i)], cmp);
    }
  }
  cin >> q;
  for (int k; q--;) {
    cin >> k;
    if (k == 0) {
      cout << ans << '\n';
      continue;
    }
    ull _ans = ans;
    for (int i = 0, x; i < k; ++i) {
      cin >> x;
      p[i * 2] = a[x], p[i * 2 + 1] = ar[x];
      ++e[a[x]].dt0, ++e[ar[x]].dt1;
      _ans -= da[x];
    }
    stable_sort(p, p + k * 2, cmp);
    int m = unique(p, p + k * 2) - p;
    auto C = [&_ans](int x, int f) -> void {
      _ans += (e[x].sw - e[f].sw) * e[x].dt0 * e[x].dt1;
      e[f].dt0 += e[x].dt0, e[f].dt1 += e[x].dt1, e[x].dt0 = e[x].dt1 = 0;
    };
    vector<int> r;
    for (int i = 0; i < m; ++i) {
      int x = p[i], y = 0;
      for (; !r.empty() && e[x].d >= e[r.back()].d + e[r.back()].s;) {
        y = r.back(), r.pop_back();
        if (!r.empty() && e[x].d >= e[r.back()].d + e[r.back()].s) {
          C(y, r.back());
        }
      }
      if (y) {
        int z = L(y, x);
        C(y, z);
        if (r.empty() || z != r.back()) {
          r.push_back(z);
        }
      }
      r.push_back(x);
    }
    int y = 0;
    for (; r.size() > 1; y = r.back(), r.pop_back(), C(y, r.back())) {
    }
    if (r.size() == 1 && r[0] != 1) {
      C(r[0], 1);
    }
    e[1].dt0 = e[1].dt1 = 0;
    cout << _ans << '\n';
  }
  return 0;
}