Skip to content

11122: 【原1122】二哥开房间

题目

题目描述

author: Huihuang Zheng 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1122

Background

也许是房间开多了,二哥最近一直喊虚。这天二哥又和...去旅馆开房间,却遇上了虚逼P和小Z(别问虚逼P和小Z为什么会在旅馆= =)

二哥希望不要把他开房间的事说出去,所以小Z是不会告诉你们的!但虚逼P对二哥说:“我出道很简单的题给你做,做不出来你得承认你很虚。”

Description

这个旅店有房间号为1...N(1 <= N <= 50000)个房间。 每当有人来开房时,他们总希望开房间号相邻的房间。他们给出希望开的房间数量D(1 <= D <= N),旅店要是有这样的号码连续的空房,就给客人房间号最小的D个房间,并告诉客人这D个房间中房号最小的那个房号,之后,这D间房便被入住了。否则,旅店输出0,这些客人一个都不会入住。

当客人退房时,会给出X和Y两个数,表示退X, X+1...X + Y - 1这Y个房间(1 <= X <= N - Y + 1)。注意:退的房间可以是没人开的,退房的这Y个人未必是同时来开房的那一批人。

Hints

虚逼P说这是道很简单的线段树题

Input Format

第一行,两个正整数N,M。 N 即共几个房间, M是接下来有M行输入 接下来M行,每行有两种可能输入: (1)两个整数1 和 D,代表现在有客人来开房间号连续的D间房 (2)三个整数2,X,Y 代表上面说的从X房开始的Y间房被退掉

Output Format

每次有客人开房,输出一行整数 若旅店有连续房间,给出D间房中房号最小的号码。否则输出0。

Sample Input

10 6
1 3
1 3
1 3
1 3
2 5 5
1 6

Sample Output

1
4
7
0
5

FineArtz's solution

/* 二哥开房间 */
#include <iostream>
using namespace std;

const int MAXN = 50000;

struct Node{
    int l = 0, r = 0;
    int lsum = 0, rsum = 0, sum = 0;
    int lazy = 0; //0: None, 1: occupied, 2: recycled
};

Node a[MAXN * 4 + 5];
int n, m;

void pushUp(int x){
    a[x].lsum = a[x << 1].lsum;
    a[x].rsum = a[x << 1 | 1].rsum;
    int mid = (a[x].l + a[x].r) >> 1;
    if (a[x << 1].lsum == mid - a[x].l + 1)
        a[x].lsum += a[x << 1 | 1].lsum;
    if (a[x << 1 | 1].rsum == a[x].r - mid)
        a[x].rsum += a[x << 1].rsum;
    a[x].sum = max(a[x << 1].rsum + a[x << 1 | 1].lsum, max(a[x << 1].sum, a[x << 1 | 1].sum));
}

void pushDown(int x){
    if (a[x].lazy == 0)
        return;
    int mid = (a[x].l + a[x].r) >> 1;
    a[x << 1].lazy = a[x << 1 | 1].lazy = a[x].lazy;
    if (a[x].lazy == 1){
        a[x << 1].lsum = a[x << 1].rsum = a[x << 1].sum = 0;
        a[x << 1 | 1].lsum = a[x << 1 | 1].rsum = a[x << 1 | 1].sum = 0;
    }
    else{
        a[x << 1].lsum = a[x << 1].rsum = a[x << 1].sum = mid - a[x].l + 1;
        a[x << 1 | 1].lsum = a[x << 1 | 1].rsum = a[x << 1 | 1].sum = a[x].r - mid;
    }
    a[x].lazy = 0;
}

void buildTree(int x, int l, int r){
    a[x].l = l;
    a[x].r = r;
    if (l == r){
        a[x].lsum = a[x].rsum = a[x].sum = 1;
        return;
    }
    int mid = (l + r) >> 1;
    buildTree(x << 1, l, mid);
    buildTree(x << 1 | 1, mid + 1, r);
    pushUp(x);
}

