CF1896D Ones and Twos 题解

CF1896D

如果只有单次询问其实可以双指针，但是这个难以进行拓展。

考虑找点性质。

发现 \(a_i,v\in\{1,2\}\)，从值域上下手。发现若存在和为 \(S\) 的方案，则一定有和为 \(S-2\) 的方案，因为可以直接 \(-2\) 或 \(-1-1\)。

然后就变为找最大的和为奇/偶数了，因为如果最大的都不行就肯定不行了。

于是就只需要支持快速找到最左边和最右边的 \(1\) 的位置，用 set 即可。记得判断一下是否存在 \(1\) 防止 RE。

代码十分简洁。

代码：

#include<bits/stdc++.h>
using namespace std;
int n,m,sum;
int a[200010];
set<int> s[3];
void solve(){
	scanf("%d%d",&n,&m);sum=0;
	for(int i=1;i<=n;i++)scanf("%d",&a[i]),s[a[i]].insert(i),sum+=a[i];
	for(int _=1,opt,x;_<=m;_++){
		scanf("%d%d",&opt,&x);
		if(opt==1){
			if((sum&1)==(x&1)){
				if(sum>=x)puts("YES");
				else puts("NO");
			}else{
				if(!s[1].size())puts("NO");
				else{
					int mx=max(sum-(*s[1].begin())*2+1,sum-(n-(*s[1].rbegin())+1)*2+1);
					if(mx>=x)puts("YES");
					else puts("NO");
				}
			}
		}else{
			int y;scanf("%d",&y);
			sum-=a[x];s[a[x]].erase(x);
			a[x]=y;
			sum+=a[x];s[a[x]].insert(x);
		}
	}
	s[1].clear();s[2].clear();
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--)solve();
	return 0;
}