GDKOI 2021 提高组 Day1 第三题 回文（manachar+ST表）

GDKOI 2021 提高组 Day1 第三题 回文

题目大意

• 给出长为$n$的串，和$q$组询问，每次询问区间中的最长回文串。
• $n,q\le 5\ast 10^5$

题解

• 可以先用manachar求出以每个位置为中心的回文串，询问时二分答案，然后在区间中判断是否存在长度为$mid$的回文串，用ST表维护区间最值。
• 注意二分判断时并非在整个区间$[l,r]$中找最大值，而需分别将左端点右移和右端点左移大约$mid$（因奇偶而不同）的位置，以保证找到的回文串整段落在区间内。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
#define N 500010
#define ll long long
#define md 998244353
char a[N];
int n, Q, o;
int s0[N], s1[N], F0[N][20], F1[N][20], G0[N][20], G1[N][20];
float lo[N];
int find0(int l, int r) {
	if(l > r) return 0;
	o = floor(lo[r - l + 1] / lo[2]);
	return max(F0[l][o], G0[r][o]);
}
int find1(int l, int r) {
	if(l > r) return 0;
	o = floor(lo[r - l + 1] / lo[2]);
	return max(F1[l][o], G1[r][o]);
}
int read() {
	int s = 0;
	char x = getchar();
	while(x < '0' || x > '9') x = getchar();
	while(x >= '0' && x <= '9') s = s * 10 + x - 48, x = getchar();
	return s;
}
void write(int s) {
	int l = 0, c[10];
	while(s) c[++l] = s % 10, s /= 10;
	while(l) putchar(c[l--] + 48);
	puts("");
}
int main() {
	scanf("%s", a + 1);
	n = strlen(a + 1);
	int i, j, l, r, L, R, mid, ans;
	for(i = 1; i <= n; i++) lo[i] = log(i);
	l = 1, r = 0;
	for(i = 1; i <= n; i++) {
		s1[i] = 1, s0[i] = 0;
		if(l <= r && i <= r) {
			if((r - l + 1) % 2 == 0) {
				s0[i] = min(s0[2 * mid - i], r - i);
				s1[i] = min(s1[2 * mid - i + 1], r - i + 1);
			}
			else {
				s0[i] = min(s0[2 * mid - i - 1], r - i);
				s1[i] = min(s1[2 * mid - i], r - i + 1);
			}
		}
		while(i - s0[i] > 0 && i + s0[i] < n && a[i - s0[i]] == a[i + s0[i] + 1]) s0[i]++;
		while(i - s1[i] > 0 && i + s1[i] <= n && a[i - s1[i]] == a[i + s1[i]]) s1[i]++;
		if(i + s1[i] - 1 > r) l = i - s1[i] + 1, r = i + s1[i] - 1, mid = i;
		if(i + s0[i] > r) l = i - s0[i] + 1, r = i + s0[i], mid = i;
	} 
	for(i = n; i; i--) {
		F0[i][0] = s0[i] * 2, F1[i][0] = s1[i] * 2 - 1;
		for(j = 1; j < 19 && i + (1 << (j - 1)) - 1 <= n; j++) F0[i][j] = max(F0[i][j - 1], F0[i + (1 << (j - 1))][j - 1]);
		for(j = 1; j < 19 && i + (1 << (j - 1)) - 1 <= n; j++) F1[i][j] = max(F1[i][j - 1], F1[i + (1 << (j - 1))][j - 1]);
	}
	for(i = 1; i <= n; i++) {
		G0[i][0] = s0[i] * 2, G1[i][0] = s1[i] * 2 - 1;
		for(j = 1; j < 19 && i - (1 << (j - 1)) + 1 > 0; j++) G0[i][j] = max(G0[i][j - 1], G0[i - (1 << (j - 1))][j - 1]);
		for(j = 1; j < 19 && i - (1 << (j - 1)) + 1 > 0; j++) G1[i][j] = max(G1[i][j - 1], G1[i - (1 << (j - 1))][j - 1]);
	}
	scanf("%d", &Q);
	for(i = 1; i <= Q; i++) {
		l = read(), r = read(), L = 1, R = r - l + 1, ans = 1;
		while(L <= R) {
			mid = (L + R) / 2;
			if(mid % 2 == 0) {
				if(find0(l + mid / 2 - 1, r - mid / 2) >= mid || find1(l + (mid + 1) / 2, r - (mid + 1) / 2) >= mid) ans = mid, L = mid + 1; else R = mid - 1;
			}
			else {
				if(find0(l + (mid + 1) / 2 - 1, r - (mid + 1) / 2) >= mid || find1(l + mid / 2, r - mid / 2) >= mid) ans = mid, L = mid + 1; else R = mid - 1;
			}
		}
		write(ans);
	}
	return 0;
}

自我小结

• 写字符串哈希的话可能会被卡，写manachar事实上并不麻烦。
• 对直接询问区间最值不方便处理的情况，可以考虑二分出某个定值后再判断是否存在。