事实证明卡住的地方比我预想的要弱智一些，构思的时候已经想到了均摊，但对
border
的变化规律似乎缺乏更深的理解，也对最值相关缺乏研究，导致没有想到另一个均摊。
当然，这题也带来一个直觉，就是 border 相关的工程一般比较轻量级。
第一眼是 border 的四种求法中的 SAM，后来发现显然不用这么复杂，考虑
KMP 的过程即可。
注意到一个前缀的所有 border 是 KMP
失配树上的一条祖先链。想借此维护，但变化量看上去并不小，主要是 变为
的时候，可能接上了一条完全不同的祖先链，然后就卡在这儿了。
但事实上，我们直接考虑每个 border
串，在加入一个字符之后，它要么长度也加 ，要么就不是 border 串了。
注意到处理完上述变化之后，最多只会有一个长度为 的 border 串新加入进来（因为剩下的
border 串都是由上一轮的 border 整体加 而来）。
所以删除操作可以暴力执行，我们可以找到每个要删除的 border
串，然后更新相应的信息。
那么如何快速找到那些要删除的 border 串呢。
之前说过，一个前缀的所有 border 是失配树上的祖先链，也就是 ，我们对于每个
，维护最深的一个后继字符与它不同的祖先
，即满足 的最深的点。在遍历祖先的过程中，使用 加速即可。
至于 border 串长整体
怎么做，设当前加入了
个字符，考察一个长度为 的 串，它的区间从加入前的 变为了 ，我们发现，对于这些串，它们的权值只是对当前加入的 取了个 。
那么现在就是要维护一堆数，支持对所有数取 和维护和。
我们可以用 map 维护每种权值的出现次数，要对 取 时，把比 大的权值都直接变为 即可。
考察 map 中不同元素个数的变化情况，容易证明这里的均摊复杂度是 的。
所以总时间复杂度是 的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
| #include <bits/stdc++.h>
using namespace std;
template<typename T>
inline void write(const T &a)
{
if(a >= 10) write(a / 10);
putchar(a % 10 + '0');
}
const int N = 6e5 + 5,MASK = (1 << 30) - 1;
typedef long long ll;
typedef __int128 lll;
int n;
int w[N],s[N];
int stk[N],top;
map<int,int> mp;
int nxt[N];
ll ans;
lll lastans;
int anc[N];
inline int Qpos(int pos)
{
return w[*lower_bound(stk + 1,stk + top + 1,pos)];
}
int main()
{
cin >> n;
int j = 0;
nxt[1] = 0;
char ch;
cin >> ch >> w[1];
s[1] = ch - 'a';
lastans = w[1];
stk[++top] = 1;
write(lastans);
putchar('\n');
for(int i = 2;i <= n;i++)
{
char ch;
cin >> ch >> w[i];ch -= 'a';
w[i] ^= lastans & MASK;
s[i] = (ch + lastans) % 26;
while(j && s[i] != s[j + 1]) j = nxt[j];
if(s[i] == s[j + 1]) ++j;
nxt[i] = j;
if(s[i] == s[nxt[i - 1] + 1]) anc[i - 1] = anc[nxt[i - 1]];
else anc[i - 1] = nxt[i - 1];
for(int k = i - 1;k;)
{
if(s[k + 1] == s[i]) k = anc[k];
else
{
int val = Qpos(i - k);
--mp[val];
if(mp[val] == 0) mp.erase(val);
ans -= val;
k = nxt[k];
}
}
if(s[1] == s[i])
++mp[w[i]],ans += w[i];
while(top && w[stk[top]] >= w[i])
--top;
stk[++top] = i;
int num = 0;
auto it = mp.upper_bound(w[i]);
while(it != mp.end())
{
num += it -> second;
ans -= 1ll * (it -> first - w[i]) * it -> second;
mp.erase(it);
it = mp.upper_bound(w[i]);
}
mp[w[i]] += num;
lastans += w[stk[1]] + ans;
write(lastans);
putchar('\n');
}
return 0;
}
|
这是一道总结 border
变化规律和最值变化规律的好题，对向后加入字符的问题，border
有比较简明的变化方式；对很多数不断地 ，也可以使用均摊复杂度做到优秀的结果。
思考的大方向没有什么问题，但是细节并没有想清楚，这是需要改进的。