来自机房大佬 FFT 的简单解法。
思路
首先有个结论：如果 \(a\) 中存在一个子串的和为 \(x\) (\(x>2\))，那么也就一定存在一个子串之和为 \(x-2\)。怎么证明？其实和为 \(x\) 的子串有 \(3\) 种情况：
- \(\text{1}\dots \text{1}\) 两边都为 \(1\) 时把两边删去就能得到 \(x-2\)。
- \(\text{2}\dots \text{1}\) 一边是 \(2\) 一边是 \(1\) 时删 \(2\) 即可。
- \(\text{2}\dots \text{2}\) 两边都是 \(2\) 随便删一个即可。
有了这个结论，我们就可以维护一个区间总和 \(sum\)。当 \(s>sum\) 时肯定不存在，先判掉。接下来如果 \(s \equiv sum\pmod 2\)，也就是 \(s\) 与 \(sum\) 奇偶性相同时，根据上面的结论 \(sum\) 一直减 \(2\) 就能得到 \(s\) 了。最后一种情况 \(s\) 与 \(sum\) 奇偶性不同时，我们就需要一些 \(1\) 去改变 \(sum\) 的奇偶性。找到最左边的 \(1\) 的位置，记为 \(l\)，那么在 \(l\) 前面的全部是 \(2\)，删去无法改变 \(sum\) 奇偶，故必须再删去 \(l\) 位置的一个 \(1\)，才能让 \(sum\) 与 \(s\) 奇偶相同。这时就只需判断去掉前 \(l\) 个数的 \(sum^{\prime}\) 是否 \(\ge s\)，满足条件就可以一直减 \(2\) 得到 \(s\) 了。对于最右边的 \(1\) 做一次相同的判断即可。
维护的话选用 set，将每个 \(1\) 的位置存入 set 中。修改就把新的 \(1\) 位置加入（或者删除旧的 \(1\) 位置），同时更新一下 \(sum\) 就好了。
code
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int t;
int n,a[2000005],sum,q;
set<int>s;
void solve(){
while(!s.empty())s.erase(s.begin());
cin>>n>>q;
sum=0;
for(int i=1;i<=n;++i){
cin>>a[i];
sum+=a[i];
if(a[i]==1)s.insert(i);
}
while(q--){
int sl;
char op;
cin>>op>>sl;
if(op==1){
if(sl>sum){
cout<<"NO"<<endl;
continue;
}
if(sl%2==sum%2){//奇偶性相同
cout<<"YES"<<endl;
continue;
}
if(s.empty()){//没有1，sum、s奇偶性又不一样就无解
cout<<"NO"<<endl;
continue;
}
int l=*s.begin();
auto p=s.end();p--;
int r=*p;//获取最左、最右的1的位置
if(sum-(l-1)*2-1>=sl||sum-(n-r)*2-1>=sl)cout<<"YES"<<endl;//去掉前面和后面判断
else cout<<"NO"<<endl;
}
else{
int x;
cin>>x;
if(a[sl]==x)continue;
if(a[sl]==1)s.erase(s.find(sl));//更新
else s.insert(sl);
sum+=x-a[sl];
a[sl]=x;
}
}
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>t;
while(t--)solve();
return 0;
}