洛谷P2572-序列操作(双标记线段树)

题目链接:洛谷P2572-序列操作

题意:

给定一个01序列,然后给5种操作:

  1. 0 a b 把[a, b]区间内的所有数全变成0。
  2. 1 a b 把[a, b]区间内的所有数全变成1。
  3. 2 a b 把[a,b]区间内的所有数全部取反,也就是说把所有的0变成1,把所有的1变成0。
  4. 3 a b 询问[a, b]区间内总共有多少个1。
  5. 4 a b 询问[a, b]区间内最多有多少个连续的1。

题解:

硬核双标记线段树,维护最大公共子段和。

对于双标记,首先lazy标记区间复制,rev标记区间翻转。

在pushdown的过程中,需要考虑两点:

  1. 标记的优先级。
  2. 向下传递标记对其他标记的影响。

对于第一点,区间赋值的优先级高于翻转,所以优先向下传递赋值标记。

对于第二点,向下传递赋值标记的时候,子节点的赋值标记直接传递,并清空当前节点及子节点的翻转标记;向下传递翻转标记的时候,需考虑子节点的标记,若子节点已经有了赋值标记,那么子节点的赋值标记即为父节点赋值标记的翻转(即异或1),若子节点没有赋值标记,子节点的翻转标记异或1。

