洛谷P4344 [SHOI2015]脑洞治疗仪(ODT)

题意

题目链接

sol

odt板子题。

操作1直接拆区间就行。

#include<bits/stdc++.h>
#define fi first
#define se second 
const int maxn = 2e5 + 10;
using namespace std;
inline int read() {
    char c = getchar(); int x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int n, m;
#define sit set<node>::iterator 
struct node {
    int l, r;
    mutable int v;
    bool operator < (const node &rhs) const {
        return l < rhs.l;
    }
};
set<node> s;
sit split(int p) {
    sit pos = s.lower_bound({p, 0, 0});
    if(pos->l == p) return pos;
    pos--;
    int l = pos->l, r = pos->r, v = pos->v;
    s.erase(pos);
    s.insert({l, p - 1, v});
    return s.insert({p, r, v}).fi;
}
void mem(int l, int r) {
    sit ed = split(r + 1), bg = split(l);
    s.erase(bg, ed);
    s.insert({l, r, 0});
}
void fix(int l0, int r0, int l, int r) {
    int num = 0;
    sit ed = split(r + 1), bg = split(l);
    for(sit i = bg; i != ed; i++) if(i->v == 1) num += i->r - i->l + 1;
    s.erase(bg, ed);
    s.insert({l, r, 0});
    ed = split(r0 + 1), bg = split(l0);
    sit gg; int rr = -1;
    for(sit i = bg; i != ed; i++) {
        if(i -> v == 1) continue;
        if(num <= 0) return ;
        int len = i->r - i->l + 1;
        if(len <= num) {i -> v = 1, num -= len; gg = i; rr = i->r; continue;}
        int l = i->l, r = i->r;
        s.erase(i);
        s.insert({l, l + num - 1, 1});
        s.insert({l + num, r, 0});
        return ;
    }
    if(rr > l0) {//ò»¸ö²¢ã»óðê²ã´âñóãµäó廯 
        gg++;
        s.erase(bg, gg);
        s.insert({l0, rr, 1});  
    }
}
int query(int l, int r) {
    sit ed = split(r + 1), bg = split(l);
    int pre = 0, ans = 0;
    for(sit i = bg; i != ed; i++) {
        if(i->v == 0) ans = max(ans, i->r - i->l + 1 + pre), pre += i->r - i->l + 1;
        else pre = 0;
    }
    return ans;
}
int main() {
    //freopen("a.in", "r", stdin);
    n = read(); m = read();
    for(int i = 1; i <= n; i++) s.insert({i, i, 1});
    s.insert({n + 1, n + 1, 1});
    for(int i = 1; i <= m; i++) {
        int opt = read(), l = read(), r = read();
        if(opt == 0) mem(l, r);
        else if(opt == 1) {
            int l1 = read(), r1 = read();
            fix(l1, r1, l, r);
        } else printf("%d\n", query(l, r));
    }
    return 0;
}