变换01串

首先我们可以发现，一个串中相邻相同的段显然可以被同时操作，也就是说例如我们可以在串 $11001100$ 上使用如同串 $1010$ 的操作，那么我们现在考虑 $1010$ 这种“缩过”的串的最小操作次数的是否已经达到了 $11001100$ 的最优解呢？答案是没错，因为我们反过去想，我们要把 $1010$ 变成 $11001100$ ，可以理解为不断在 $1010$ 加字符，我们发现往串里面加一个字符不可能对答案有优化，反而我还要考虑操作这个新加的字符，所以“缩”掉之后的串的答案一定是最优的。

那么我们现在实际上就要求得一个相邻不同的串的最小操作次数，于是我们就会愉快的发现答案一定是长度减一，比如 $1010$ 无论如何都要3次。那么我们现在考虑如何在线解决题目要解决的问题。对区间询问和操作，于是我们就想能否用线段树维护整个过程。

那么首先树上的结点肯定要存答案的，所以我存个缩完之后的长度就行了，那么左右儿子节点要合并，怎么更新父节点答案？我们发现，两个区间合并，我们只需要关心左儿子的尾和右儿子首部即可，我们如果“左尾”和“右首”相同，那么父节点缩完之后的长度必然是左儿子和右儿子的长度和减一，否则不用减一。父亲的首部自然等于左儿子的首部，父亲的尾部自然等于右儿子的尾部。综上，在树上的节点中，我们只要维护三个值，缩完之后的长度，首部的值，尾部的值。那么取反怎么操作？实际上取反就是首部尾部取反，缩完之后的长度肯定是不会变的。

这里注意取反是区间操作，所以我们是需要用 $l a z y$ 维护一下还有多少次反转没有下传给儿子，在 $l a z y$ 下放的时候，只有 $l a z y$ 是奇数的时候需要对树上的儿子节点进行一次取反，否则不用（毕竟操作偶数次等于没操作）。我们可以把两个区间合并重载成加法减少代码难度。

#include <bits/stdc++.h>
#define lson (rt<<1)
#define rson (rt<<1|1)

using namespace std;

const int N = 1e5 + 10;

struct node {
    int l;
    int r;
    int cnt;
    node operator + (const node &t) {
        if (r == t.l) return {l, t.r, cnt + t.cnt - 1};
        return {l, t.r, cnt + t.cnt};
    }
};

int n, q;
node tree[N << 2];
int lz[N << 2];

void build(int rt, int l, int r) {
    if (l == r) {
        int x; scanf("%1d", &x);
        tree[rt].cnt = 1;
        tree[rt].l = tree[rt].r = x;
        return ;
    }
    int mid = l + r >> 1;
    build(lson, l, mid);
    build(rson, mid + 1, r);
    tree[rt] = tree[lson] + tree[rson];
}

void push_down(int rt) {
    if (lz[rt]) {
        if (lz[rt] & 1) {
            tree[lson].l = !tree[lson].l;
            tree[lson].r = !tree[lson].r;
            tree[rson].l = !tree[rson].l;
            tree[rson].r = !tree[rson].r;
        }
        lz[lson] += lz[rt];
        lz[rson] += lz[rt];
        lz[rt] = 0;
    }
}

void update(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) {
        lz[rt]++;
        tree[rt].l = !tree[rt].l;
        tree[rt].r = !tree[rt].r;
        return ;
    }
    push_down(rt);
    int mid = l + r >> 1;
    if (mid >= L) update(lson, l, mid, L, R);
    if (mid < R) update(rson, mid + 1, r, L, R);
    tree[rt] = tree[lson] + tree[rson];
}

node query(int rt, int l, int r, int L, int R) {
    if (L <= l && r <= R) return tree[rt];
    push_down(rt);
    int mid = l + r >> 1;
    if (mid < L) return query(rson, mid + 1, r, L, R);
    else if (mid >= R) return query(lson, l, mid, L, R);
    return query(lson, l, mid, L, R) + query(rson, mid + 1, r, L, R);
}

int main() {
    scanf("%d%d", &n, &q);
    build(1, 1, n);
    while(q--) {
        int t, L, R; scanf("%d%d%d", &t, &L, &R);
        if (t == 1) {
            printf("%d\n", query(1, 1, n, L, R).cnt - 1);
        }
        else {
            update(1, 1, n, L, R);
        }
    }
}

题解 | #变换01串#

变换01串