SHOI2015 脑洞治疗仪

#include <cstdio>

#include <algorithm>

#define LOG(FMT...) fprintf(stderr, FMT)

using namespace std;

struct data {
    int l, r;
    int sum, lmex, rmex, mex;

    data() {}

    data(int l, int r, int x) : l(l), r(r), sum(x), lmex(x), rmex(x), mex(x) {}

    data operator+(const data& x) const;

    bool full() const;
};

struct node {
    data d;
    int lazy;
    node *ls, *rs;

    int bound(int l, int& x);
    data query(int l, int r);
    void change(int l, int r, int x);

    void push_down();
    void update();
    data get_d() const;
};

const int N = 200010;

int n, m;
node* root;

node* build(int l, int r);

int main() {
    int op, l, r, l2, r2, x, y;
    scanf("%d%d", &n, &m);
    root = build(1, n);
    while (m--) {
        scanf("%d%d%d", &op, &l, &r);
        switch (op) {
        case 0:
            root->change(l, r, 1);
            break;
        case 1:
            scanf("%d%d", &l2, &r2);
            x = r - l + 1 - root->query(l, r).sum;
            root->change(l, r, 1);
            y = min(root->bound(l2, x), r2);
            if (y >= l2)
                root->change(l2, y, 0);
            break;
        case 2:
            printf("%d\n", root->query(l, r).mex);
            break;
        }
    }
    return 0;
}

node* build(int l, int r) {
    static node pool[N << 1];
    static int cnt;
    node* p = pool + ++cnt;
    p->d = data(l, r, 0);
    if (l == r)
        return p;
    int mid = (l + r) >> 1;
    p->ls = build(l, mid);
    p->rs = build(mid + 1, r);
    return p;
}

data node::query(int l, int r) {
    if (d.l == l && d.r == r)
        return get_d();
    push_down();
    if (r <= ls->d.r)
        return ls->query(l, r);
    if (l >= rs->d.l)
        return rs->query(l, r);
    return ls->query(l, ls->d.r) + rs->query(rs->d.l, r);
}

void node::change(int l, int r, int x) {
    if (d.l == l && d.r == r) {
        lazy = x;
        return;
    }
    push_down();
    if (r <= ls->d.r)
        ls->change(l, r, x);
    else if (l >= rs->d.l)
        rs->change(l, r, x);
    else {
        ls->change(l, ls->d.r, x);
        rs->change(rs->d.l, r, x);
    }
    update();
}

int node::bound(int l, int& x) {
    if (!x)
        return l - 1;
    push_down();
    if (d.l == l) {
        if (d.sum <= x) {
            x -= d.sum;
            return d.r;
        }
        int ret = ls->bound(l, x);
        if (!x)
            return ret;
        return rs->bound(rs->d.l, x);
    }
    if (ls->d.r >= l) {
        int ret = ls->bound(l, x);
        if (!x)
            return ret;
        return rs->bound(rs->d.l, x);
    }
    return rs->bound(l, x);
}

void node::push_down() {
    switch (lazy) {
    case 0:
        d.sum = d.lmex = d.rmex = d.mex = 0;
        break;
    case 1:
        d.sum = d.lmex = d.rmex = d.mex = d.r - d.l + 1;
        break;
    default:
        return;
    }
    if (ls)
        ls->lazy = rs->lazy = lazy;
    lazy = 2;
}

void node::update()
{ d = ls->get_d() + rs->get_d(); }

data node::get_d() const {
    if (lazy == 0)
        return data(d.l, d.r, 0);
    if (lazy == 1)
        return data(d.l, d.r, d.r - d.l + 1);
    return d;
}

data data::operator+(const data& x) const {
    data ret;
    ret.l = l;
    ret.r = x.r;
    ret.sum = sum + x.sum;
    if (full())
        ret.lmex = sum + x.lmex;
    else
        ret.lmex = lmex;
    if (x.full())
        ret.rmex = rmex + x.sum;
    else
        ret.rmex = x.rmex;
    ret.mex = max(max(mex, x.mex), rmex + x.lmex);
    return ret;
}

bool data::full() const
{ return sum == r - l + 1; }