AtCoder Beginner Contest 250E Prefix Equality

题意：给两个数组A,B，进行q组询问，每次询问由A的前x项和B的前y项构成的集合是否相同（数组大小及询问数目为2e5）

最简单的想法就是开两个map，一个记录A取到每一位所得到的集合以及该集合出现的位置，另一个记录B取到每一位所得到的集合，对于每次查询，在A取到B的前y项构成的集合出现的位置中寻找x，如果x存在答案当然就是Yes。但是，在map中用set作为索引寻址的复杂度也是O(set的大小)的，再套q次询问最大复杂度就变成了O(N^2)，显然过不了，需要优化比较两个set是否相等时的时间复杂度，于是想到哈希

我们可以使用一种称为子集哈希的技巧维护一个集合的哈希值：给集合中的每一个数随机赋值为一个long long范围的数作为它的哈希，集合的哈希就是集合中每一个数的哈希值的异或（因为异或的顺序不影响异或结果）。这样，我们只要检测每次insert操作是否成功，如果成功就将当前集合的哈希异或insert的数分配到的随机值（如果没有分配则需要先分配并记录），显然异或不会增加二进制位的数目，因此最终集合的哈希值不会超过long long的界限。这样，我们就可以实现O(1)的set相等判断。

此外，随机值的生成应当使用mt19937库以确保值处在long long范围（而非通常的rand()的32768）

#include <bits/stdc++.h>

using namespace std;

template <typename T> inline T read(){
	T sum = 0;
	int fl = 1,ch = getchar();
	for(; !isdigit(ch); ch = getchar()) if(ch == '-') fl = -1;
	for(; isdigit(ch); ch = getchar()) sum = (sum << 3) + (sum << 1) + ch - '0';
	return sum * fl;
}

constexpr int maxn = 2e5 + 5;

int n,q;
int b[maxn];
map <int,unsigned long long> vis;
map <long long,map<int,bool> > chk;
map <int,long long> findB;

int main(){
	mt19937_64 gen (19260817);
	n = read<int>();
	set<int> a,b;
	long long hashA = 0,hashB = 0;
	for(int i = 1; i <= n; i++){
		int x = read<int>();
		bool flag = a.insert(x).second;
		if(flag){
			unsigned long long rnd;
			if(vis[x]){
				rnd = vis[x];
			}else{
				rnd = gen();
				vis[x] = rnd;
			}
			hashA ^= rnd;
		}
		chk[hashA][i] = true;
	}
	for(int i = 1; i <= n; i++){
		int x = read<int>();
		bool flag = b.insert(x).second;
		if(flag){
			unsigned long long rnd;
			if(vis[x]){
				rnd = vis[x];
			}else{
				rnd = gen();
				vis[x] = rnd;
			}
			hashB ^= rnd;
		}
		findB[i] = hashB;
	}
	q = read<int>();
	while(q--){
		int x,y;
		x = read<int>();
		y = read<int>();
		if(chk[findB[y]][x]){
			puts("Yes");
		}else puts("No");
	}
	return 0;
}