<题解>[SCOI2010]序列操作

线段树大水题
但是这道大水题打了两天就对了。为什么?可以去看看这篇帖子
线段树分别维护左右连续0/1段,区间最大0/1段,1的数量(0的数量可以直接算出),然后是推平和翻转的标记。
pushup50行,老套路不想说了
pushdown还是挺简单的(虽然看到全WA我内心是崩溃的然后怀疑人生),如果有推平直接覆盖翻转标记,如果要推平先检测推平标记,有推平标记直接翻转推平标记,否则翻转翻转标记。
自认为我的pushdown还是写的很简单的,其他题解写一长串。

#include <cstdio>
#include <cstring>
#include <cctype>
#include <algorithm>

struct Read
{
    //...
} read;

const int N = 100000 + 10;

namespace SegTree
{

struct Node
{
    int l, r, cnt1, lc[2], rc[2], maxc[2];
    char reverse_flag, all_flag;
    inline void set_all(int v)
    {
        reverse_flag = false;
        all_flag = (v == 1) ? 1 : -1;
        maxc[v] = lc[v] = rc[v] = r - l + 1;
        maxc[1 - v] = lc[1 - v] = rc[1 - v] = 0;
        cnt1 = maxc[1];
    }
    inline void reverse(void)
    {
        if (all_flag)
        {
            set_all(all_flag == -1);
            return;
        }
        reverse_flag ^= 1;
        cnt1 = r - l + 1 - cnt1;
        std::swap(lc[0], lc[1]);
        std::swap(rc[0], rc[1]);
        std::swap(maxc[0], maxc[1]);
    }
} nd[N * 4];

#define LV (p << 1)
#define RV (LV + 1)
#define P (nd[p])
#define L (nd[LV])
#define R (nd[RV])
#define MID ((P.l + P.r) >> 1)

inline void update(Node &to, Node &l, Node &r)
{
    to.cnt1 = l.cnt1 + r.cnt1;
    for (int i = 0; i < 2; ++i)
    {
        to.lc[i] = l.lc[i] + ((l.lc[i] == l.r - l.l + 1) ? r.lc[i] : 0);
        to.rc[i] = r.rc[i] + ((r.rc[i] == r.r - r.l + 1) ? l.rc[i] : 0);
        to.maxc[i] = std::max(l.rc[i] + r.lc[i], std::max(l.maxc[i], r.maxc[i]));
    }
}

inline void update(int p)
{
    update(P, L, R);
}

void build(int p, int l, int r)
{
    P.l = l, P.r = r;
    if (l == r)
    {
        P.set_all(read);
        return;
    }
    int mid = MID;
    build(LV, l, mid);
    build(RV, mid + 1, r);
    update(p);
}

void pushdown(int p)
{
    if (P.all_flag)
    {
        L.set_all(P.all_flag == 1);
        R.set_all(P.all_flag == 1);
        P.all_flag = false;
        return;
    }
    if (P.reverse_flag)
    {
        L.reverse();
        R.reverse();
        P.reverse_flag = false;
        return;
    }
}

void tp_v(int p, int l, int r, int v)
{
    if (l <= P.l && P.r <= r)
    {
        P.set_all(v);
        return;
    }
    pushdown(p);
    int mid = MID;
    if (l <= mid)
        tp_v(LV, l, r, v);
    if (mid < r)
        tp_v(RV, l, r, v);
    update(p);
}

void rev(int p, int l, int r)
{
    if (l <= P.l && P.r <= r)
    {
        P.reverse();
        return;
    }
    pushdown(p);
    int mid = MID;
    if (l <= mid)
        rev(LV, l, r);
    if (mid < r)
        rev(RV, l, r);
    update(p);
}

int tot(int p, int l, int r)
{
    if (l <= P.l && P.r <= r)
        return P.cnt1;
    pushdown(p);
    int mid = MID, ret = 0;
    if (l <= mid)
        ret = tot(LV, l, r);
    if (mid < r)
        ret += tot(RV, l, r);
    return ret;
}

Node lx(int p, int l, int r)
{
    if (l <= P.l && P.r <= r)
        return P;
    pushdown(p);
    int mid = MID;
    Node ret;
    if (l <= mid && mid < r)
    {
        Node left = lx(LV, l, r), right = lx(RV, l, r);
        update(ret, left, right);
        return ret;
    }
    else if (l <= mid)
        return lx(LV, l, r);
    else
        return lx(RV, l, r);
}

} // namespace SegTree

