题解 | #小红的01串（六）#

F 小红的01串（六）

~~碎碎念：第一眼看题意，这不是非常经典的线段树么。然后开始写，都把 push_down 写完了，结果发现 $n$ 是 $1e9$ 的，要加个离散化才行。~~

建议正在学线段树的同学都可以做做这题，如果能独立把代码调出来的话相信你的收获一定会很大。

我们先思考 $n \le 10^5$ 左右的情况。我们可以开一个线段树，维护以下信息：

将当前区间修改为 $0$ 开头的好串和 $1$ 开头的好串的最小修改次数（分别记作 $num0$ 和 $num1$ ）

首先考虑合并操作，我们在 push_up 的时候，当前节点的 $num0$ 就是左子树的 $num0$ 加上右子树的 $num0$ 或者 $num1$ ，取决于左子树维护的区间长度。如果是奇数，说明 $0$ 开头的好串一定是 $1$ 结尾，那么右子树需要从 $0$ 开头，因此需要用 $num0$ 更新，另外一个情况同理。

再考虑更新操作，注意到有两个区间修改操作，先考虑单种：

若只有区间修改为 $1$ 的话可以考虑加个 $lazyTag1$ ，然后直接更新区间 $num0$ 和 $num1$ 。
若只有区间取反，可以考虑加个 $lazyTag2$ ，然后交换区间 $num0$ 和 $num1$ 即可。

接下来考虑复合操作：

若对一个区间先取反后修改为 $1$ ，相当于取反操作无效，只用管修改操作。
若对一个区间先修改为 $1$ 后再取反，相当于区间修改为 $0$ ，直接更新 $num0$ 和 $num1$ 。

因此我们看得出来，对于一个区间的两个 $lazyTag$ ，他们的先后顺序是有区别的，因此我们可以将两个 $lazyTag$ 记作是第几次操作，方便我们更新。

这里需要注意一点：若我们在 push_down 的过程中，发现离当前区间的操作的最近操作是取反，并且当前又更新了一个取反操作，那么我们应该要做的是把取反的 $lazyTag$ 给取消掉，而不是更新取反的 $lazyTag$ ，否则会影响下面子区间的取反操作。

好了，分析完以后，发现 $n \le 10^9$ ，所以我们不能像刚刚一样每个叶节点只维护一个位置，因此要让每个叶节点维护一个区间，例如我们的操作区间依次是 $[1, 6],[2, 9],[6, 10]$ ，先变成左闭右开的区间，即 $[1,7),[2,10),[6,11)$ ，把端点记下来也就是 $1, 2, 6, 7, 10, 11$ ，最后将相邻两个数之间合并成一个左闭右开的区间即可。 $[1,2),[2,6),[6,7),[7,10),[10, 11)$ 。离散化后就可以转化了。

时间复杂度 $O(q \cdot \log q)$

#include <bits/stdc++.h>
#define ls (u << 1)
#define rs (u << 1 | 1)
using namespace std;
typedef long long LL;
typedef pair<int, int> PII;
const int N = 3e5 + 10;

struct qy {
    int opt, l, r;
} a[N];
struct node {
    int l, r;       // 管理的左右区间，用离散化之后的值代替
    int ranL, ranR; // 表示管理的左右区间
    int num0, num1; // 将当前区间修改为0开头的好串和1开头的好串的修改次数
    int lazy_tag;   // 更新区间翻转的lazy是第几次操作
    int lazy_1;     // 更新区间为1的lazy是第几次操作
} tr[N << 2];

