传送门 神仙题目，吹爆kfj。 dls用的border的那种写法还没有学会。 离线之后hash判周期。 border算法 会补的（一定会的）
#include<bits/stdc++.h> using namespace std; const int maxn = 1e6 + 50; const int seed = 131; typedef unsigned long long ull; ull g[maxn * 2], hash1[maxn * 2]; int ans[maxn], l[maxn], r[maxn], ll, rr,s[maxn*2]; ull get_hash(int l, int r) { return hash1[r] - hash1[l - 1] * g[r - l + 1]; } int trans(char s[]) { if (s[0] == 'd')return 1; if (s[0] == 'r')return 2; if (s[0] == 'm')return 3; if (s[0] == 'f')return 4; if (s[0] == 'l')return 6; if (s[0] == 's') { if (s[1] == 'o') return 5; if (s[1] == 'i') return 7; } } int main() { int n; g[0] = 1; for (int i = 1; i < maxn; i++) g[i] = g[i - 1] * seed; scanf("%d", &n); ll = rr = n + 1; char flag, str[10]; for (int i = 1; i <= n; i++) { scanf(" %c%s", &flag, str); if (flag == 'a') s[rr++] = trans(str); else s[--ll] = trans(str); l[i] = ll; r[i] = rr - 1; } for (int i = ll; i < rr; i++) hash1[i] = hash1[i - 1] * seed + s[i]; for (int i = 1; i <= n; i++) { int res = 0; for (ll = i, rr = n; ll <= rr;) { int mid = ll + rr >> 1; if (get_hash(l[mid], r[mid] - i) == get_hash(l[mid] + i, r[mid])) ll = (res = mid) + 1; else rr = mid - 1; } ans[i]++; ans[res + 1]--; printf("%d\n", ans[i] += ans[i - 1]); } }