自动搬运

查看原文

来自洛谷，原作者为

	OrezTsim 我居然忘记锁号了！但是，我是 goushi 男，我要吃贝！

搬运于2025-08-24 22:37:51，当前版本为作者最后更新于2022-11-16 20:13:14，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

先考虑 $[1,n]$ 的答案。

猜结论。将 $a_i=0$ 视为 $-1$，做前缀和，每一次 $<0$ 就意味着删掉一个 $0$。

再做一遍后缀和，执行同样的操作。

最后的答案就是区间长度 $-$ 删掉的 $0$ 的数量。

事实上，交一发，发现有 40pts，证明贪心是对的。

（但是我真的不会证贪心策略，我只能感性理解，如果有神仙知道请发到评论区 /kk）

那么考虑答案的变化过程。

比方说，当前前缀和数组 $\text{pre}_i=-1$，考虑对 $[i,n]$ 全体 $+1$。

继续碰到 $\text{pre}'_j=-1$（有原来 $\text{pre}_j=-2$），对 $[j,n]$ 全体 $+1$。

那么我们发现，统计做前缀和的过程，其实依次就是找到第一个 $-1,-2,...,-x$。

那么第一轮操作（统计前缀和）的操作次数，也就是 $-\min\limits_{i=1}^n \{\text{pre}_i\}$。

由于第一轮操作会对第二轮操作（统计后缀和）产生影响，考虑影响。

对于现在的后缀数组 $\text{suf}'_i$（在第一轮操作之前为 $\text{suf}_i$），$\Delta=$ 在 $i$ 右侧删除的 $0$ 的个数。

想到这个不好维护，转化为差，即 $-\min\limits_{i=1}^n\{\text{pre}_i\}-$ $i$ 左侧删除的 $0$ 的个数。

根据上侧的贪心策略，在 $i$ 左侧删除的 $0$ 的个数 $=-\min\limits_{j=1}^{i-1}\{\text{pre}_j\}$。

那么 $\text{suf}'_i=\text{suf}_i+(-\min\limits_{i=1}^n\{\text{pre}_i\})-(-\min\limits_{j=1}^{i-1}\{\text{pre}_j\})$。

则最终答案为 $-\min\limits_{i=1}^n \{\text{pre}_i\}+(-\min\limits_{i=1}^n \{\text{suf}'_i\})=-\min\limits_{i=1}^n \{\text{suf}_i+\min\limits_{j=1}^{i-1}\{\text{pre}_j\}\}$。

考虑怎么维护这个东西。

想想，答案其实是对于每一个段 $[i,n]$，都求出 $\min\limits_{j=1}^{i-1}\{\text{pre}_j\}$。

枚举 $i,j$ 的过程本质上也就是枚举互不相交的一个前缀和一个后缀。

问题就转化为，求互不相交的一个前缀和一个后缀的和的最小值。

继续转化，其实一个前缀和一个后缀的和的最小值，就等于全局和减去夹在中间的区间和。

问题等于 $\max\limits_{1 \le l < r \le n}\{(\sum\limits_{k=1}^n a_k)-(\sum\limits_{k=l+1}^{r-1}a_k)\}$。

那么就转化为最大子段和问题。这个东西显然可以推广到区间上。

由于题目问的是最多剩下多少个数，所以要用区间长度减掉维护的答案。

#include <bits/stdc++.h>
#define ls ((rt) << 1)
#define rs ((rt) << 1 | 1)
using namespace std;

const int N = 5e5 + 10; int n, q;
struct Node { int al, sum, pre, suf; } t[N << 2];

inline Node pushup(Node f, Node s) {
    Node res; res.sum = f.sum + s.sum;
    res.pre = max(f.pre, f.sum + s.pre), res.suf = max(s.suf, s.sum + f.suf);
    res.al = max(max(f.al, s.al), f.suf + s.pre); return res;
}

inline void build(int rt, int l, int r) {
    if (l == r) {
        char op; cin >> op;
        t[rt].al = t[rt].sum = t[rt].pre = t[rt].suf = (op == '0'? -1 : 1);
        if (t[rt].al < 0) t[rt].al = 0; return ;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid), build(rs, mid + 1, r);
    t[rt] = pushup(t[ls], t[rs]); return ;
}

inline Node query(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) return t[rt];
    int mid = (l + r) >> 1; Node f, s; int tag = 0;
    if (L <= mid) f = query(ls, l, mid, L, R), ++tag;
    if (R > mid) s = query(rs, mid + 1, r, L, R), tag += 2;
    if (tag == 1) return f; if (tag == 2) return s;
    return pushup(f, s);
}

inline void solve() {
    int l, r; cin >> l >> r;
    Node res = query(1, 1, n, l, r); int len = res.al - res.sum;
    if (len >= r - l + 1) cout << -1 << endl;
    else cout << r - l + 1 - len << endl; return ;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0), cout.tie(0);
    cin >> n >> q; build(1, 1, n);
    while (q--) solve(); return 0;
}