[bzoj 4896] [Thu Summer Camp2016]补退选

一个可重集, n个事件: - 加入一个字符串 - 删除一个字符串 (保证先前存在) - 查询最早在第几个事件后, 集合中以s为前缀的字符串数量超过k, 不存在输出-1

强制在线. (n≤10^5, 字符串长度≤60, 字符集=前10个小写英文字母) 先前阅读过一些dalao的游记, 已知: 本题存在线性做法, 骗人写可持久化.

考虑Trie树, 则问题转化为: 链修改+查询某点的权值最早何时超过k / 点修改+查询某子树权值之和最早何时超过k.

第一个方向更好做. 进一步发现, 对每个点, 直接把所有 (存在的) k的答案保存下来就可以了. 时间空间是允许的, 因为每次最多添加|s|个新的答案, 而|s|≤60.

typedef long long ll;

const int N = 1e5 * 60;

int ptr = 2, ch[N+2][10], cnt[N+2];
vector<int> v[N+2];

void add(char* s, int t)
{
	int x = 1;
	while (*s) {
		int c = *s - 'a';
		if (!ch[x][c]) ch[x][c] = ptr++;
		x = ch[x][c];
		if (++cnt[x] > (int)v[x].size())
			v[x].push_back(t);
		++s;
	}
}

void remove(char* s)
{
	int x = 1;
	while (*s) {
		--cnt[x = ch[x][*s - 'a']];
		++s;
	}
}

int query(char* s, int k)
{
	int x = 1;
	while (*s) {
		int c = *s - 'a';
		if (!ch[x][c]) return -1;
		x = ch[x][c];
		++s;
	}
	return k < (int)v[x].size() ? v[x][k] : -1;
}

int main()
{
	int n;
	ll ans = 0;
	
	scanf("%d", &n);
	rep (i, 1, n+1) {
		int k;
		char s[61];
		ll a, b, c;
		scanf("%d%s", &k, s);
		if (k == 1) {
			add(s, i);
		} else if (k == 2) {
			remove(s);
		} else {
			scanf("%lld%lld%lld", &a, &b, &c);
			printf("%lld\n", ans = query(s, (a*abs(ans) + b) % c));
		}
	}

	return 0;
}