CodeTON Round 7 : D. Ones and Twos

不参加だった回。
https://codeforces.com/contest/1896/problem/D

問題

1と2で構成される数列Aが与えられる。
以下のクエリを順次処理せよ。

• 整数Sが与えられるので、Aのうち、連続な部分列で和がSとなるものがあるか答える。
• Aの1要素を更新する。

解法

和が2以上の整数Vとなる数列があるなら、先頭または末尾の要素を消すことでV-2も作れる。
よってAの和をXとしたとき、以下を判定すればよい。

• X≧SかつXとSの偶奇が一緒なら、条件を満たす。
• XとSの偶奇が不一致の場合、先頭または末尾の1を含まないようにしたとき、V以上の数列を作れるか判定すればよい。

int T;
int N,Q;
int A[101010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>T;
	while(T--) {
		cin>>N>>Q;
		int sum=0;
		set<int> one;
		FOR(i,N) {
			cin>>A[i];
			sum+=A[i];
			if(A[i]==1) one.insert(i);
		}
		while(Q--) {
			cin>>i;
			if(i==1) {
				cin>>x;
				int ok=0;
				if(x%2==sum%2) {
					if(sum>=x) ok=1;
				}
				else if(one.size()) {
					if(sum-(2**one.begin()+1)>=x) ok=1;
					if(sum-(2*(N-1-*one.rbegin())+1)>=x) ok=1;
				}
				
				
				if(ok) {
					cout<<"YES"<<endl;
				}
				else {
					cout<<"NO"<<endl;
				}
			}
			else {
				cin>>x>>y;
				x--;
				if(A[x]==y) continue;
				one.erase(x);
				sum-=A[x];
				A[x]=y;
				sum+=A[x];
				if(A[x]==1) one.insert(x);
			}
		}
		
	}
}

まとめ

思ったよりシンプルな解法。