arc072e

题意：给出一个数列a，一个数的初始值为D，按数列顺序操作，每次把D变为$$min(D,abs(D-a[i]))$$。q个询问，每次询问任意修改a数列一个位置数后能否使操作a序列后D值不为0。

设$$b[i]$$表示最小的D初始值使经过i及以后的操作后值不为0。
则$$b[n+1]=1$$
如果$$\lfloor\frac{a[i]}{2}\rfloor\ge b[i+1]$$则$$b[i]=b[i+1]$$,因为$$a[i]$$操作无效
否则$$b[i]=b[i+1]+a[i]$$

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int N=510000;
int n,q;
int a[N],d[N];
ll b[N];
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%d%d",&n,&d[0]);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    b[n+1]=1;
    for(int i=n;i>=1;i--)
    {
        if(a[i]/2>=b[i+1])b[i]=b[i+1];
        else b[i]=b[i+1]+a[i];
    }
    for(int i=1;i<=n;i++)
        d[i]=min(d[i-1],abs(d[i-1]-a[i]));
    scanf("%d",&q);
    for(int i=1,t;i<=q;i++)
    {
        scanf("%d",&t);
        puts(b[t+1]<=d[t-1] ? "YES" : "NO");
    }
    return 0;
}