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;
}