自动搬运

查看原文

来自洛谷，原作者为

	xfrvq **

搬运于2025-08-24 23:05:50，当前版本为作者最后更新于2024-11-07 19:46:01，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

简单哈希。

考虑给定一对相似的序列 $a_n,b_n$，我们如何找出不同的唯一一对 $a_x,b_y$。

注意到 $\sum\limits_{i=1}^n a_i-\sum\limits_{i=1}^n b_i=a_x-b_y$。

同理可构造 $\sum\limits_{i=1}^n {a_i}^2-\sum\limits_{i=1}^n {b_i}^2={a_x}^2-{b_y}^2$。

根据平方差公式，后式除以前式可得 $a_x+b_y$ 的值。$a_x,b_y$ 也就都可以解出来了。

解出来后，验证两个序列分别除去 $a_x,b_y$ 后是否本质相同。采用 random hashing，即为每个数赋一个随机权，两序列本质相同仅当其随机权和相等。

区间和，区间平方和都可以前缀和维护。

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using LL = __int128;

const int N = 1e5 + 5;

int n,m,a[N],b[N];
LL s1[N],s2[N];
ll h[N];
map<int,ll> H;
mt19937 rnd(20081229);

int main(){
	scanf("%d%d",&n,&m);
	for(int i = 1;i <= n;++i){
		scanf("%d",a + i);
		s1[i] = s1[i - 1] + a[i];
		s2[i] = s2[i - 1] + LL(a[i]) * a[i];
		if(!H[a[i]]) H[a[i]] = rnd();
		h[i] = h[i - 1] + H[a[i]];
	}
	for(int l1,r1,l2,r2;m--;){
		scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
		LL v1 = s1[r1] - s1[l1 - 1] - s1[r2] + s1[l2 - 1];
		LL v2 = s2[r1] - s2[l1 - 1] - s2[r2] + s2[l2 - 1];
		if(v1 == 0 || v2 % v1){ puts("NE"); continue; }
		v2 /= v1;
		ll a = (v1 + v2) / 2,b = (v2 - v1) / 2;
		ll h1 = h[r1] - h[l1 - 1],h2 = h[r2] - h[l2 - 1];
		puts(h1 - H[a] == h2 - H[b] ? "DA" : "NE");
	}
	return 0;
}