P5335 [THUSC2016]补退选(trie)

nofind · 2019-07-08 08:44:18 · 题解

题意：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;
}