或许我们可以用 map?

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=4e5+10;
int ch[N][10],siz[N],lenn;char st[N];
unordered_map<int,int>dp[N];
void ins(char s[],int x)
{
	int len=strlen(st+1),p=0;
	for(int i=1;i<=len;i++)
	{
		int j=s[i]-'a';
		if(!ch[p][j])ch[p][j]=++lenn;
		p=ch[p][j];
		siz[p]++;
		if(!dp[p][siz[p]])dp[p][siz[p]]=x;
	}
}
void del(char s[])
{
	int len=strlen(st+1),p=0;
	for(int i=1;i<=len;i++)
	{
		int j=s[i]-'a';
		p=ch[p][j];
		siz[p]--;
	}
}
int query(char s[],int x)
{
	int len=strlen(st+1),p=0;
	for(int i=1;i<=len;i++)
	{
		int j=s[i]-'a';
		if(!ch[p][j])return 0;
		p=ch[p][j];
	}
	return dp[p][x];
}
signed main()
{
	int q;cin>>q;int lst=0;
	for(int i=1;i<=q;i++)
	{
		int op;cin>>op;scanf("%s",st+1);
		if(op==1)ins(st,i);
		if(op==2)del(st);
		if(op==3)
		{
			int a,b,c;cin>>a>>b>>c;
			int x=(a*lst+b)%c;x++;
			int ans=query(st,x);
			if(ans==0)cout<<-1<<'\n',lst=1;
			else cout<<ans<<'\n',lst=ans;
		}
	}
	return 0;
}

警示后人:开long long,a*|ans|会超

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,ch[6000010][11],ed[6000010],id;
vector<pair<int,int>> v[6000010];
void ins(string s,int x){
	int p=0;
	for(int i=0;i<s.size();i++){
		int j=s[i]-'a';
		if(!ch[p][j])ch[p][j]=++id;
		p=ch[p][j];
		ed[p]++;
		if(v[p].empty()||v[p].back().second<ed[p]){
			v[p].push_back({x,ed[p]});
		}
	}
}
void del(string s){
	int p=0;
	for(int i=0;i<s.size();i++){
		int j=s[i]-'a';
		p=ch[p][j];
		ed[p]--;
	}
}
int find(string s,int k){
	int p=0;
	for(int i=0;i<s.size();i++){
		p=ch[p][s[i]-'a'];
		if(!p)return -1;
	}
	if(v[p].empty()||v[p].back().second<k)return -1;
	int l=0,r=v[p].size()-1;
	while(l<r){
		int mid=(l+r)>>1;
		if(v[p][mid].second>=k)r=mid;
		else l=mid+1;
	}
	return v[p][l].first;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	string s;
	int la=0;
	for(int i=1;i<=n;i++){
		int op;
		cin>>op;
		if(op==1){
			cin>>s;
			ins(s,i);
		}
		else if(op==2){
			cin>>s;
			del(s);
		}
		else{
			cin>>s;
			int a,b,c;
			cin>>a>>b>>c;
			int k=((ll)a*la+b)%c+1;
			cout<<(la=find(s,k))<<'\n';
			if(la==-1)la=1;
		} 
	}
	return 0;
}

题意：https://www.luogu.org/problemnew/show/P5335

本篇题解主要是为学长补个代码~

说下做法：

我们把学生姓名插入一个trie树，同时对每个节点维护一个sum数组

插入或删除一个字符串,就在路径上的sum上+1、-1,当sum第一次大于vector的size(即突破了之前的数量),就在vector后插入事件时间time

查询的时候暴力在trie上查询即可。

code:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=1000010;
int n,ans,tot;
int sum[maxn];
int trie[maxn][26];
char s[maxn];
vector<int>a[maxn];
void insert(char *s,int delta,int id)
{
    int len=strlen(s+1),now=0;
    for(int i=1;i<=len;i++)
    {
        int c=s[i]-'a';
        if(!trie[now][c]) trie[now][c]=++tot;
        now=trie[now][c];
        sum[now]+=delta;
        if(sum[now]>(int)a[now].size()) a[now].push_back(id);
    }
}
int query(char *s,int k)
{
    int len=strlen(s+1),now=0;
    for(int i=1;i<=len;i++)
    {
        int c=s[i]-'a';
        now=trie[now][c];
        if((int)a[now].size()<=k) return -1;//注意超过:<= 
    }
    return a[now][k];
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        int op;scanf("%d",&op);
        if(op==1) scanf("%s",s+1),insert(s,1,i);
        if(op==2) scanf("%s",s+1),insert(s,-1,i);
        if(op==3)
        {
            scanf("%s",s+1);
            ll a,b,c;scanf("%lld%lld%lld",&a,&b,&c);
            ll num=(a*(ll)abs(ans)+b)%c;
            ans=query(s,(int)num);printf("%d\n",ans);
        }
    }
    return 0;
}