# 11122: 【原1122】二哥开房间

### 题目描述

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

## 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;

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() {
create_tree(1, 1, n);
while (m--) {
if (op == 1) {
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 {