首页 > 代码库 > BZOJ 4896 ：[Thu Summer Camp2016]补退选 Trie树+Vector

BZOJ 4896 ：[Thu Summer Camp2016]补退选 Trie树+Vector

2024-09-27 15:27:39   203人阅读

4896: [Thu Summer Camp2016]补退选

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 315  Solved: 97
[Submit][Status][Discuss]

Description

X是T大的一名老师，每年他都要教授许多学生基础的C++知识。在T大，每个学生在每学期的开学前都需要选课，每
次选课一共分为三个阶段：预选，正选，补退选；其中"补退选"阶段最忙碌。在补退选阶段，学生即可以选课，也
可以退课。对于X老师来说，在补退选阶段可能发生以下两种事件：
1:一个姓名为S的学生选了他的课（姓名S将出现在X的已选课学生名单中）
2:一个姓名为S的学生退了他的课（姓名S将从X的已选课学生名单中移除）
同时，X老师对于有哪些学生选了他的课非常关心，所以他会不定时的查询已选课学生名单，每次查询的格式如下
：最早在哪个事件之后，姓名以S为前缀的学生数量超过了vX老师看你骨骼惊奇，所以想用这个问题考考你，你当
然不会畏惧，所以勇敢的接下了这个任务。
注意1：学生的姓名可能相同，如果有p个姓名相同的学生都选了X老师的课，则他们的姓名将出现在X老师的名单上p次。
注意2：只有已经选了课的学生才会退课，如果姓名为S的学生退课，则在他退课之前X老师的名单上一定有姓名S。
注意3：选课，退课和查询都被定义为"事件"，"事件"的编号从1开始

Input

第一行包含一个正整数n，表示一共发生了n个事件。
接下来n行，每行描述一个事件；每行第一个正整数k表示事件类型：
1.如果k=1，表示选课事件，接下来一个字符串S，表示一个姓名为S的学生选了X老师的课
2.如果k=2，表示退课事件，接下来一个字符串S，表示一个姓名为S的学生退了X老师的课
3.如果k=3，表示查询事件，接下来一个字符串S以及三个非负整数a,b,c，表示X老师想知道最早在第几个事件之后
，姓名以S为前缀的学生数量超过了(a*|ANS|+b)%c，|ANS|表示上次查询事件的答案的绝对值，如果当前是第一次
查询，则|ANS|=0；如果任何时刻都没有超过该值，则答案为-1。注：输入中的所有字符串均只包含小写字母。
 

Output

对于每个查询事件，输出一行表示该查询答案。

Sample Input

6
1 lcaq
3 lca 0 0 5
1 lcq
3 lc 0 1 5
2 lcaq
3 lc 0 1 5

Sample Output

1
3
3

HINT

 

n<=100000，字符串长度 <= 60，输入中的所有字符串只会包含前 10 个小写字母

 

Source

鸣谢Sengxian上传

想法：Trie上每个节点挂一个Vector，存下每个数量最早到达事件。$O(\sum len)$

#include<cstdio>#include<cstring>#include<vector>typedef long long ll;template<class T>inline void read(T&x){    x=0;bool f=0;char c=getchar();    while((c<‘0‘||c>‘9‘)&&c!=‘-‘) c=getchar();if(c==‘-‘)f=1, c=getchar();    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘; c=getchar();}    x=f?-x:x;}const int MAXN(6000010);struct Trie{    int nx[10],now;    std::vector<int>last;}trie[MAXN];int ktot=1;int n,leng,k;ll a,b,c,Ans;char str[100];void update(int k,int y,int pos){    trie[k].now+=y;    if((int)trie[k].last.size()==trie[k].now)     trie[k].last.push_back(pos);}void insert(int y,int pos){    int k=1;    for(int i=1;i<=leng;i++)    {        if(!trie[k].nx[str[i]-‘a‘]){trie[k].nx[str[i]-‘a‘]=++ktot;trie[ktot].last.push_back(0);}        k=trie[k].nx[str[i]-‘a‘];        update(k,y,pos);    }}int query(int limt){    int k=1;    for(int i=1;i<=leng;i++)    {        if(!trie[k].nx[str[i]-‘a‘])return -1;        k=trie[k].nx[str[i]-‘a‘];    }    if((int)trie[k].last.size()<=limt)return -1;    else return trie[k].last[limt];}int main(){//    freopen("C.in","r",stdin);    read(n);    for(int i=1;i<=n;i++)    {        read(k);        scanf("%s",str+1);leng=strlen(str+1);        if(k==1)insert(1,i);  else        if(k==2)insert(-1,i); else        {            read(a);read(b);read(c);            Ans=((ll)a*Ans+b)%c;            Ans=query(Ans+1);            printf("%lld\n",Ans);            Ans=Ans<0?-Ans:Ans;//            fprintf(stderr,"!\n");        }//        fprintf(stderr,"fuck\n");    }    return 0;}

 

BZOJ 4896 ：[Thu Summer Camp2016]补退选 Trie树+Vector


联系
我们