526互联

NOI2023 D2T2 字符串

发布时间 2023-09-20 13:49:51作者: Chy12321

从最朴素的 \(\mathcal O(qn^2)\) 做法开始，即暴力枚举每个 \(s[i : i + l - 1]\) 和 \(\operatorname R(s[i + l : i + 2l - 1])\) 并统计答案。

发现没有啥合适的字符串算法来直接地进行优化，考虑 容斥 出答案。

令 \(P_i = s[1 : i], S_i = s[i : n]\)，同时设 \(s[i : i + l - 1] < \operatorname R(s[i + l : i + 2l - 1])\) 为条件 \(A\)，\(S_i < P_{i + 2l - 1}\) 为条件 \(B\)，易得 \(A \Rightarrow B\)。

考虑一个条件 \(C\)，使得 \(B - C = A\)。易得条件 \(C\) 为 \(s[i : i + 2l - 1]\) 回文且 \(S_{i + 2l} < P_{i - 1}\)。

综上，我们将答案转化为了满足 \(S_i < P_{i + 2l - 1}\) 的 \(l\) 的个数与满足 \(s[i : i + 2l - 1]\) 回文且 \(S_{i + 2l} < P_{i - 1}\) 的 \(l\) 的个数之差。

对于第一部分：

对 \(s + c_1 + \operatorname R(s) + c_2\)（其中 \(c_1, c_2\) 为不属于 \(s\) 字符集的分割符，且 \(c_1 > c_2\) ） 求 SA，则问题又转化为一个二维偏序问题，离线后按后缀排序从大到小用两棵树状数组维护出现过的奇数、偶数位置数量并更新相应答案即可，时间复杂度 \(\mathcal O[(n + q) \log n]\)。

对于第二部分：

用 Manacher 求出所有回文串，令以 \(i\) 和 \(i + 1\) 的间隔为中心的最长回文半径为 \(R_i\)，显然有 \(s[i - R_i + 1 : i] = \operatorname R(s[i + 1 : i + R_i])\)，因此若 \(s_{i - R_i} = s_{i + R_i + 1}\)，则所有以 \(i\) 和 \(i + 1\) 的间隔为回文中心的回文串均符合条件。时间复杂度 \(\mathcal O(n)\)。同时注意到问题转化为：在平面直角坐标系内对所有形如 \((i - l_i + 1, i + l_i)\) 的点权值 \(+ 1\)，其中 \(1 \le l_i \le R_i\)。然后查询形如 \((i, i + 2r - 1)\) 的点以下的点权和。
为了方便描述，定义一次对某个特定 \(i\) 进行所有点权修改的操作为一批操作。

这显然是二位数点问题，但修改的次数是 \(\mathcal O(n^2)\) 的，考虑变换一下点坐标，使一批修改有相同的横坐标或纵坐标，通过差分将修改次数将至 \(\mathcal O(n)\)。

发现回文串的中心点始终不变，于是把修改的点的坐标变换为 \((i - l_i + 1, i + 1)\)，相应地，查询的点坐标变换为 \((i, i + r)\)。这样，一批修改的纵坐标就统一了。

扫描线 + 树状数组，时间复杂度 \(\mathcal O[(n + q) \log n]\)。

总时间复杂度 \(\mathcal O[(n + q) \log n]\)。

代码：

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;

constexpr int MAXN = 1e5 + 10;

int n, q, c[MAXN << 1], sa[MAXN << 1], rk[MAXN << 1], RL[MAXN << 1], ans[MAXN];
char s[MAXN], s1[MAXN << 1], s2[MAXN << 1];
pii ask[MAXN];

struct Node {
	int id, x, y;

	bool operator!=(const Node &rhs) const {
		return x != rhs.x || y != rhs.y;
	}
} a[MAXN << 1], b[MAXN << 1];

struct BIT {
	int c[MAXN << 1];

	void clear() {
		memset(c, 0, sizeof(c));
	}

	void fix(int x, int val) {
		for (int i = x; i < (MAXN << 1); i += i & (-i)) c[i] += val;
	}

	int query(int x) {
		int res = 0;
		for (int i = x; i; i -= i & (-i)) res += c[i];
		return res;
	}

	inline int query(int l, int r) {
		return query(r) - query(l - 1);
	}
};

