AGC

ARC

ABC

ABC 250

E. Prefix Equality (整數哈希)

題意

給了兩個長度為 (n) 的數組，判斷兩者前綴的集合是否相同（長度可以不一樣）。

數據范圍
(1leq N,Qleq 2 imes 10^5)
(1leq a_i,b_i leq 10^9)
(1leq x_i,y_i leq N)

思路

• 顯然需要 std::set ，考慮兩個 set 分別記錄兩個數組每個數是否出現
• 用兩個數組對兩個 set 進行整數哈希，h[i] 表示數組前 i 位上的哈希值，如果沒有新的數出現 h[i] = h[i - 1].

Solution

#include<bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
typedef std::pair<int, int> PII;
typedef std::pair<ll, ll> PLL;
#define x first
#define y second
#define pb push_back
#define mkp make_pair
#define endl "
"
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<int> a(n + 1), b(n + 1);
	vector<unsigned int> 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<int> s1, s2;
	h1[0] = h2[0] = 0;
	map<int,ull> 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
" : cout << "No
";
	}
    return 0;
}
`