P5335 题解
显然如果可以离线是特别好做的，只要在每个节点存储问题每次修改后回答即可。
那这道题强制在线，我们不能边修改边统计是否到了答案，不妨直接把可能成为答案的所有数给算出来。
具体地，每次加入一个字符串后，统计前缀出现的次数的最大值是否超过原先的最大值，如果超过，就记录这个数。
每次查询就可以查到前缀出现的最多次数是否大于询问次数了。
具体实现可以使用一个 vector。
代码：
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define eps 1e-8
const int inf=0x3f3f3f3f;
const int Maxn=7e6+10;
struct trie{
int val;
int ch[15];
}t[Maxn];
vector<int> res[Maxn];
int tot=0;
void add(string str,int tim)
{
int now=0;
for(int i=0;i<str.size();i++)
{
if(!t[now].ch[str[i]-'a'])
{
t[now].ch[str[i]-'a']=++tot;
}
now=t[now].ch[str[i]-'a'];
t[now].val++;
if(res[now].size()<t[now].val)
{
// cout<<now<<":push "<<tim<<endl;
res[now].push_back(tim);
}
}
}
void del(string str)
{
int now=0;
for(int i=0;i<str.size();i++)
{
now=t[now].ch[str[i]-'a'];
t[now].val--;
}
}
int query(string str,int id)
{
int now=0;
for(int i=0;i<str.size();i++)
{
if(!t[now].ch[str[i]-'a']) return -1;
now=t[now].ch[str[i]-'a'];
if(res[now].size()<=id) return -1;
}
return res[now][id];
}
signed main()
{
int T;
scanf("%lld",&T);
int lstans=0;
for(int Case=1;Case<=T;Case++)
{
int opt;
scanf("%lld",&opt);
if(opt==1)
{
string str;
cin>>str;
add(str,Case);
}else if(opt==2){
string str;
cin>>str;
del(str);
}else{
string str;
int a,b,c;
cin>>str;scanf("%lld%lld%lld",&a,&b,&c);
int qu=(a%c*abs(lstans%c)%c+b%c)%c;
lstans=query(str,qu);
printf("%lld\n",lstans);
}
}
return 0;
}