int n, m;

int main(void)
{
    n = read, m = read;
    SegTree::build(1, 1, n);
    while (m--)
    {
        int a = read, b = read, c = read;
        b += 1;
        c += 1;
        switch (a)
        {
        case 0:
            SegTree::tp_v(1, b, c, 0);
            break;
        case 1:
            SegTree::tp_v(1, b, c, 1);
            break;
        case 2:
            SegTree::rev(1, b, c);
            break;
        case 3:
            printf("%d\n", SegTree::tot(1, b, c));
            break;
        //case 4: 致洛咕:Never Mind the Scandal and Liber
        default:
            printf("%d\n", SegTree::lx(1, b, c).maxc[1]);
            break;
        };
    }
}

说到推平,怎么能不说说珂朵莉呢?顺便借这道题练了一下珂朵莉。

#include <cstdio>
#include <set>

struct Node
{
    int l, r;
    mutable int t;//记得加mutable,因为set的迭代器是read-only的
    inline bool operator<(const Node &b) const { return l < b.l; }
    Node(int l = 0, int r = 0, int t = 0) : l(l), r(r), t(t) {}
};
typedef std::set<Node> set;
typedef set::iterator It;

int n, m;
set s;

inline void build(void)
{
    Node waiting;
    for (int i = 0; i < n; ++i)
    {
        scanf("%d", &waiting.t);
        waiting.l = waiting.r = i;
        s.insert(waiting);
    }
    waiting.l = waiting.r = n;
    s.insert(waiting);
}

It split(int p)//return[p, r]
{
    It nd = s.lower_bound(Node(p));
    if (nd != s.end() && nd->l == p)
        return nd;
    --nd;
    int left = nd->l, right = nd->r, type = nd->t;
    s.erase(nd);
    s.insert(Node(left, p - 1, type));
    return s.insert(Node(p, right, type)).first;
}

void assign(int l, int r, int v)
{
    It second = split(r + 1), first = split(l);
    //先split右边
    //如果先split左边,spilt右边可能会导致(这个函数的)first失效
    s.erase(first, second);
    s.insert(Node(l, r, v));
}

void reverse(int l, int r)
{
    It second = split(r + 1), first = split(l);
    while (first != second)
    {
        first->t ^= 1;
        ++first;
    }
}

int sum(int l, int r)
{
    It second = split(r + 1), first = split(l);
    int ret = 0;
    while (first != second)
    {
        if (first->t)
            ret += first->r - first->l + 1;
        ++first;
    }
    return ret;
}

int lx(int l, int r)
{
    It second = split(r + 1), first = split(l);
    int ret = 0, tmp = 0;
    while (first != second)
    {
        if (first->t)
            tmp += first->r - first->l + 1;
        else
            ret = std::max(ret, tmp), tmp = 0;
        ++first;
    }
    return std::max(ret, tmp);
}

int main(void)
{
    scanf("%d %d", &n, &m);
    build();
    while (m--)
    {
        int a, b, c;
        scanf("%d %d %d", &a, &b, &c);
        switch (a)
        {
        case 0:
            assign(b, c, 0);
            break;
        case 1:
            assign(b, c, 1);
            break;
        case 2:
            reverse(b, c);
            break;
        case 3:
            printf("%d\n", sum(b, c));
            break;
        //case 4:
        default:
            printf("%d\n", lx(b, c));
            break;
        }
    }
}

交上去T成**,自闭,然后XY大佬过来嘲讽我了一波然后发现数据改了就很尴尬

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注