AGC

ARC

ABC

ABC 250

E. Prefix Equality (整数哈希)

题意

给了两个长度为 \(n\) 的数组，判断两者前缀的集合是否相同（长度可以不一样）。

数据范围
\(1\leq N,Q\leq 2\times 10^5\)
\(1\leq a_i,b_i \leq 10^9\)
\(1\leq x_i,y_i \leq N\)

思路

• 显然需要 std::set ，考虑两个 set 分别记录两个数组每个数是否出现
• 用两个数组对两个 set 进行整数哈希，h[i] 表示数组前 i 位上的哈希值，如果没有新的数出现 h[i] = h[i - 1].

Solution

#include
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair PII;
typedef std::pair PLL;
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "\n"
using namespace std;
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937_64 rd(seed1);
const int mod = 1e9 + 7;

int main(){
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	vector a(n + 1), b(n + 1);
	vector h1(n + 1), h2(n + 1);
	for(int i = 1; i <= n; i++)
		cin >> a[i];
	for(int i = 1; i <= n; i++)
		cin >> b[i];
	set s1, s2;
	h1[0] = h2[0] = 0;
	map mp;
	for(int i = 1; i <= n; i++){
		h1[i] = h1[i - 1];
		h2[i] = h2[i - 1];
		if(!mp.count(a[i])){
			mp[a[i]] = rd();
		}
		if(!s1.count(a[i]))
			h1[i] += mp[a[i]];
		if(!mp.count(b[i]))
			mp[b[i]] = rd();
		if(!s2.count(b[i]))
			h2[i] += mp[b[i]];
		s1.insert(a[i]);
		s2.insert(b[i]);
	}
	int q;
	cin >> q;
	while(q--){
		int x, y;
		cin >> x >> y;
		(h1[x] == h2[y]) ? cout << "Yes\n" : cout << "No\n";
	}
    return 0;
}
`