前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >洛谷P4344 [SHOI2015]脑洞治疗仪(ODT)

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

作者头像
attack
发布2019-03-04 10:17:03
3360
发布2019-03-04 10:17:03
举报
文章被收录于专栏:数据结构与算法

题意

题目链接

Sol

ODT板子题。

操作1直接拆区间就行。

代码语言:javascript
复制
#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;
}
本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2019-02-09 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题意
  • Sol
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档