CF710F String Set Queries

题目描述

你需要对一个字符串集合 $D$ 处理 $m$ 个查询。每个查询有三种类型之一：

1. 向集合 $D$ 中添加一个字符串 $s$。保证字符串 $s$ 之前没有被添加过。
2. 从集合 $D$ 中删除一个字符串 $s$。保证字符串 $s$ 当前在集合 $D$ 中。
3. 给定字符串 $s$，求集合 $D$ 中所有字符串在 $s$ 中出现的次数总和。如果集合 $D$ 中的某个字符串 $p$ 在 $s$ 中出现了多次，则应计入所有出现次数。

请注意，你需要以在线模式（online）解决此问题。这意味着你不能一次读取所有输入。你只能在输出上一个三类查询的答案后读取下一个查询。在你的程序中，你需要在每次输出后调用 C++ 的 fflush 或 Java 的 BufferedWriter.flush 函数。

输入格式

第一行包含一个整数 $m$（$1\le m\le 3\cdot 10^5$），表示查询的数量。

接下来的 $m$ 行，每行包含一个整数 $t$（$1\le t\le 3$）和一个非空字符串 $s$，表示查询的类型以及需要处理的字符串。所有字符串仅包含小写英文字母。

输入中所有字符串总长度不超过 $3\cdot 10^5$。

输出格式

对于每个三类查询，输出一个整数 $c$，表示集合 $D$ 中所有字符串在 $s$ 中出现的次数之和。

输入输出样例 #1

输入 #1

5
1 abc
3 abcabc
2 abc
1 aba
3 abababc

输出 #1

2
2

输入输出样例 #2

输入 #2

10
1 abc
1 bcd
1 abcd
3 abcd
2 abcd
3 abcd
2 bcd
3 abcd
2 abc
3 abcd

输出 #2

3
2
1
0

说明/提示

由 ChatGPT 5 翻译

思路

分块即可。

代码

#include<bits/stdc++.h>
using namespace std;
const long long mod=1e9+33,mod2=1000099721;
const long long wc=131,wc2=133;
long long m,t,op1=0,op2=0,p1[300005],p2[300005],oj=0,wu[300005],wd[300005],wd2=0,wds[300005],wds2=0,os1[300005],os2[300005],md=0,op=0;
string s;
map<pair<long long,long long>,long long> mp;
int main(){
    p1[0]=1;
    for(int i=1;i<=300000;i++){
        p1[i]=p1[i-1]*wc%mod;
    }
    p2[0]=1;
    for(int i=1;i<=300000;i++){
        p2[i]=p2[i-1]*wc2%mod2;
    }
    md=sqrt(300000);
    cin>>m;
    for(int i=1;i<=m;i++){
        cin>>t>>s;
        if(t==1){
            op1=0;
            for(int j=0;j<=s.size()-1;j++){
                op1=(op1*wc+(long long)s[j])%mod;
            }
            op2=0;
            for(int j=0;j<=s.size()-1;j++){
                op2=(op2*wc2+(long long)s[j])%mod2;
            }
            mp[{op1,op2}]++;
            wd[s.size()]++;     
            wu[s.size()]++;       
            if(s.size()>=md+1&&wu[s.size()]==1){
                wds[++wds2]=s.size();
            }
        }
        else if(t==2){
            op1=0;
            for(int j=0;j<=s.size()-1;j++){
                op1=(op1*wc+(long long)s[j])%mod;
            }
            op2=0;
            for(int j=0;j<=s.size()-1;j++){
                op2=(op2*wc2+(long long)s[j])%mod2;
            }
            mp[{op1,op2}]--;
            wd[s.size()]--;            
        }
        else{
            op=0;
            op1=0;
            for(int j=0;j<=s.size()-1;j++){
                op1=(op1*wc+(long long)s[j])%mod;
                os1[j+1]=op1;
            }
            op2=0;
            for(int j=0;j<=s.size()-1;j++){
                op2=(op2*wc2+(long long)s[j])%mod2;
                os2[j+1]=op2;
            }       
            for(int j=1;j<=md&&j<=s.size();j++){
                if(wd[j]!=0){
                    for(int l=1;l+j-1<=s.size();l++){
                        op+=mp[{(os1[l+j-1]-os1[l-1]*p1[j]%mod+mod)%mod,(os2[l+j-1]-os2[l-1]*p2[j]%mod2+mod2)%mod2}];
                    }
                }
            }
            for(int j=1;j<=wds2;j++){
                if(wds[j]<=s.size()){
                    for(int l=1;l+wds[j]-1<=s.size();l++){
                        op+=mp[{(os1[l+wds[j]-1]-os1[l-1]*p1[wds[j]]%mod+mod)%mod,(os2[l+wds[j]-1]-os2[l-1]*p2[wds[j]]%mod2+mod2)%mod2}];
                    }
                }
            }
            cout<<op<<endl;
            cout.flush();
        }
    }
	return 0;//
}