CF1286E Fedya the Potter Strikes Back 题解
jiangly
2020-01-10 19:07:21
#### 题意
你有一个序列，序列的每一个位置有一个字母 $c_i$ 和一个数 $w_i$。一个区间的权值定义为区间内 $w_i$ 的最小值。
初始时序列为空，你要执行 $n$ 次操作，每次在序列末尾添加一个元素（字母和数），并求出操作后序列的每一个满足下列条件的区间的权值和：
- 该区间和与其长度相等的前缀形成的字符串相同。
强制在线。
#### 限制
$1\le n\le 600000$, $|\Sigma|=26$。
#### 题解
考虑在每次加入一个字符后，求出所有合法后缀（即 border）的权值和。容易想到用 KMP 算法解决。
具体的，我们维护 border 的集合。加入一个字符 $c_i$ 后，对集合的改变为：
- 如果一个 border 对应前缀的下一个字符不是 $c$，将其删除。
- 如果 $c_i=c_0$，加入长度为 $1$ 的 border。
由于最多加入 $n$ 个 border，所以每次操作删除的 border 个数是均摊 $O(1)$ 的。
我们考虑如何快速找到被删除的 border。由于这些 border 都在 KMP 算法中从 $i$ 到 $0$ 的路径上（即 $i$, $\mathrm{next}_i$, $\mathrm{next}_{\mathrm{next}_i},\ldots,0$），我们对每一个节点记录其第一个后继字符不一样的祖先，这样我们就能在 $O(1)$ 时间内找到下一个被删除的 border。根据上面的分析，这样做的复杂度是均摊 $O(1)$ 的。
最后是权值的处理。在删除一个 border 时，需要询问它的权值，可以通过单调栈 + 二分解决。还需要把所有大于 $w_i$ 的权值修改为 $w_i$，我们使用 `std::map` 维护每个权值以及出现次数，修改时暴力找到所有大于 $w_i$ 的权值，这样做的复杂度是均摊 $O(\log n)$。
时间复杂度：$O(n\log n)$。
#### 代码
```cpp
#include <iostream>
#include <vector>
#include <string>
#include <iomanip>
#include <map>
#include <algorithm>
constexpr long long P = 1'000'000'000'000'000'000;
long long ansH, ansL;
int ans26, ansB;
int n;
std::string s;
char c;
std::vector<int> anc, nxt, w, stk{0};
std::map<int, int> cnt;
void print() {
if (ansH == 0) {
std::cout << ansL << "\n";
return;
}
std::cout << ansH << std::setw(18) << std::setfill('0') << ansL << "\n";
}
int query(int pos) {
return w[*std::lower_bound(stk.begin(), stk.end(), pos)];
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cin >> n;
anc.resize(n + 1);
nxt.resize(n + 1);
w.resize(n);
std::cin >> c >> w[0];
s += c;
ans26 = w[0] % 26;
ansL = ansB = w[0];
print();
long long sum = 0;
for (int i = 1, j = 0; i < n; ++i) {
std::cin >> c >> w[i];
c = (c - 'a' + ans26) % 26 + 'a';
s += c;
w[i] ^= ansB;
while (j > 0 && c != s[j])
j = nxt[j];
if (c == s[j])
++j;
nxt[i + 1] = j;
if (c == s[nxt[i]]) {
anc[i] = anc[nxt[i]];
} else {
anc[i] = nxt[i];
}
for (int k = i; k > 0; ) {
if (s[k] == c) {
k = anc[k];
} else {
int v = query(i - k);
--cnt[v];
sum -= v;
if (cnt[v] == 0)
cnt.erase(v);
k = nxt[k];
}
}
if (s[0] == c) {
++cnt[w[i]];
sum += w[i];
}
while (!stk.empty() && w[i] <= w[stk.back()])
stk.pop_back();
stk.push_back(i);
int nw = 0;
for (auto it = cnt.upper_bound(w[i]); it != cnt.end(); ) {
sum -= 1LL * (it -> first - w[i]) * it -> second;
nw += it -> second;
auto j = std::next(it);
cnt.erase(it);
it = j;
}
cnt[w[i]] += nw;
long long res = w[stk[0]] + sum;
ansL += res;
if (ansL >= P) {
ansL -= P;
++ansH;
}
ans26 = (ans26 + res) % 26;
ansB = (ansB + res) & ((1 << 30) - 1);
print();
}
return 0;
}
```