Codeforces Round 974 (Div. 3) H. Robin Hood Archery

https://codeforces.com/problemset/problem/2014/H

一道可以用哈希异或和莫队算法做的好题。

题目翻译

莫队做法

//#pragma GCC optimize("Ofast")
//#pragma GCC optimize("Ofast,no-stack-protector,unroll-loops,fast-math")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4.1,sse4.2,avx,avx2,popcnt,tune=native")
#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define double long double
mt19937 rnd(time(0));
const int N=2e6+7;
int a[N];
int sqn;
int n,m;
struct node {
    int l,r,id;
    bool operator < (const node &b)const{
        if(b.l/sqn==l/sqn){
            if((l/sqn)&1)return r<b.r;
            else return r>b.r;
        }else{
            return b.l>l;
        }
    };
}q[N];
bool cnt[1000006];
int now=0;
void cal(int x,int op){
    if(op==1){
        if(cnt[a[x]]==1)cnt[a[x]]=0;
        else cnt[a[x]]=1;
    }
    else {
        if(cnt[a[x]]==1)cnt[a[x]]=0;
        else cnt[a[x]]=1;
    }
    if(cnt[a[x]]%2==0)now--;
    else now++;
}
int ans[N];
void solved(){
    for(int i=1;i<=n;i++)cnt[a[i]]=0;
    cnt[a[1]]=0;
    cin>>n>>m;
    sqn=sqrt(n);
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++){
        int l,r;cin>>l>>r;
        q[i]={l,r,i};
    }
    sort(q+1,q+1+m);
    int l=1,r=1;
    cnt[a[1]]=1;
    now=1;
    for(int i=1;i<=m;i++){
        while(l<q[i].l)cal(l++,0);
        while(l>q[i].l)cal(--l,1);
        while(r<q[i].r)cal(++r,1);
        while(r>q[i].r)cal(r--,0);
        ans[q[i].id]=now;
    }
    for(int i=1;i<=m;i++)cout<<(ans[i]==0 ? "YES":"NO")<<'\n';
}

signed main(){
    auto begin = std::chrono::high_resolution_clock::now();
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int _=1;
    cin>>_;
    while(_--)solved();
    auto end = std::chrono::high_resolution_clock::now();
    auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
    //cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds."; 
    return 0;
}

哈希做法

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define il inline
#define N 200005
#define M 1000005
il ll rd(){
	ll s = 0, w = 1;
	char ch = getchar();
	for (;ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') w = -1;
	for (;ch >= '0' && ch <= '9'; ch = getchar()) s = ((s << 1) + (s << 3) + ch - '0');
	return s * w;
}il ll rnd(){return (rand() | (rand() << 16));}
ll n, m, a[N], l, r, s[N], t[M];
int main(){
	srand(time(0));
	for (int T = rd(); T--;){
		n = rd(), m = rd();
		for (int i = 1; i <= n; i++){
			a[i] = rd();
			if (!t[a[i]]) t[a[i]] = rnd();
			s[i] = s[i - 1] ^ t[a[i]];
		}while (m--) l = rd(), r = rd(), puts((s[r] ^ s[l - 1]) ? "NO" : "YES");
		for (int i = 1; i <= n; i++) t[a[i]] = 0;
	}
	return 0;
}