题解：CF2014H Robin Hood Archery

· · 题解

题目传送门

分析

发现答案就是对于区间 [l,r]，问是否所有 l\le i\le r 的 a_i，都出现了偶数次。

区间问题，考虑莫队，发现莫队可行。

对于每个查询，先进行最优的排序。

然后每个询问，找到有多少个数字出现了偶数次，再记录出现了几个数，如果两个数相等，则他们能打平（也就是不会落败。他作为后手，可以证明不可能能赢）。

所以莫队模板即可啦！只是统计时有点繁琐，如果有问题，请看代码。

::::::warning[注意] 有多测，注意清空。 ::::::

代码

/*
cnt是统计出现次数的，res是记录偶数的个数，now则是出现个数的出现个数
*/
#include<bits/stdc++.h>
using namespace std ;
const int kMaxN = 2e5 + 5 ;
int n , q ;
int len , res , now ;
int a[kMaxN] , ans[kMaxN] , cnt[1000005] ; 
struct node
{
  int l , r , id ;
}Node[kMaxN] ;
bool cmp(node x , node y)
{
  if(x.l / len == y.l / len)
  {
    if(x.l / len % 2) return x.r < y.r ;
    return x.r > y.r ;
  }
  return x.l < y.l ;
}
void ADD(int x)
{
  cnt[a[x]]++ ; 
  if(cnt[a[x]] == 1) now++ ; // 记录
  // 为了要把之前的减一或者加一抵消，要加二或者减二
  if(cnt[a[x]] == 0) res++ ;
  else if(abs(cnt[a[x]] % 2) && cnt[a[x]] - 1 != 0) res -= 2 ;
  else if(abs(cnt[a[x]] % 2)) res-- ;
  else if(cnt[a[x]] % 2 == 0) res += 2 ;
}
void SUB(int x)
{
  cnt[a[x]]-- ;
  // 与ADD相似
  if(cnt[a[x]] == 0) now-- ;
  if(cnt[a[x]] == 0) res++ ;
  else if(cnt[a[x]] % 2 == 0) res += 2 ;
  else if(abs(cnt[a[x]] % 2) && cnt[a[x]] + 1 != 0) res -= 2 ;
  else if(abs(cnt[a[x]] % 2)) res-- ;
}
void solve()
{
  cin >> n >> q ;
  len = sqrt(n) ;
  for( int i = 1 ; i <= n ; i++ ) cin >> a[i] ;
  for( int i = 1 ; i <= q ; i++ )
  {
    cin >> Node[i].l >> Node[i].r ;
    Node[i].id = i ;
  }
  sort(Node + 1 , Node + q + 1 , cmp) ;
  // 多测清空
  memset(cnt , 0 , sizeof cnt) ; 
  now = res = 0 ;
  int l = 1 , r = 0 ;
  for( int i = 1 ; i <= q ; i++ )
  {
    while(l < Node[i].l) SUB(l++) ;
    while(l > Node[i].l) ADD(--l) ;
    while(r < Node[i].r) ADD(++r) ;
    while(r > Node[i].r) SUB(r--) ;
    // cout << now << " " << res << " " << Node[i].id << "\n" ;
    ans[Node[i].id] = ((Node[i].r - Node[i].l + 1) % 2 ? 0 : now == res) ;
  }
  for( int i = 1 ; i <= q ; i++ ) cout << (ans[i] ? "YES\n" : "NO\n") ;
}
int main()
{
  ios::sync_with_stdio(0) , cin.tie(0) , cout.tie(0) ;
  int t = 1 ;
  cin >> t ;
  while(t--) solve() ;
  return 0 ;
}