题解：CF1896D Ones and Twos

lyhqwq · 2024-05-29 15:27:20 · 题解

Solution

一眼题，这能蓝？

如果我们能找到一个前缀的和为 x，那么答案为 YES。

否则一定可以找到一个前缀 [1,p] 的和为 x+1，此时我们只需要在 [1,n-p+1] 和 [p,n] 中找到一个 1 即可。

用树状数组维护区间和可以做到 O(n\log^2 n)。

Code

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int _;
int n,q;
int a[N];
namespace BIT{
    int tree[N];
    int lowbit(int x){return x&(-x);}
    void update(int x,int v){
        for(int i=x;i<=n;i+=lowbit(i)) tree[i]+=v;
    }
    int query(int x){
        int ans=0;
        for(int i=x;i;i-=lowbit(i)) ans+=tree[i];
        return ans;
    }
    int Q(int l,int r){return query(r)-query(l-1);}
}
using namespace BIT;
int main(){
    scanf("%d",&_);
    while(_--){
        scanf("%d%d",&n,&q);
        for(int i=1;i<=n;i++) tree[i]=0;
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),update(i,a[i]);
        while(q--){
            int op,x,v;
            scanf("%d%d",&op,&x);
            if(op==1){
                int l=1,r=n,p=0;
                while(l<=r){
                    int mid=(l+r)>>1;
                    if(query(mid)>=x) p=mid,r=mid-1;
                    else l=mid+1;
                }
                if(!p){puts("NO");continue;}
                if(query(p)==x) puts("YES");
                else{
                    if(query(n-p+1)!=2*(n-p+1)||query(n)-query(p-1)!=2*(n-p+1)) puts("YES");
                    else puts("NO");
                }
            }
            else{
                scanf("%d",&v);
                update(x,-a[x]);
                a[x]=v;
                update(x,a[x]);
            }
        }
    }
    return 0;
}