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

做法

显然分讨 \prod_{i=l}^{r}a_i。

• 若全为 1。则 r-l+1=\sum_{i=l}^{r}a_i=k+1。显然可以特判。
• 若不全为 1。此时 \sum_{i=l}^{r}a_i=k。

显然有结论：

• 若 k>r-l，无解。
• 若 k=r-l，显然有两种方案：或是全为 1，或是只有 1 个 0。如果本身序列中存在 0 则第二种划算，否则第一种划算。
• 若 k<r-l。显然就是要有 k 个 1。我们直接求 \sum_{i=l}^{r}a_i，并与 k 作差求绝对值即可。由于要加快区间求和，所以可以用前缀和。

代码

#include<bits/stdc++.h>
using namespace std;
int a[1000007];
inline int abs(int&x)
{
    return x>=0?x:-x;
}
int main()
{
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n,q,l,r,k,cnt;
    cin>>n>>q;
    for(int i=0;i<n;i++)
    {
        cin>>l;
        a[i+1]=l+a[i];
    }
    for(int i=0;i<q;i++)
    {
        cin>>l>>r>>k;
        if(r-l<k)
        {
            cout<<"-1\n";
        }
        else
        {
            cnt=a[r]-a[l-1];
            if(cnt==r-l+1&&k==r-l)
            {
                cout<<"0\n";
            }
            else
            {
                cout<<abs(cnt-k)<<'\n';
            }
        }
    }
    return 0;
}