Loj#2291.「THUSC 2016」补退选 | wzf2000's blog

Loj#2291.「THUSC 2016」补退选

Loj#2291.「THUSC 2016」补退选 题解

题意:

  • 每次加入或删除一个字符串 $S$。
  • 询问前缀为某字符串 $S$ 的字符串数量最早超过 $v$ 的时刻。
  • $n\le 100000,|S|\le 60$。

题解:

  • 加入或删除一个字符串 $S$,都只会对其 $\rm trie$ 树到根路径上的每个点产生影响。
  • 考虑对于每个节点开一个 $\rm vector$ 维护其达到某个值的最早时刻,每次询问输出即可。
  • 时间复杂度 $O(|S|n)$。

代码:

#include <bits/stdc++.h>
#define gc getchar()
using namespace std;
const int N=100009;
int n,last=0;
char str[69];
struct Trie
{
    int rt,cnt,to[N*60][10],now[N*60];
    vector<int> Ans[N*60];
    void init()
    {
        rt=cnt=1;
        memset(now,0,sizeof(now)),memset(to,0,sizeof(to));
        for (int i=0;i<N*60;i++) Ans[i].clear();
    }
    void add(char *a,int len,int T)
    {
        int x=rt;
        for (int i=1;i<=len;i++)
        {
            x=to[x][a[i]-'a']?to[x][a[i]-'a']:to[x][a[i]-'a']=++cnt;
            if ((++now[x])>Ans[x].size()) Ans[x].push_back(T);
        }
    }
    void del(char *a,int len)
    {
        for (int i=1,x=rt;i<=len;i++) now[x=to[x][a[i]-'a']]--;
    }
    int qry(char *a,int len,int S)
    {
        int x=rt;
        for (int i=1;i<=len;i++) x=to[x][a[i]-'a'];
        if (Ans[x].size()<=S) return -1;
        return Ans[x][S];
    }
}tr;
int read()
{
    int x=1;
    char ch;
    while (ch=gc,ch<'0'||ch>'9') if (ch=='-') x=-1;
    int s=ch-'0';
    while (ch=gc,ch>='0'&&ch<='9') s=s*10+ch-'0';
    return s*x;
}
int main()
{
    tr.init();
    n=read();
    for (int i=1;i<=n;i++)
    {
        int op=read();
        scanf("%s",str+1);
        int len=strlen(str+1);
        if (op==1) tr.add(str,len,i);
        if (op==2) tr.del(str,len);
        if (op==3)
        {
            int a=read(),b=read(),c=read();
            int now=(1ll*a*abs(last)+b)%c;
            printf("%d\n",last=tr.qry(str,len,now));
        }
    }
    return 0;
}