参考代码:

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5 + 10;
int n, m;
struct NODE
{
    int l, r;
    int sum;
    int ls[2], rs[2], ms[2];
    int lazy, rev;
} gss[MAXN << 2];
void pushup(int rt)
{
    gss[rt].sum = gss[rt << 1].sum + gss[rt << 1 | 1].sum;
    for (int i = 0; i <= 1; i++)
    {
        gss[rt].ls[i] = gss[rt << 1].ls[i];
        if (i == 0 && gss[rt << 1].sum == 0)
            gss[rt].ls[i] += gss[rt << 1 | 1].ls[i];
        else if (i == 1 && gss[rt << 1].sum == gss[rt << 1].r - gss[rt << 1].l + 1)
            gss[rt].ls[i] += gss[rt << 1 | 1].ls[i];
        gss[rt].rs[i] = gss[rt << 1 | 1].rs[i];
        if (i == 0 && gss[rt << 1 | 1].sum == 0)
            gss[rt].rs[i] += gss[rt << 1].rs[i];
        else if (i == 1 && gss[rt << 1 | 1].sum == gss[rt << 1 | 1].r - gss[rt << 1 | 1].l + 1)
            gss[rt].rs[i] += gss[rt << 1].rs[i];
        gss[rt].ms[i] = max({gss[rt << 1].ms[i], gss[rt << 1 | 1].ms[i], gss[rt << 1].rs[i] + gss[rt << 1 | 1].ls[i]});
    }
}
void pushdown(int rt)
{
    if (gss[rt].lazy != -1)
    {
        int x = gss[rt].lazy;
        gss[rt << 1].lazy = gss[rt << 1 | 1].lazy = x;
        gss[rt].rev = gss[rt << 1].rev = gss[rt << 1 | 1].rev = 0;
        gss[rt << 1].sum = (gss[rt << 1].r - gss[rt << 1].l + 1) * x;
        gss[rt << 1 | 1].sum = (gss[rt << 1 | 1].r - gss[rt << 1 | 1].l + 1) * x;
        gss[rt << 1].ls[x] = gss[rt << 1].rs[x] = gss[rt << 1].ms[x] = gss[rt << 1].r - gss[rt << 1].l + 1;
        gss[rt << 1].ls[x ^ 1] = gss[rt << 1].rs[x ^ 1] = gss[rt << 1].ms[x ^ 1] = 0;
        gss[rt << 1 | 1].ls[x] = gss[rt << 1 | 1].rs[x] = gss[rt << 1 | 1].ms[x] = gss[rt << 1 | 1].r - gss[rt << 1 | 1].l + 1;
        gss[rt << 1 | 1].ls[x ^ 1] = gss[rt << 1 | 1].rs[x ^ 1] = gss[rt << 1 | 1].ms[x ^ 1] = 0;
        gss[rt].lazy = -1;
    }
    if (gss[rt].rev)
    {
        gss[rt << 1].sum = (gss[rt << 1].r - gss[rt << 1].l + 1) - gss[rt << 1].sum;
        gss[rt << 1 | 1].sum = (gss[rt << 1 | 1].r - gss[rt << 1 | 1].l + 1) - gss[rt << 1 | 1].sum;
        (gss[rt << 1].lazy != -1) ? gss[rt << 1].lazy ^= 1 : gss[rt << 1].rev ^= 1;
        (gss[rt << 1 | 1].lazy != -1) ? gss[rt << 1 | 1].lazy ^= 1 : gss[rt << 1 | 1].rev ^= 1;
        swap(gss[rt << 1].ls[0], gss[rt << 1].ls[1]), swap(gss[rt << 1 | 1].ls[0], gss[rt << 1 | 1].ls[1]);
        swap(gss[rt << 1].rs[0], gss[rt << 1].rs[1]), swap(gss[rt << 1 | 1].rs[0], gss[rt << 1 | 1].rs[1]);
        swap(gss[rt << 1].ms[0], gss[rt << 1].ms[1]), swap(gss[rt << 1 | 1].ms[0], gss[rt << 1 | 1].ms[1]);
        gss[rt].rev = 0;
    }
}
void build(int l, int r, int rt)
{
    gss[rt].l = l, gss[rt].r = r;
    gss[rt].lazy = -1, gss[rt].rev = 0;
    if (l == r)
    {
        int x;
        scanf("%d", &x);
        gss[rt].sum = x;
        gss[rt].lazy = -1, gss[rt].rev = 0;
        gss[rt].ls[x] = gss[rt].rs[x] = gss[rt].ms[x] = 1;
        gss[rt].ls[x ^ 1] = gss[rt].rs[x ^ 1] = gss[rt].ms[x ^ 1] = 0;
        return;
    }
    int mid = (l + r) >> 1;
    build(l, mid, rt << 1);
    build(mid + 1, r, rt << 1 | 1);
    pushup(rt);
}
void update(int L, int R, int x, int rt)
{
    pushdown(rt);
    if (L <= gss[rt].l && gss[rt].r <= R)
    {
        if (x == 0 || x == 1)
        {
            gss[rt].lazy = x;
            gss[rt].sum = (gss[rt].r - gss[rt].l + 1) * x;
            gss[rt].ls[x] = gss[rt].rs[x] = gss[rt].ms[x] = gss[rt].r - gss[rt].l + 1;
            gss[rt].ls[x ^ 1] = gss[rt].rs[x ^ 1] = gss[rt].ms[x ^ 1] = 0;
        }
        else if (x == 2)
        {
            gss[rt].rev ^= 1;
            gss[rt].sum = (gss[rt].r - gss[rt].l + 1) - gss[rt].sum;
            swap(gss[rt].ls[0], gss[rt].ls[1]);
            swap(gss[rt].rs[0], gss[rt].rs[1]);
            swap(gss[rt].ms[0], gss[rt].ms[1]);
        }
        return;
    }
    int mid = (gss[rt].l + gss[rt].r) >> 1;
    if (L <= mid)
        update(L, R, x, rt << 1);
    if (R > mid)
        update(L, R, x, rt << 1 | 1);
    pushup(rt);
}
int querysum(int L, int R, int rt)
{
    if (L <= gss[rt].l && gss[rt].r <= R)
        return gss[rt].sum;
    pushdown(rt);
    int mid = (gss[rt].l + gss[rt].r) >> 1;
    int res = 0;
    if (L <= mid)
        res += querysum(L, R, rt << 1);
    if (R > mid)
        res += querysum(L, R, rt << 1 | 1);
    return res;
}
NODE querygss(int L, int R, int rt)
{
    if (L == gss[rt].l && R == gss[rt].r)
        return gss[rt];
    pushdown(rt);
    int mid = (gss[rt].l + gss[rt].r) >> 1;
    if (mid < L)
        return querygss(L, R, rt << 1 | 1);
    else if (mid >= R)
        return querygss(L, R, rt << 1);
    else
    {
        NODE res, resL = querygss(L, mid, rt << 1), resR = querygss(mid + 1, R, rt << 1 | 1);
        res.sum = resL.sum + resR.sum;
        for (int i = 0; i <= 1; i++)
        {
            res.ls[i] = resL.ls[i];
            if (i == 0 && resL.sum == 0)
                res.ls[i] += resR.ls[i];
            else if (i == 1 && resL.sum == resL.r - resL.l + 1)
                res.ls[i] += resR.ls[i];
            res.rs[i] = resR.rs[i];
            if (i == 0 && resR.sum == 0)
                res.rs[i] += resL.rs[i];
            else if (i == 1 && resR.sum == resR.r - resR.l + 1)
                res.rs[i] += resL.rs[i];
            res.ms[i] = max({resL.ms[i], resR.ms[i], resL.rs[i] + resR.ls[i]});
        }
        return res;
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    build(0, n - 1, 1);
    while (m--)
    {
        int op, x, y;
        scanf("%d%d%d", &op, &x, &y);
        if (op == 0)
            update(x, y, 0, 1);
        else if (op == 1)
            update(x, y, 1, 1);
        else if (op == 2)
            update(x, y, 2, 1);
        else if (op == 3)
            printf("%d\n", querysum(x, y, 1));
        else if (op == 4)
            printf("%d\n", querygss(x, y, 1).ms[1]);
    }
    return 0;
}

发表留言

人生在世,错别字在所难免,无需纠正。