题解：CF2014H Robin Hood Archery

· · 题解

CF题目传送门

题目大意

Robin 和 Sheriff 比赛，Robin 先手，每次比赛他们选择 l - r 的区间内的目标进行射击。射击编号为 i 的目标会加 a_i 分，然后这个目标被摧毁。两人初始得分均为 0。若 Sheriff 能获胜或平局输出 YES，否则输出 NO。

题目思路

由于 Robin 先手，为了获胜，当轮到 Robin 时他一定会选择当前剩余目标中最大分值的目标。所以无论如何 Sheriff 一定不会获胜，最多只能平局。

如果能平局，说明 l - r 这个区间内所有出现过的数的出现次数均为偶数（这样两人才能平均分，达到平局的效果）。此时用莫队维护区间数值出现次数。

剩下的便是板子了。

不会的去这里。

Code

附上完整代码。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
struct node{
    int l,r,id;
}q[N];
int a[N];
int ans[N],cnt[N];
int n,m,sq;
bool cmp(node x,node y){
    if(x.l / sq != y.l / sq) return x.l / sq < y.l / sq;
    else return x.r / sq < y.r / sq; 
}
int cur = 1;
void add(int p){
    cnt[a[p]] ++;
    if(cnt[a[p]] & 1) cur ++;
    else cur --;
}
void del(int p){
    cnt[a[p]] --;
    if(cnt[a[p]] & 1) cur ++;
    else cur --;
}
void solve(){
    cur = 1;
    cin >> n >> m;
    sq = min((int)sqrt(n) + 1,n);
    for(int i = 0;i < n;i ++){
        cin >> a[i];
        cnt[a[i]] = 0;
    } 
    for(int i = 0;i < m;i ++){
        cin >> q[i].l >> q[i].r;
        q[i].l --;
        q[i].r --;
        q[i].id = i;
        ans[i] = 0;
    }
    sort(q,q + m,cmp);
    cnt[a[0]] ++;
    int L = 0,R = 0;
    for(int i = 0;i < m;i ++){
        while(R < q[i].r) add(++ R);
        while(L > q[i].l) add(-- L);
        while(L < q[i].l) del(L ++);
        while(R > q[i].r) del(R --);    
        ans[q[i].id] = cur;
    }
    for(int i = 0;i < m;i ++){
        if(ans[i]) cout << "NO\n";
        else cout << "YES\n";
    }
}
int main(){
    int T;
    cin >> T;
    while(T --) solve();
    return 0;
}