Example
InputCopy
2
3 3
1 2 2
1 2
1 3
2 3
5 3
2 1 2 1 1
1 2
1 3
4 5
OutputCopy
NO
NO
YES
NO
NO
YES
思路:异或哈希模板
AC代码:
#include<bits/stdc++.h>using namespace std;
typedef long long ll;typedef pair<ll, ll>PII;
const int N = 2e6 + 10;
const ll MOD = 1e9 + 7;
const ll INF = 1e18;//生成随机数
mt19937_64 rng(std::chrono::steady_clock::now().time_since_epoch().count());
ll v[N];int main()
{for(int i = 1; i <= N; i ++){v[i] = rng();}//生成随机数为了判断区间内所有的数是否都出现偶数次int t;cin >> t;while(t --){//相同的时候不会输游戏即打成平局int n, q;cin >> n >> q;vector<ll>s(n + 10);for(int i = 1; i <= n; i ++){int x;cin >> x;s[i] = s[i - 1] ^ v[x];}while(q --){int l, r;cin >> l >> r;if(s[r] - s[l - 1] != 0) cout << "NO" << endl;else cout << "YES" << endl;}}return 0;
}