vector<int> v;
int getIdx(int x) {
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

void calc(int u, int lt, int l1) {
    int len = tr[u].ranR - tr[u].ranL + 1;
    if (lt && l1 && lt > l1) {
        // 先1后翻，等价于赋0
        tr[u].num0 = len / 2;
        tr[u].num1 = (len + 1) / 2;
    } else if (l1) {
        // 剩下的情况就是翻后1或者有1无翻，直接赋值为1
        tr[u].num0 = (len + 1) / 2;
        tr[u].num1 = len / 2;
    } else if (lt) {
        swap(tr[u].num0, tr[u].num1);
    }
}

void push_down(int u) {
    if (tr[u].lazy_1) tr[ls].lazy_1 = tr[rs].lazy_1 = tr[u].lazy_1;
    if (tr[u].lazy_tag) {
        // down下去取反操作时，注意看最近的操作是不是取反
        // 如果是的话就需要更新子区间的lazy_tag为0
        if (tr[ls].lazy_1 < tr[ls].lazy_tag) tr[ls].lazy_tag = 0;
        else tr[ls].lazy_tag = tr[u].lazy_tag;
        if (tr[rs].lazy_1 < tr[rs].lazy_tag) tr[rs].lazy_tag = 0;
        else tr[rs].lazy_tag = tr[u].lazy_tag;
    }
    calc(ls, tr[u].lazy_tag, tr[u].lazy_1);
    calc(rs, tr[u].lazy_tag, tr[u].lazy_1);
    tr[u].lazy_1 = tr[u].lazy_tag = 0;
}

void push_up(int u) {
    tr[u].ranL = tr[ls].ranL, tr[u].ranR = tr[rs].ranR;
    // 更新num0
    tr[u].num0 = tr[ls].num0;
    int len_l = tr[ls].ranR - tr[ls].ranL + 1;
    if (len_l & 1) tr[u].num0 += tr[rs].num1;
    else tr[u].num0 += tr[rs].num0;
    // 更新num1
    tr[u].num1 = tr[ls].num1;
    if (len_l & 1) tr[u].num1 += tr[rs].num0;
    else tr[u].num1 += tr[rs].num1;
}

void build(int u, int l, int r) {
    tr[u].l = l, tr[u].r = r;
    if (l == r) {
        tr[u].ranL = v[l - 1];
        tr[u].ranR = v[l] - 1;
        int len = tr[u].ranR - tr[u].ranL + 1;
        tr[u].num0 = len / 2;
        tr[u].num1 = (len + 1) / 2;
        return ;
    }
    int mid = (l + r) >> 1;
    build(ls, l, mid);
    build(rs, mid + 1, r);
    push_up(u);
}

void update(int u, int st, int ed, int opt, int num_opt) {
    // opt=1表示更新当前区间为1，否则就是翻转
    int l = tr[u].l, r = tr[u].r;
    if (st <= l && r <= ed) {
        if (opt == 1) {
            tr[u].lazy_1 = num_opt;
            calc(u, 0, num_opt);
        }
        if (opt == 2) {
            if (tr[u].lazy_1 < tr[u].lazy_tag) tr[u].lazy_tag = 0;
            else tr[u].lazy_tag = num_opt;
            calc(u, num_opt, 0);
        }
        return ;
    }
    push_down(u);
    int mid = (l + r) / 2;
    if (st <= mid) update(ls, st, ed, opt, num_opt);
    if (ed > mid) update(rs, st, ed, opt, num_opt);
    push_up(u);
}

node query(int u, int st, int ed) {
    int l = tr[u].l, r = tr[u].r;
    if (st <= l && r <= ed) return tr[u];
    push_down(u);
    int mid = (l + r) >> 1;
    node ans;
    ans.num0 = -1;
    if (st <= mid) {
        node tmp = query(ls, st, ed);
        ans = tmp;
    }
    if (ed > mid) {
        node tmp = query(rs, st, ed);
        if (ans.num0 == -1) ans = tmp;
        else {
            // 更新答案的num0
            int lenl = ans.ranR - ans.ranL + 1;
            if (lenl & 1) ans.num0 += tmp.num1;
            else ans.num0 += tmp.num0;
            // 更新答案的num1
            if (lenl & 1) ans.num1 += tmp.num0;
            else ans.num1 += tmp.num1;
            ans.ranR = tmp.ranR;
        }
    }
    return ans;
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("1.in", "r", stdin);
    freopen("1.out", "w", stdout);
#endif
    int m, q;
    cin >> m >> q;
    for (int i = 1; i <= q; i ++ ) {
        cin >> a[i].opt >> a[i].l >> a[i].r;
        v.push_back(a[i].l);
        v.push_back(a[i].r + 1);
    }
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    int n = v.size() - 1;
    build(1, 1, n);
    for (int i = 1; i <= q; i ++ ) {
        int opt = a[i].opt;
        int l = getIdx(a[i].l) , r = getIdx(a[i].r + 1) - 1;
        if (opt == 1) update(1, l, r, 1, i);
        else if (opt == 2) update(1, l, r, 2, i);
        else {
            node ans = query(1, l, r);
            cout << min(ans.num0, ans.num1) << endl;
        }
    }
    return 0;
}