【BZOJ4896】[Thu Summer Camp2016]补退选 Trie树

时间:2022-12-17 09:22:22

【BZOJ4896】[Thu Summer Camp2016]补退选

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 个小写字母

题解:直接给Trie树上的每个节点都开一个vector,记录它第一次人数超过i的时间,就没有然后了~

只包含前10个小写字母是骗人的,不要信

好吧实测只考虑前10个小写字母可以AC,就是样例过不去~

#include <cstdio>
#include <cstring>
#include <iostream>
#include <vector>
using namespace std;
struct node
{
	int ch[26],siz;
	vector<int> v;
}p[300000];
int n,tot,ans;
char str[70];
int main()
{
	int i,j,a,b,c,d,l,u;
	scanf("%d",&n);
	tot=1;
	for(i=1;i<=n;i++)
	{
		scanf("%d%s",&d,str),l=strlen(str);
		if(d==1)
		{
			for(u=1,j=0;j<l;j++)
			{
				a=str[j]-'a';
				if(!p[u].ch[a])	p[u].ch[a]=++tot;
				u=p[u].ch[a],p[u].siz++;
				if(p[u].siz>p[u].v.size())	p[u].v.push_back(i);
			}
		}
		if(d==2)
		{
			for(u=1,j=0;j<l;j++)	a=str[j]-'a',u=p[u].ch[a],p[u].siz--;
		}
		if(d==3)
		{
			for(u=1,j=0;j<l&&u;j++)	a=str[j]-'a',u=p[u].ch[a];
			scanf("%d%d%d",&a,&b,&c),a=((long long)a*ans+b)%c;
			if(!u||a>=p[u].v.size())
			{
				ans=1;
				printf("-1\n");
				continue;
			}
			ans=p[u].v[a];
			printf("%d\n",ans);
		}
	}
	return 0;
}