P5840 题解

_sunkuangzheng_ · 2024-01-04 12:46:00 · 题解

AC 自动机太 hard 了，提供一个无脑 SA 做法。

考虑问题的弱化版本：所有查询在修改之后。我们把所有 s_i 和 t_i 用分隔符隔开，拼在一起得到串 S。查询时找到 S 串中以 t_i 开头的后缀的排名 rk 和长度 len，以 rk 为中心二分得到 \operatorname{LCP} \ge len 的极长区间，在这个区间内数有多少种不同的 t_i 即可。区间数颜色问题可以离线树状数组一只 \log 解决。

考虑一边插入一边查询，相当于增加了时间维度。离线所有操作，做和上面一样的操作，只不过查询变成了 [l,r] 区间内出现了多少个不同的 t_i 满足 time_i \le now。我们知道区间数颜色的本质是二维数点（i \in [l,r],lst_i \in [1,l-1]，lst_i 指元素 a_i 上一次出现的位置），那么增加时间维度后问题就变成了三维数点，CDQ 分治即可。

采用 \log^2 的 SA，记 m = \sum |t_i|,n = \sum |s_i|，时间复杂度 \mathcal O((m+q) \log^2(m+q) +(m+n) \log^2 (m+n))，其中前半部分是 CDQ 分治，后半部分是后缀数组。

但是你 TLE 啦！经过测试发现跑完 SA 就已经 TLE 了。复制 atcoder 头文件里线性 SA 就好了，可以 AC。

/**
 *    author: sunkuangzheng
 *    created: 04.01.2024 11:00:42
**/
#include<bits/stdc++.h>
// #ifdef DEBUG_LOCAL
// #include <mydebug/debug.h>
// debug_helper deg;
// #endif
using ll = long long;
const int N = 4e6+3e5+5;
using namespace std;string s,t;vector<tuple<int,int,int>> qq;
int T,n,al[N],ar[N],q,op,p,m,sa[N],ok[N],rk[N],h[N],st[N][25],len[N],lst[N],mp[N],tr[N],re;
namespace atcoder {
//篇幅原因省略这一部分，见 https://atcoder.github.io/ac-library/production/document_en/string.html
}using namespace atcoder;
void upd(int x,int p){for(;x <= n;x += x & -x) tr[x] += p;}
int qry(int x){for(re = 0;x;x -= x & -x) re += tr[x];return re;}
struct fk{int a,b,c,id;}a[N*3]; 
struct count{
    int cnt,ans[N];
    void add(int x,int y,int z,int id){a[++cnt] = {x,y,z,id};}
    void cdq(int l,int r){
        if(l == r) return ;
        int mid = (l + r) / 2,i = mid + 1,j = l;
        auto cmp = [&](fk a,fk b){return a.b < b.b || a.b == b.b && a.c < b.c;};
        cdq(l,mid),cdq(mid+1,r);
        sort(a+l,a+mid+1,cmp),sort(a+mid+1,a+r+1,cmp);
        for(;i <= r;i ++){
            for(;a[i].b >= a[j].b && j <= mid;j ++) if(!a[j].id) upd(a[j].c,1);
            if(a[i].id != 0) ans[abs(a[i].id)] += (a[i].id > 0 ? 1 : -1) * qry(a[i].c);
        }for(int k = l;k < j;k ++) if(!a[k].id) upd(a[k].c,-1);
    }void sol(int n){for(int i = 1;i <= n;i ++) ans[i] = 0;cnt = 0;}
}hh;
void SA(string &s,int &n){
    n = s.size();
    vector<int> _sa = suffix_array(s);s = " " + s;
    for(int i = 1;i <= n;i ++) sa[i] = _sa[i-1]+1,rk[sa[i]] = i;
}void grgh(int n){
    for(int i = 1,k = 0;i <= n;h[rk[i ++]] = k) 
        for(k --,k = max(k,0);s[i + k] != '#' && s[i + k] == s[sa[rk[i] - 1] + k];k ++); 
    for(int i = 1;i <= n;i ++) st[i][0] = h[i];
    for(int j = 1;j <= __lg(n);j ++) for(int i = 1;i + (1 << j) - 1 <= n;i ++)
        st[i][j] = min(st[i][j-1],st[i+(1<<j-1)][j-1]);
}void los(){
    cin >> n;
    for(int i = 1;i <= n;i ++) cin >> t,al[i] = s.size() + 1,s += t + '#',ar[i] = s.size() - 1,len[i] = t.size();
    cin >> q;int ed = n;
    for(int i = 1;i <= q;i ++){
        cin >> op;
        if(op == 1) cin >> t,al[++n] = s.size() + 1,s += t + '#',ar[n] = s.size() - 1;
        else cin >> p,qq.emplace_back(p,n,i);
    }SA(s,m),grgh(m);
    auto lcp = [&](int i,int j){
        if(i == j) return m - sa[i] + 1;
        int k = __lg(j - i);
        return min(st[i+1][k],st[j-(1<<k)+1][k]);
    };hh.sol(q);
    for(auto [k,id,di] : qq){
        int l,r,ql,qr,le = len[k]; k = rk[al[k]]; 
        for(l = 1,r = k;l <= r;){
            int mid = (l + r) / 2;
            if(lcp(mid,k) >= le) r = mid - 1; else l = mid + 1; 
        }ql = r + 1;
        for(l = k,r = m;l <= r;){
            int mid = (l + r) / 2;
            if(lcp(k,mid) >= le) l = mid + 1; else r = mid - 1;
        }qr = l - 1;
        hh.add(ql-1,ql-1,id,-di),hh.add(qr,ql-1,id,di);
    }for(int i = 1;i <= n;i ++) for(int j = al[i];j <= ar[i];j ++) mp[rk[j]] = i;
    for(int i = 1;i <= m;i ++){
        if(mp[i] <= ed) continue;
        hh.add(i,lst[mp[i]],mp[i],0),lst[mp[i]] = i;
    }//cout << hh.cnt << "\n";
    sort(a+1,a+hh.cnt+1,[&](fk a,fk b){return a.a < b.a || a.a == b.a && a.b < b.b || a.a == b.a && a.b == b.b && a.c < b.c;});
    hh.cdq(1,hh.cnt);
    for(auto [k,id,di] : qq) cout << hh.ans[di] << "\n";
}int main(){
    ios::sync_with_stdio(0),cin.tie(0);
    for(T = 1;T --;) los();
}