CF710F String Set Queries 题解
CF710F String Set Queries
题目描述
你需要对一个字符串集合D DD处理m mm个查询。每个查询有三种类型之一：
- 向集合D DD中添加一个字符串s ss。保证字符串s ss之前没有被添加过。
- 从集合D DD中删除一个字符串s ss。保证字符串s ss当前在集合D DD中。
- 给定字符串s ss，求集合D DD中所有字符串在s ss中出现的次数总和。如果集合D DD中的某个字符串p pp在s ss中出现了多次，则应计入所有出现次数。
请注意，你需要以在线模式（online）解决此问题。这意味着你不能一次读取所有输入。你只能在输出上一个三类查询的答案后读取下一个查询。在你的程序中，你需要在每次输出后调用 C++ 的 fflush 或 Java 的 BufferedWriter.flush 函数。
输入格式
第一行包含一个整数m mm（1 ≤ m ≤ 3 ⋅ 10 5 1 \leq m \leq 3 \cdot 10^{5}1≤m≤3⋅105），表示查询的数量。
接下来的m mm行，每行包含一个整数t tt（1 ≤ t ≤ 3 1\leq t \leq 31≤t≤3）和一个非空字符串s ss，表示查询的类型以及需要处理的字符串。所有字符串仅包含小写英文字母。
输入中所有字符串总长度不超过3 ⋅ 10 5 3 \cdot 10^{5}3⋅105。
输出格式
对于每个三类查询，输出一个整数c cc，表示集合D DD中所有字符串在s ss中出现的次数之和。
输入输出样例 #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>usingnamespacestd;constlonglongmod=1e9+33,mod2=1000099721;constlonglongwc=131,wc2=133;longlongm,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<longlong,longlong>,longlong>mp;intmain(){p1[0]=1;for(inti=1;i<=300000;i++){p1[i]=p1[i-1]*wc%mod;}p2[0]=1;for(inti=1;i<=300000;i++){p2[i]=p2[i-1]*wc2%mod2;}md=sqrt(300000);cin>>m;for(inti=1;i<=m;i++){cin>>t>>s;if(t==1){op1=0;for(intj=0;j<=s.size()-1;j++){op1=(op1*wc+(longlong)s[j])%mod;}op2=0;for(intj=0;j<=s.size()-1;j++){op2=(op2*wc2+(longlong)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();}}elseif(t==2){op1=0;for(intj=0;j<=s.size()-1;j++){op1=(op1*wc+(longlong)s[j])%mod;}op2=0;for(intj=0;j<=s.size()-1;j++){op2=(op2*wc2+(longlong)s[j])%mod2;}mp[{op1,op2}]--;wd[s.size()]--;}else{op=0;op1=0;for(intj=0;j<=s.size()-1;j++){op1=(op1*wc+(longlong)s[j])%mod;os1[j+1]=op1;}op2=0;for(intj=0;j<=s.size()-1;j++){op2=(op2*wc2+(longlong)s[j])%mod2;os2[j+1]=op2;}for(intj=1;j<=md&&j<=s.size();j++){if(wd[j]!=0){for(intl=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(intj=1;j<=wds2;j++){if(wds[j]<=s.size()){for(intl=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();}}return0;//}