void update(int x, int l, int r, int lazy){
    if (a[x].l >= l && a[x].r <= r){
        a[x].lazy = lazy;
        if (lazy == 1)
            a[x].lsum = a[x].rsum = a[x].sum = 0;
        else
            a[x].lsum = a[x].rsum = a[x].sum = a[x].r - a[x].l + 1;
        return;
    }
    pushDown(x);
    int mid = (a[x].l + a[x].r) >> 1;
    if (l <= mid)
        update(x << 1, l, r, lazy);
    if (r > mid)
        update(x << 1 | 1, l, r, lazy);
    pushUp(x);
}

int query(int x, int len){
    if (a[x].l == a[x].r)
        return a[x].l;
    pushDown(x);
    int mid = (a[x].l + a[x].r) >> 1;
    if (a[x << 1].sum >= len)
        return query(x << 1, len);
    else if (a[x << 1].rsum + a[x << 1 | 1].lsum >= len)
        return mid - a[x << 1].rsum + 1;
    else
        return query(x << 1 | 1, len);
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    buildTree(1, 1, n);
    while (m--){
        int op, x, y;
        cin >> op;
        switch (op){
        case 1:
            cin >> x;
            if (x > a[1].sum)
                cout << 0 << '\n';
            else{
                y = query(1, x);
                cout << y << '\n';
                update(1, y, y + x - 1, 1);
            }
            break;
        case 2:
            cin >> x >> y;
            update(1, x, x + y - 1, 2);
            break;
        }
    }
    return 0;
}

q4x3's solution

/**
 * 线段树
 * 最难写的是query
 * TAT
 * 下 次 一 定
 **/
#include <iostream>
#include <stdio.h>

using namespace std;

const int MAXN = 5e4 + 233;
int lmax[MAXN * 4], rmax[MAXN * 4], totmax[MAXN * 4], lazy[MAXN * 4]; // 退房lazy为-1入住为1
int N, M;

void build(int rt, int l, int r) {
    if(l == r) {
        lmax[rt] = 1;
        rmax[rt] = 1;
        totmax[rt] = 1;
        return;
    }
    int mid = (l + r) >> 1;
    build(rt << 1, l, mid);
    build(rt << 1 | 1, mid + 1, r);
    lmax[rt] = lmax[rt << 1] + lmax[rt << 1 | 1];
    rmax[rt] = rmax[rt << 1] + rmax[rt << 1 | 1];
    totmax[rt] = totmax[rt << 1] + totmax[rt << 1 | 1];
}

void update(int rt, int l, int r, int w) {
    if(w == -1) {
        lmax[rt] = rmax[rt] = totmax[rt] = r - l + 1;
        lazy[rt] = -1;
    } else if(w == 1) {
        lmax[rt] = rmax[rt] = totmax[rt] = 0;
        lazy[rt] = 1;
    }
}

void pushdown(int rt, int l, int r) {
    int mid = (l + r) >> 1;
    update(rt << 1, l, mid, lazy[rt]);
    update(rt << 1 | 1, mid + 1, r, lazy[rt]);
    lazy[rt] = 0;
}

void modify(int rt, int l, int r, int s, int t, int w) {
    if(s <= l && t >= r) {
        update(rt, l, r, w);
        return;
    }
    pushdown(rt, l, r);
    int mid = (l + r) >> 1;
    if(s <= mid) modify(rt << 1, l, mid, s, t, w);
    if(t > mid) modify(rt << 1 | 1, mid + 1, r, s, t, w);
    if(lmax[rt << 1] < mid - l + 1) lmax[rt] = lmax[rt << 1];
    else lmax[rt] = mid - l + 1 + lmax[rt << 1 | 1];
    if(rmax[rt << 1 | 1] < r - mid) rmax[rt] = rmax[rt << 1 | 1];
    else rmax[rt] = r - mid + rmax[rt << 1];
    totmax[rt] = rmax[rt << 1] + lmax[rt << 1 | 1];
    totmax[rt] = (totmax[rt] > totmax[rt << 1]) ? totmax[rt] : totmax[rt << 1];
    totmax[rt] = (totmax[rt] > totmax[rt << 1 | 1]) ? totmax[rt] : totmax[rt << 1 | 1];
}

