线段树优化贪心策略。

· · 题解

先考虑 [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;
}