abc367F 判断区间构成的多重集合是否相同

给定长度为N的两个数组A[i]和B[i]，有Q组询问，每次给定(l[i],r[i],L[i],R[i])，问由A[l[i]]_{A[r[i]]构成的multiset，与B[L[i]]}B[R[i]]构成的multiset是否相同？

范围：1<=N,Q<=2E5, 1<=A[i],B[i]<=N, 1<=l[i]<=r[i]<=N, 1<=L[i]<=R[i]<=N

分析：将int映射为u64，因为集合不区分先后，而加法满足交换律，因此用加法来做哈希，又因为是多重集合，相同元素要叠加。为了减少冲突，这里用了3重哈希。

#include <bits/stdc++.h>
using i64 = long long;
using u64 = unsigned long long;

struct hval {
	u64 h1, h2, h3;
	u64 f1(u64 x) { return 19260817 + 1237123ULL * x * x * x; }
	u64 f2(u64 x) { return 71806291 + 3217321ULL * x * x; }
	u64 f3(u64 x) { return 74328249 + 1678931ULL * x; }
	void set(int x) {
		h1 = f1(x & 0x7fffffff) + f1(x >> 31);
		h2 = f2(x & 0x07ffffff) + f2(x >> 27);
		h3 = f3(x & 0x00007fff) + f3(x >> 15);
	}
	hval(u64 a=0, u64 b=0, u64 c=0):h1(a), h2(b), h3(c) {}
	bool operator==(const hval &rhs) const {
		return h1 == rhs.h1 && h2 == rhs.h2 && h3 == rhs.h3;
	}
	friend hval operator+(const hval &a, const hval &b) {
		return hval(a.h1 + b.h1, a.h2 + b.h2, a.h3 + b.h3);
	}
	friend hval operator-(const hval &a, const hval &b) {
		return hval(a.h1 - b.h1, a.h2 - b.h2, a.h3 - b.h3);
	}
};

void solve() {
	int N, Q;
	std::cin >> N >> Q;
	std::vector<int> A(N+1), B(N+1);
	for (int i = 1; i <= N; i++) {
		std::cin >> A[i];
	}
	for (int i = 1; i <= N; i++) {
		std::cin >> B[i];
	}

	std::vector<hval> HA(N+1), HB(N+1);
	for (int i = 1; i <= N; i++) {
		HA[i].set(A[i]);
		HB[i].set(B[i]);
	}
	std::partial_sum(HA.begin(), HA.end(), HA.begin());
	std::partial_sum(HB.begin(), HB.end(), HB.begin());

	for (int i = 1; i <= Q; i++) {
		int l, r, L, R;
		std::cin >> l >> r >> L >> R;
		if (HA[r] - HA[l-1] == HB[R] - HB[L-1]) {
			std::cout << "Yes\n";
		} else {
			std::cout << "No\n";
		}
	}
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	int t = 1;
	while (t--) solve();
	return 0;
}