int query(int rt, int l, int r, int len) {
    if(l == r) return l;
    int mid = (l + r) >> 1;
    pushdown(rt, l, r);
    if(totmax[rt << 1] >= len) return query(rt << 1, l, mid, len);
    else if(rmax[rt << 1] + lmax[rt << 1 | 1] >= len) return mid - rmax[rt << 1] + 1;
    else return query(rt << 1 | 1, mid + 1, r, len);
}

int main() {
    scanf("%d%d", &N, &M);
    build(1, 1, N);
    for(int i = 0;i < M;++ i) {
        int tmp1, tmp2, tmp3;
        scanf("%d%d", &tmp1, &tmp2);
        if(tmp1 == 1) {
            if(tmp2 > totmax[1]) {
                printf("0\n");
                continue;
            }
            tmp3 = query(1, 1, N, tmp2);
            printf("%d\n", tmp3);
            modify(1, 1, N, tmp3, tmp3 + tmp2 - 1, 1);
        } else {
            scanf("%d", &tmp3);
            modify(1, 1, N, tmp2, tmp2 + tmp3 - 1, -1);
        }
    }
    return 0;
}

victrid's solution

#include <cstdio>
#include <iostream>
using namespace std;
// #define DEBUG

//最长的左部
//最长的右部
struct storage {
    int maxl;
    int maxr;
    int msum;
    int lazy;
};

storage seq[400005];

