AtCoder Beginner Contest 250E Prefix Equality「子集哈希」

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;
}
暂无评论

发送评论 编辑评论


				
|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