题解：P11272 「Diligent-OI R1 B」DlgtArray

题目传送门

思路

首先我们可以轻松发现区间积是 0 或 1。

那么分开处理：

• 如果区间积是 0，那说明我们要让 \sum_{i = l}^{r} a_i = k，那么输出它与 k 的绝对值即可，另外因为 \sum_{i = l}^{r} a_i 最大为 r-l+1，此时它要等于 k+1，所以 r-l 大于 k 时无解。

• 如果区间积为 1，那说明我们要让 \sum_{i = l}^{r} a_i = k+1，那么和就是 r-l+1，如果它不为 k+1 那么同区间积为 0 的情况。

注意要用前缀和优化。

然后就做完了。

CODE

#include<bits/stdc++.h>
using namespace std;
int n,q,a[1000005],s[1000005],l,r,k;
int main()
{
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        s[i]=s[i-1]+a[i];
    }
    while(q--)
    {
        scanf("%d%d%d",&l,&r,&k);
        if(s[r]-s[l-1]==r-l+1)//区间积为1
        {
           if(k>r-l)  printf("-1\n");//特判
           else  if(r-l+1==k+1)  printf("0\n");//可以
           else  printf("%d\n",abs(r-l+1-k));//否则输绝对值 
        }
        else//区间积为0
        {
            if(k>r-l)  printf("-1\n");//特判
            else  printf("%d\n",abs(s[r]-s[l-1]-k));//注意要绝对值 
        }
    }
    return 0;
}