struct set {
    int l;
    int r;
    int current;
    storage& mx;
    set left() {
        return set{l, (l + r) >> 1, current << 1, seq[current << 1]};
    }
    set right() {
        return set{((l + r) >> 1) + 1, r, current << 1 | 1, seq[current << 1 | 1]};
    }
    bool isleaf() { return !(r - l); }
    int size() { return r - l + 1; }
};
// //DEBUG
// #ifdef DEBUG
// #include <queue>
// void display_a_segtree(set s) {
//     queue<set> q;
//     q.push(s);
//     q.push(set{0, 0, 0, seq[0]});
//     while (!q.empty()) {
//         set v  = q.front();
//         set vs = q.front();
//         q.pop();
//         if (v.l == 0) {
//             putchar('\n');
//             if (q.empty())
//                 return;
//             v = q.front();
//             q.pop();
//             if (v.l == 0)
//                 return;
//             else
//                 q.push(set{0, 0, 0, seq[0]});
//         }
//         if (v.isleaf()) {
//             printf("l %d %d %d %d %d\t", v.l, v.mx.maxl, v.mx.maxr, v.mx.msum, v.mx.lazy);
//         } else {
//             printf("%d %d %d %d %d %d\t", v.l, v.r, v.mx.maxl, v.mx.maxr, v.mx.msum, v.mx.lazy);
//             q.push(v.left());
//             q.push(v.right());
//         }
//     }
// }
// #endif
void update_up(set s) {
    s.mx.maxl = s.left().mx.maxl;
    if (s.left().mx.maxl == s.left().size())
        s.mx.maxl += s.right().mx.maxl;
    s.mx.maxr = s.right().mx.maxr;
    if (s.right().mx.maxr == s.right().size())
        s.mx.maxr += s.left().mx.maxr;
    //! here should be sum.
    s.mx.msum = max(s.left().mx.msum + s.right().mx.msum, max(s.right().mx.maxr, s.right().mx.maxl));
    return;
}
void buildtree(set s) {
    if (s.isleaf()) {
        s.mx.maxl = 1;
        s.mx.maxr = 1;
        s.mx.msum = 1;
        s.mx.lazy = 0;
        return;
    }
    buildtree(s.left());
    buildtree(s.right());
    update_up(s);
    return;
}
void markoc(set s) {
    s.mx.maxl = 0;
    s.mx.maxr = 0;
    s.mx.msum = 0;
    s.mx.lazy = 1;
}
void markcl(set s) {
    s.mx.maxl = s.size();
    s.mx.maxr = s.size();
    s.mx.msum = s.size();
    s.mx.lazy = 2;
}
void pushtags(set s) {
    if (s.mx.lazy == 1) {
        s.mx.lazy = 0;
        if (s.isleaf()) {
            return;
        }
        markoc(s.left());
        markoc(s.right());
    } else if (s.mx.lazy == 2) {
        s.mx.lazy = 0;
        if (s.isleaf()) {
            return;
        }
        markcl(s.left());
        markcl(s.right());
    }
}
//status 1 occupy 2 release
void update(int l, int r, int status, set s) {
    if (s.l >= l && s.r <= r) {
        if (status == 1)
            markoc(s);
        else
            markcl(s);
        return;
    }
    if (s.isleaf())
        return;
    if (s.mx.lazy) {
        pushtags(s);
    }
    int mid = (s.l + s.r) >> 1;
    if (l <= mid) {
        update(l, r, status, s.left());
    }
    if (r > mid) {
        update(l, r, status, s.right());
    }
    update_up(s);
    return;
}
int find(int size, set s) {
    if (s.mx.msum < size)
        return 0;
    if (s.isleaf())
        return 1;
    //...Wo Shi Han Han
    if (s.mx.lazy)
        pushtags(s);
    int ll = find(size, s.left());
    if (ll)
        return ll;
    if ((s.right().mx.maxl + s.left().mx.maxr) >= size) {
        return s.left().r - s.left().mx.maxr + 1;
    }
    int lr = find(size, s.right());
    if (lr)
        return lr;
    return 0;
}
void release(int start, int size, set s) {
    return update(start, start + size - 1, 2, s);
}
int main() {
    int N, M, op1, op2, op3;
    scanf("%d %d", &N, &M);
    buildtree(set{1, N, 1, seq[1]});
    while (M--) {
        scanf("%d", &op1);
        if (op1 == 1) {
            scanf("%d", &op2);
            int p = find(op2, set{1, N, 1, seq[1]});
            printf("%d\n", p);
            if (p) {
                update(p, p + op2 - 1, 1, set{1, N, 1, seq[1]});
            }
            //display_a_segtree(set{1, N, 1, seq[1]});
        } else {
            scanf("%d %d", &op2, &op3);
            release(op2, op3, set{1, N, 1, seq[1]});
            //display_a_segtree(set{1, N, 1, seq[1]});
        }
    }
    return 0;
}

yyong119's solution

#include <iostream>
#include <cstdio>
#define MAX_N 50010
using namespace std;

struct Node {
    int l_con, r_con, c_con;
} tree[MAX_N << 3];
int tag[MAX_N << 3];
int n, m;

inline int read() {
    char c = getchar(); int res = 0, flag = 1;
    while(c != '-' && (c < '0' || c > '9')) c = getchar();
    if (c == '-') {
        flag = -1, c = getchar();
    }
    while(c >= '0' && c <= '9')
        res = 10 * res + c - '0', c = getchar();
    return res * flag;
}

void create_tree(int x, int l, int r) {
    tree[x].l_con = r - l + 1;
    tree[x].r_con = tree[x].l_con;
    tree[x].c_con = tree[x].l_con;
    if (r == l) return;
    int mid = (l + r) >> 1;
    create_tree(x << 1, l, mid);
    create_tree(x << 1 | 1, mid + 1, r);

}

