GDKOI 2021 提高組 Day1 第三題 回文
題目大意
- 給出長為 n n n的串,和 q q q組詢問,每次詢問區間中的最長回文串。
- n , q ≤ 5 ∗ 1 0 5 n,q\le5*10^5 n,q≤5∗105
題解
- 可以先用manachar求出以每個位置為中心的回文串,詢問時二分答案,然後在區間中判斷是否存在長度為 m i d mid mid的回文串,用ST表維護區間最值。
- 注意二分判斷時并非在整個區間 [ l , r ] [l,r] [l,r]中找最大值,而需分别将左端點右移和右端點左移大約 m i d mid 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事實上并不麻煩。
- 對直接詢問區間最值不友善處理的情況,可以考慮二分出某個定值後再判斷是否存在。