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