void push_down(int x, int l, int r) {
    if (tag[x] == 1) {// order
        tree[x].l_con = 0;
        tree[x].r_con = 0;
        tree[x].c_con = 0;
    }
    else {// free
        tree[x].l_con = r - l + 1;
        tree[x].r_con = tree[x].l_con;
        tree[x].c_con = tree[x].l_con;
    }
    tag[x << 1] = tag[x];
    tag[x << 1 | 1] = tag[x];
    tag[x] = 0;
}

void push_up(int x, int l, int r) {
    tree[x].l_con = tree[x << 1].l_con;
    tree[x].r_con = tree[x << 1 | 1].r_con;
    int mid = (l + r) >> 1;
    if (tree[x << 1].l_con == mid - l + 1)
        tree[x].l_con += tree[x << 1 | 1].l_con;
    if (tree[x << 1 | 1].r_con == r - mid)
        tree[x].r_con += tree[x << 1].r_con;
    tree[x].c_con = max(tree[x << 1].r_con + tree[x << 1 | 1].l_con, max(tree[x << 1].c_con, tree[x << 1 | 1].c_con));
}

int find_min(int x, int l, int r, int length) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (tag[x << 1]) push_down(x << 1, l, mid);
    if (tag[x << 1 | 1]) push_down(x << 1 | 1, mid + 1, r);

    if (tree[x << 1].c_con >= length)
        return find_min(x << 1, l, mid, length);
    else if (tree[x << 1].r_con + tree[x << 1 | 1].l_con >= length)
        return mid - tree[x << 1].r_con + 1;
    else return find_min(x << 1 | 1, mid + 1, r, length);
}

void order(int x, int l, int r, int tar_l, int tar_r) {
    if (l == tar_l && r == tar_r) {
        tree[x].l_con = 0;
        tree[x].r_con = 0;
        tree[x].c_con = 0;
        if (r != l) {
            tag[x << 1] = 1;
            tag[x << 1 | 1] = 1;
        }
        return;
    }
    int mid = (l + r) >> 1;
    if (tag[x << 1]) push_down(x << 1, l, mid);
    if (tag[x << 1 | 1]) push_down(x << 1 | 1, mid + 1, r);
    if (tar_r <= mid) order(x << 1, l, mid, tar_l, tar_r);
    else if (tar_l > mid) order(x << 1 | 1, mid + 1, r, tar_l, tar_r);
    else {
        order(x << 1, l, mid, tar_l, mid);
        order(x << 1 | 1, mid + 1, r, mid + 1, tar_r);
    }
    push_up(x, l, r);
}

void free(int x, int l, int r, int tar_l, int tar_r) {
    if (l == tar_l && r == tar_r) {
        tree[x].l_con = r - l + 1;
        tree[x].r_con = tree[x].l_con;
        tree[x].c_con = tree[x].l_con;
        if (r != l) {
            tag[x << 1] = -1;
            tag[x << 1 | 1] = -1;
        }
        return;
    }

    int mid = (l + r) >> 1;
    if (tag[x << 1]) push_down(x << 1, l, mid);
    if (tag[x << 1 | 1]) push_down(x << 1 | 1, mid + 1, r);
    if (tar_r <= mid) free(x << 1, l, mid, tar_l, tar_r);
    else if (tar_l > mid) free(x << 1 | 1, mid + 1, r, tar_l, tar_r);
    else {
        free(x << 1, l, mid, tar_l, mid);
        free(x << 1 | 1, mid + 1, r, mid + 1, tar_r);
    }
    push_up(x, l, r);
}

int main() {
    n = read(); m = read();
    create_tree(1, 1, n);
    while (m--) {
        int op; op = read();
        if (op == 1) {
            int L; L = read();
            if (L <= tree[1].c_con) {
                int x = find_min(1, 1, n, L);
                printf("%d\n", x);
                order(1, 1, n, x, x + L - 1);
            }
            else printf("0\n");
        }
        else {
            int x, y; x = read(); y = read();
            free(1, 1, n, x, x + y - 1);
        }
    }
    return 0;
}