专栏文章

题解:CF2014H Robin Hood Archery

CF2014H题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性,并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioe6ex2
此快照首次捕获于
2025/12/02 17:44
3 个月前
此快照最后确认于
2025/12/02 17:44
3 个月前
查看原文

分析

发现答案就是对于区间 [l,r][l,r],问是否所有 lirl\le i\le raia_i,都出现了偶数次。
区间问题,考虑莫队,发现莫队可行。
对于每个查询,先进行最优的排序。
然后每个询问,找到有多少个数字出现了偶数次,再记录出现了几个数,如果两个数相等,则他们能打平(也就是不会落败。他作为后手,可以证明不可能能赢)。
所以莫队模板即可啦!只是统计时有点繁琐,如果有问题,请看代码。
注意
有多测,注意清空。

代码

CPP
/*
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 ;
}

评论

0 条评论,欢迎与作者交流。

正在加载评论...