POJ 3667 Hotel

题目链接：​​传送门​​虽然是重题但还是要发一篇博客

维护最长01串
oh我之前写的好良心
再放上来

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <complex>
#include <algorithm>
#include <climits>
#include <queue>
#include <map>
#include <vector>
#include <iomanip>
#define
#define
#define

using namespace std;
struct node {
    int l, r, w, lt, rt, t, f;
}tree[A];
int n, m, x, y, typ, ans;
void up(int k) {
    tree[k].t = max(tree[k << 1].rt + tree[k << 1 | 1].lt, max(tree[k << 1].t, tree[k << 1 | 1].t));
    //当前区间最长的一段可以是左儿子的右边开始最长区间长度加上左儿子的左边开始最长区间长度
    //还可以是左儿子的区间最长长度或右儿子的区间最长长度
    if (tree[k << 1].lt == tree[k << 1].w) tree[k].lt = tree[k << 1].lt + tree[k << 1 | 1].lt;
    //可以是左儿子的区间长度加上右儿子的左边开始最长区间长度
    else tree[k].lt = tree[k << 1].lt;
    if (tree[k << 1 | 1].rt == tree[k << 1 | 1].w) tree[k].rt = tree[k << 1].rt + tree[k << 1 | 1].rt;
    //可以是右儿子的区间长度加上左儿子的右边开始最长区间长度
    //这两块可以并到一起
    else tree[k].rt = tree[k << 1 | 1].rt;
}
void build(int k, int l, int r) {
    tree[k].l = l; tree[k].r = r; tree[k].w = r - l + 1; //w维护这段区间的长度
    if (l == r) {
        tree[k].lt = tree[k].rt = tree[k].t = 1; //初值都为1
        return;
    }
    int m = (l + r) >> 1;
    build(k << 1, l, m);
    build(k << 1 | 1, m + 1, r);
    up(k);
}
void down(int k) { //标记下传
    if (tree[k].f == 1) {
        tree[k << 1].lt = tree[k << 1].rt = tree[k << 1].t = 0;
        tree[k << 1].f = 1;
        tree[k << 1 | 1].lt = tree[k << 1 | 1].rt = tree[k << 1 | 1].t = 0;
        tree[k << 1 | 1].f = 1;
        tree[k].f = 0;
        //这是删除点，也就是退房
    }
    if (tree[k].f == 2) {
        tree[k << 1].lt = tree[k << 1].rt = tree[k << 1].t = tree[k << 1].w;
        tree[k << 1].f = 2;
        tree[k << 1 | 1].lt = tree[k << 1 | 1].rt = tree[k << 1 | 1].t = tree[k << 1 | 1].w;
        tree[k << 1 | 1].f = 2;
        tree[k].f = 0;
        //开房
    }
}
void change(int k, int l, int r, int typ) {
    if (l <= tree[k].l and r >= tree[k].r) {
        if (typ == 1) {
            tree[k].lt = tree[k].rt = tree[k].t = 0;
            tree[k].f = 1;
            //退房
        }
        else tree[k].lt = tree[k].rt = tree[k].t = tree[k].w, tree[k].f = 2;//开房
        return;
    }
    down(k);
    int m = (tree[k].l + tree[k].r) >> 1;
    if (l <= m) change(k << 1, l, r, typ);
    if (r > m) change(k << 1 | 1, l, r, typ);
    up(k);
}
int ask(int k) {
    //可能大多数人会觉得这里有判断是否在区间内的操作
    //但这里的操作区间是1-n，所以就没有必要判断了
    down(k);
    //直接下放标记
    if (tree[k << 1].t >= x) return ask(k << 1); //向左儿子找
    else if (tree[k << 1].rt + tree[k << 1 | 1].lt >= x) return tree[k << 1].r - tree[k << 1].rt + 1;
    //左右两端区间并起来能达到题目要求
    //也就是明确了区间端点
    //到这里就可以返回答案了
    //就按题目要求返回左端点
    else if (tree[k << 1 | 1].t >= x) return ask(k << 1 | 1); //向右儿子找
    up(k);
}

int main(int argc, char const *argv[]) {
    scanf("%d%d", &n, &m); build(1, 1, n);
    while (m--) {
        scanf("%d", &typ);
        if (typ == 1) {
            scanf("%d", &x);
            if (tree[1].t < x) puts("0");
            else {
                ans = ask(1);
                printf("%d\n", ans);
                change(1, ans, ans + x - 1, 1); //要求查完之后把房开开
            }
        }
        else {
            scanf("%d%d", &x, &y);
            change(1, x, x + y - 1, 2); //退房
        }
    }
    return 0;
}