void getSA(char *s) {
	int n = strlen(s + 1); memset(c, 0, sizeof(c));
	for (int i = 1; i <= n; i++) c[s[i]]++;
	for (int i = 1; i <= 127; i++) c[i] += c[i - 1];
	for (int i = n; i; i--) sa[c[s[i]]--] = i;
	int tot = 0;
	for (int i = 1; i <= n; i++) tot += s[sa[i]] != s[sa[i - 1]], rk[sa[i]] = tot;
	for (int k = 1; k < n; k <<= 1) {
		for (int i = 1; i + k <= n; i++) a[i] = {i, rk[i], rk[i + k]};
		for (int i = n - k + 1; i <= n; i++) a[i] = {i, rk[i], 0};
		memset(c, 0, sizeof(c));
		for (int i = 1; i <= n; i++) c[a[i].y]++;
		for (int i = 1; i <= tot; i++) c[i] += c[i - 1];
		for (int i = n; i; i--) b[c[a[i].y]--] = a[i];
		memset(c, 0, sizeof(c));
		for (int i = 1; i <= n; i++) c[b[i].x]++;
		for (int i = 1; i <= tot; i++) c[i] += c[i - 1];
		for (int i = n; i; i--) a[c[b[i].x]--] = b[i];
		tot = 0;
		for (int i = 1; i <= n; i++) tot += a[i] != a[i - 1], rk[a[i].id] = tot;
		if (tot == n) break;
	}
	for (int i = 1; i <= n; i++) sa[rk[i]] = i;
}

void Manacher(char *s) {
	int pos = 0, maxright = 0;
	for (int i = 1; s[i]; i++) {
		RL[i] = i < maxright ? min(RL[(pos << 1) - i], maxright - i) : 1;
		while (s[i - RL[i]] == s[i + RL[i]]) RL[i]++;
		if (i + RL[i] - 1 > maxright) pos = i, maxright = i + RL[i] - 1;
	}
}

namespace Part1 {
	struct Query {
		int id, l, r;
	};

	BIT odd, eve;

	vector<Query> Q[MAXN << 1];

	void newq(int id, int i, int r) {
		Q[rk[i]].emplace_back(Query{id, i + 1, i + (r << 1) - 1});
	}

	void calc() {
		eve.clear(), odd.clear();
		int len = strlen(s1 + 1);
		for (int i = len; i; i--) {
			if (sa[i] <= n) for (Query q : Q[i]) ans[q.id] += ((q.l & 1) ? odd : eve).query(q.l, q.r);
			else if (sa[i] > n + 1 && sa[i] < len) (((len - sa[i]) & 1) ? odd : eve).fix(len - sa[i], 1);
			Q[i].clear();
		}
	}
}

namespace Part2 {
	BIT t;

	vector<pii> A[MAXN << 1], Q[MAXN << 1];

	void newa(int i, int r, int w) {
		A[i].emplace_back(pii(r, w));
	}

	void newq(int id, int i, int r) {
		Q[i].emplace_back(pii(id, i + r));
	}

	void calc() {
		t.clear();
		for (int i = 1; i <= n; i++) {
			for (pii a : A[i]) t.fix(a.first, a.second);
			A[i].clear();
			for (pii q : Q[i]) ans[q.first] -= t.query(q.second);
			Q[i].clear();
		}
	}
}

void solve() {
	// Input
	cin >> n >> q >> (s + 1);
	for (int i = 1; i <= q; i++) cin >> ask[i].first >> ask[i].second;
	// Part 1
	s1[n + 1] = 2, s1[(n + 1) << 1] = 1, s1[(n + 1) << 1 | 1] = 0;
	for (int i = 1; i <= n; i++) s1[i] = s[i], s1[n + 1 + i] = s[n - i + 1];
	getSA(s1);
	for (int i = 1; i <= q; i++) Part1::newq(i, ask[i].first, ask[i].second);
	Part1::calc();
	// Part 2
	s2[0] = s2[1] = '#', s2[(n + 1) << 1] = 0;
	for (int i = 1; i <= n; i++) s2[i << 1] = s[i], s2[i << 1 | 1] = '#';
	Manacher(s2);
	for (int i = 1; i < n; i++) {
		int R = RL[i << 1 | 1] >> 1;
		if (!R || s[i + R + 1] >= s[i - R]) continue;
		Part2::newa(i - R + 1, i + 1, 1), Part2::newa(i + 1, i + 1, -1);
	}
	for (int i = 1; i <= q; i++) Part2::newq(i, ask[i].first, ask[i].second);
	Part2::calc();
	// Output
	for (int i = 1; i <= q; i++) {
		cout << ans[i] << '\n'; ans[i] = 0;
	}
}

int main() {
	ios_base::sync_with_stdio(0); cin.tie(nullptr), cout.tie(nullptr);
	int c, t; cin >> c >> t;
	while (t--) solve();
	return 0;
}