神仙做法

似乎搞$+1, -1$的前缀和后缀和是常见的套路

懵逼的 题目

扯淡的 题解

这题很神仙 看YJQ大爷的题解完全看不懂Orz 最后参(抄)悟(袭)了一波代码…

首先我们如果把序列中的$0$变成$1$, 然后再把序列中的$1$变成$-1$, 显然这个玩意就是要我们删掉一些数, 让这个区间里的任意 前缀/后缀和 都要非负

所以我们就是要找一个最小的$fro_i + suf_j (i < j)$, 他的相反数就是要删掉的$1$的个数

当时我就想不明白: 这个$i, j$中间的那些部分怎么办啊…后来发现如果$i$向后移动, $j$向前移动不会让这个$fro_i + suf_j$更小的话, 说明中间这个部分一定是已经合法, 不必再删掉$1$了…

真是个神仙做法

沙茶的 代码

具体的实现 我们可以发现这个区间的前缀和其实就是全局前缀和的这一个部分减去区间左端点的左边, 后缀和同理, 于是我们可以直接找最小值, 然后再用这些值减出来输出答案

我现在也能抄题解一遍过了呢 _(:з」∠)_

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#define MAXN (200000 + 5)
#define LS(dq) ((dq) << 1)
#define RS(dq) (((dq) << 1) | 1)
#define INF (0x7ffffff)
using namespace std;
struct node
{
    int le, ri, minfr, minsu, minz;
}b[MAXN << 2];
int fr[MAXN], su[MAXN], n, ans, minpre, a[MAXN], q;
void js(int dq, int le, int ri)
{
    b[dq].le = le, b[dq].ri = ri;
    if (le == ri)
    {
        b[dq].minfr = fr[le];
        b[dq].minsu = su[le];
        b[dq].minz = INF;
        return ;
    }
    int mi = (le + ri) >> 1;
    js(LS(dq), le, mi);
    js(RS(dq), mi + 1, ri);
    b[dq].minfr = min(b[LS(dq)].minfr, b[RS(dq)].minfr);
    b[dq].minsu = min(b[LS(dq)].minsu, b[RS(dq)].minsu);
    b[dq].minz = min(min(b[LS(dq)].minz, b[RS(dq)].minz), b[RS(dq)].minsu + b[LS(dq)].minfr);
}
void cx(int dq, int le, int ri)
{
    if (b[dq].le == le && b[dq].ri == ri)
    {
        ans = min(ans, b[dq].minz);
        ans = min(ans, b[dq].minsu + minpre);
        minpre = min(minpre, b[dq].minfr);
        return ;
    }
    int mi = (b[dq].le + b[dq].ri) >> 1;
    if (ri <= mi)
        cx(LS(dq), le, ri);
    else if (le > mi)
        cx(RS(dq), le, ri);
    else
        cx(LS(dq), le, mi), cx(RS(dq), mi + 1, ri);
}
int main()
{
    scanf("%d%d", &n, &q);
    for (int i = 1, srx; i <= n; i++)
        scanf("%1d", &srx), a[i + 1] = (srx ? -1 : 1);
    for (int i = 2; i <= n + 1; i++)
        fr[i] = fr[i - 1] + a[i];
    for (int i = n + 1; i > 1; i--)
        su[i] = su[i + 1] + a[i];
    js(1, 1, n + 2);
    for (int i = 1, srl, srr; i <= q; i++)
    {
        scanf("%d%d", &srl, &srr);
        srr += 2;
        ans = minpre = INF;
        cx(1, srl, srr);
        printf("%d\n", fr[srl] + su[srr] - ans);
    }
    return 0;
}

By 联赛钦定爆零的 Cansult