[THUSC2016] 补退选

首先对于所有的字符串进行哈希

构建两个哈希表，均为哈希值映射至vector

我们约定一些东西方便表示

\(v1\) 表示第一个哈希表对应的vector， \(v2\) 表示第二个哈希表对应的vector

\(v1\) 中元素表示当前该前缀对应所有操作编号（可能不正确，但是没影响，具体看下面的 注意 标注的地方）

第二个哈希表的vector（即 \(v2\) ）表示所有历史出现过的情况（即这个vector只加不减）。如果 \(v1.size()\) 超过 \(v2.size()\) ，那么向 \(v2\) 尾部加入 \(v1\) 中元素

那么 \(mp2[x]\) 这个 \(v2\) 的 \(v2[y]\) 表示，编号为 \(v2[y]\) 的操作结束后，哈希值为 \(x\) 的前缀个数为 \(y\)

对于 \(opt1\) ，把 \(s\) 的每一个前缀对应的哈希值丢进map里面，在对应vector最后插入这个操作的编号，复杂度 \(O(|s|)\)

对于 \(opt2\) ，把 \(s\) 的每一个前缀对应的 \(v1\) 的最后一个元素删去。 \(O(|s|)\) 。

对于 \(opt3\) ，询问为 \(v\) ,把 \(s\) 整个串的哈希值对应 \(v2\)，直接询问 \(v2[v+1]\) 对应编号。这一步是 \(O(|s|)\) 的，因为要处理出哈希值。

注意：这样维护 \(opt2\) 并不能保证删去了正确的元素。

比如，我先插入一个 \(aaabzzz\) ，而后又插入了一个 \(aaabyyy\) ，再删除了 \(aaabzzz\) 。设 \(hash("aaab")=x\) 。直接删除最后一个，对 \(mp1[x]\) 删去的是插入 \(aaabyyy\) 的操作编号。

设插入 \(aaabyyy\) 后，前缀 \(aaab\) 的答案为 \(v_0\)

但是由于在对 \(aaabyyy\) 插入时，我把 \(v1\) 尾部元素插入了 \(v2\)，而我会在 \(v2\) 中查询答案。所以对询问为 \(v_0\) 的贡献，已经正确的记录在了 \(v2\) 中，所以删除了也不影响。

这图没有画出 \(v1,v2\) 的区别，所以看不懂不用纠结。

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/hash_policy.hpp>

typedef unsigned long long ull;

const ull BB = 13;
const int N = 66;

using namespace std;
using namespace __gnu_pbds;//pbds跑的快一些

int q , Q;

char s[N]; int len;
ull h[N] , B[N];
void gethash(){
	for(int i = 1; i <= len; ++ i){
		h[i] = h[i - 1] * BB + s[i];
	}
}

gp_hash_table<ull , vector<int> > mp1 , mp2;//1为当前，2为历史
long long lstans = 0;
void solve(){
	int op; cin >> op;
	cin >> (s + 1);
	len = strlen(s + 1);
	gethash();
	if(op == 1){
		for(int i = 1; i <= len; ++ i){
			mp1[h[i]].push_back(Q);
			if(mp1[h[i]].size() > mp2[h[i]].size()){
				mp2[h[i]].push_back(Q);
			}
		}
	}
	if(op == 2){
		for(int i = 1; i <= len; ++ i){
			mp1[h[i]].pop_back();
		}
	}
	if(op == 3){
		long long a , b , c;//注意1e5*1e5>INT_MAX
		cin >> a >> b >> c;
		int v = (a * llabs(lstans) + b) % c;
		if(mp2.find(h[len]) == mp2.end()){
			cout << -1 << endl;
			lstans = -1;
		}
		else if(mp2[h[len]].size() <= v){
			cout << -1 << endl;
			lstans = -1;
		}
		else {
			cout << mp2[h[len]][v] << endl;
			lstans = mp2[h[len]][v];//注意记录lstans，模拟考时我差点没记录，在线改离线qwq
		}
	}
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
//	freopen("C.in" , "r" , stdin);
//	freopen("C.out" , "w" , stdout);
	
	B[0] = 1;
	for(int i = 1; i <= 50; ++ i){
		B[i] = B[i - 1] * BB;
	}
	cin >> q;
	for(Q = 1; Q <= q; ++ Q) solve();
	
	return 0;
}

有问题可以私信轰炸我捏