CF1286E Fedya the Potter Strikes Back

发表于 更新于 分类于

kmp 好题，着重对 fail 数组的理解

题意

给定字符串 ss 和序列 ww ，初始均为空。
总共 nn 次操作，每次在 ss 末端添加一个小写字符 cc ，在 ww 末端添加一个整数 ww ，每次添加后求出所有满足 s[1,r−l+1]=s[l,r]s[1,r-l+1] = s[l,r] 的区间 [l,r][l,r] 的最小值之和。
强制在线。
其中 1≤n≤6⋅105,0≤w≤230−1,c∈[a,z]1 \leq n \leq 6 \cdot 10^5, 0 \leq w \leq 2^{30}-1, c \in [a, z] 。

思路

考虑到条件 s[1,r−l+1]=s[l,r]s[1,r-l+1] = s[l,r] 不难想到每次添加字符后的答案即为上一次的答案加上当前串的所有 borderborder 的贡献。
那么需要每次添加字符时实时维护当前串的 borderborder 集合 TT 与它们的总贡献 sumsum 。

  • 对于 TT ，考虑添加一个字符后，对于 TT 中的每一个 borderborder ，若它的后一个字符不是 cc ，则需要将它从 TT 中删除，而如果有 c=s[1]c = s[1] 则需要将 11 也加入集合。对于每次添加操作，最多会往集合中加入一个数，每个数最多被删去一次，所以维护 TT 的复杂度是均摊 O(n)O(n) 的。
    对于删去不满足条件的 borderborder 的操作，可以考虑在维护 failfail 数组的同时维护一个 prepre 数组，其中 preipre_i 表示前 i−1i - 1 个字符组成的前缀的 borderborder 集合中最长的不满足条件的 borderborder 长度，每次暴力遍历 prepre 即可，由于均摊操作复杂度有保证。
  • 对于 sumsum ，考虑删去 TT 中的一个 borderborder 后需要减掉其对应的贡献，这个可以用一个单调栈 + 二分解决，对于剩下的 borderborder 均往后拓展了一位，需要将其贡献与 ww 取 minmin ，若新添加 11 则需要加上 ww 的贡献。
    对于将贡献与 ww 取 minmin 的操作，可以考虑对每种贡献 w′w' 用 mapmap 记录一个数量，每次暴力将 mapmap 中大于 ww 的数更新为 ww 。由于每种数字只会被更新一次（更新完即合并了），所以加上 mapmap 的复杂度后维护 sumsum 的复杂度是均摊 O(n⋅logn)O(n \cdot logn) 的。
    注意结果可能会爆 long longlong\ long ，用 int128int128 存答案即可，维护的总复杂度为 O(n⋅logn)O(n \cdot logn) 。

代码

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
80
81
82
83
84
85
86
87
88
/*
    Author: Cupids_Bow
    Time: 2022-08-04 08:40:41
*/
#include<bits/stdc++.h>
using namespace std;

using ll=long long;

constexpr int N=6e5+5;

int n;
char s[N];
int a[N],fail[N],pre[N];
__int128_t ans,sum;
vector<int> sta;
map<int,int> mp;

int qry(int x){
    return a[(*lower_bound(sta.begin(),sta.end(),x))];
}

void print(__int128_t x){
    if(x>=10) print(x/10);
    cout<<(char)(x%10+'0');
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    cin>>n;
    for(int i=1;i<=n;i++){
        char c;
        int w;
        cin>>c>>w;
        c=(c-'a'+ans%26)%26+'a';
        w=w^(ans&((1<<30)-1));
        s[i]=c;
        a[i]=w;
        if(i==1) fail[i]=0;
        else{
            for(int j=fail[i-1];;j=fail[j]){
                if(s[j+1]==s[i]){
                    fail[i]=j+1;
                    break;
                }
                else if(j==0){
                    fail[i]=0;
                    break;
                }
            }
        }
        if(c==s[fail[i-1]+1]) pre[i]=pre[fail[i-1]+1];
        else pre[i]=fail[i-1];
        for(int j=pre[i];j;){
            if(c==s[j+1]){
                j=pre[j+1];
                continue;
            }
            int val=qry(i-j);
            mp[val]--;
            sum-=val;
            if(mp[val]==0) mp.erase(val);
            j=fail[j];
        }
        while(sta.size()&&a[sta.back()]>w) sta.pop_back();
        sta.push_back(i);
        if(s[i]==s[1]){
            mp[w]++;
            sum+=w;
        }
        int cnt=0;
        for(auto it=mp.upper_bound(w);it!=mp.end();){
            sum-=1ll*(it->first-w)*it->second;
            cnt+=it->second;
            auto nex=next(it);
            mp.erase(it);
            it=nex;
        }
        mp[w]+=cnt;
        ans+=sum;
        print(ans);
        cout<<"\n";
    }

    return true&&false;
}