题意:n个旅馆,m次操作,操作1查询长度为x的连续空置房间并入住(取最左区间),没有返回0,操作2退x-y之间的房
线段树维护lmax表示空房间可以向左延伸的最大距离,rmax表示空房间可以向右延伸的最大距离,sum表示空房间个数,lazy表示房间状态是入住或退房
#include <bits/stdc++.h>
using namespace std;
const int maxn = 100005;
struct node
{int lmax,rmax,sum,lazy,l,r,len;
}tree[maxn<<2];
void build(int root, int l, int r) {tree[root].l = l, tree[root].r = r, tree[root].len = r - l + 1;tree[root].lazy = 0; tree[root].sum = tree[root].lmax = tree[root].rmax = tree[root].len;if(l == r)return;int mid = (l + r) >> 1; build(root<<1, l, mid);build(root<<1|1, mid+1, r);
}
void push_up(int root) {if(tree[root<<1].len == tree[root<<1].sum) tree[root].lmax = tree[root<<1|1].lmax + tree[root<<1].len;else tree[root].lmax = tree[root<<1].lmax;if(tree[root<<1|1].len == tree[root<<1|1].sum) tree[root].rmax = tree[root<<1].rmax + tree[root<<1|1].len;else tree[root].rmax = tree[root<<1|1].rmax;tree[root].sum = max(tree[root<<1].sum, max (tree[root<<1|1].sum, tree[root<<1].rmax + tree[root<<1|1].lmax));
}
void push_down(int root) {if(!tree[root].lazy)return;if(tree[root].lazy == 1) {tree[root<<1].sum = tree[root<<1].lmax = tree[root<<1].rmax = 0;tree[root<<1|1].sum = tree[root<<1|1].lmax = tree[root<<1|1].rmax = 0;tree[root<<1].lazy = tree[root<<1|1].lazy = 1;}else {tree[root<<1].sum = tree[root<<1].lmax = tree[root<<1].rmax = tree[root<<1].len;tree[root<<1|1].sum = tree[root<<1|1].lmax = tree[root<<1|1].rmax = tree[root<<1|1].len;tree[root<<1].lazy = tree[root<<1|1].lazy = 2;}tree[root].lazy = 0;
}
void update(int root, int l, int r, int tag) {if(l <= tree[root].l && tree[root].r <= r) {if(tag == 1) tree[root].sum = tree[root].lmax = tree[root].rmax = 0;else tree[root].sum = tree[root].lmax = tree[root].rmax = tree[root].len;tree[root].lazy = tag;return;}push_down(root);int mid = (tree[root].l + tree[root].r) >> 1;if(mid >= l) update(root<<1, l, r, tag);if(r > mid) update(root<<1|1, l, r, tag);push_up(root);
}
int ask(int root, int length) {// cout<<tree[root].l << " " << tree[root].r<<" "<<tree[root<<1].rmax<<" "<<tree[root<<1|1].lmax<<endl;push_down(root);if(tree[root].len == 1)return tree[root].l;int mid = (tree[root].l + tree[root].r) >> 1;if(tree[root<<1].sum >= length) return ask(root<<1,length);if(tree[root<<1].rmax + tree[root<<1|1].lmax >= length) return mid - tree[root<<1].rmax + 1;if(tree[root<<1|1].sum >= length) return ask(root<<1|1, length);return 0;
}
int main() {std::ios::sync_with_stdio(false);std::cin.tie(nullptr);int n,m;cin>>n>>m;build(1,1,n);while(m--) {int opt;cin>>opt;if(opt == 1) {int x;cin>>x;int left = ask(1,x);cout<<left<<endl;if(left) {update(1,left,left+x-1,1);// for(int i=1;i<=2*n;i++)// cout<<tree[i].l <<" "<<tree[i].r<<" "<<tree[i].sum<<endl;}}else {int x,y;cin>>x>>y;update(1,x,x+y-1,2);}}return 0;
}