P2894 线段树
纯正线段树
分析问题：
对于这一个问题，这个线段树，所维护的域与简单的区间加法就大不相同了，区间加法参见P3372，最简单的线段树的模板所要维护的域实际上只有一个，但是这个题目的维护就会不一样些;
我们所要维护的域实际上有3个，分别是lans（从维护的区间的左边的第一个数开始的最长的连续空闲房间的数量）rans（从维护的区间的右边的第一个数开始的最长的连续空闲房间的数量）和ans（总的维护区间的空闲房间的数量）
现在善于思考的小盆友就应该有疑问了，为什么是这三个域呢？？？
其实如果我们开始主观判断的话，想到的实际上应该是只需要维护ans这一个域，但我们在建树的时候就会发现，如果只去维护了ans这一个域的话，就没有办法完成push_up的工作，所以说，利用lans和rans就可以轻松的把数据”挂“上去喽。就像这样：
inline int max(int a,int b,int c)
{
int zhuan = a > b ? a : b;
return zhuan > c ? zhuan : c;
}
inline int ls(int fa)
{return fa<<1;}
inline int rs(int fa)
{return fa<<1|1;}
inline void push_up(int fa)
{
t[fa].ans = max(t[ls(fa)].rans + t[rs(fa)].lans , t[ls(fa)].ans , t[rs(fa)].ans);
int mid = t[fa].l + t[fa].r >>1;
if(t[ls(fa)].ans == mid - t[fa].l + 1)
t[fa].lans = t[ls(fa)].ans + t[rs(fa)].lans;
else
t[fa].lans = t[ls(fa)].lans;
if(t[rs(fa)].ans == t[fa].r - mid)
t[fa].rans = t[rs(fa)].ans + t[ls(fa)].rans;
else
t[fa].rans = t[rs(fa)].rans;
}哦对了，我的树上维护了这样的几个域：
class segment
{
public:
int debt;
int lans,rans;
int ans;
int l,r;
}t[maxn * 4+10];顾名思义，debt就是债务的意思，其实就是我们平常使用的懒惰标记，在这里我把它比喻成债务，就是还没有还给下面的节点的意思，是不是很通俗易懂呢，之后l和r就是所维护的区间的节点，lans，rans和ans就是我上面所说。
解释完这个，我们就要开始建树了，就像这样：
inline void build(int fa,int l,int r)
{
t[fa].l = l; t[fa].r = r;
if(l == r)
{
t[fa].ans = t[fa].lans = t[fa].rans = 1;
t[fa].debt = -1;
return;
}
int mid = l + r >> 1;
build(ls(fa),l,mid); build(rs(fa),mid+1,r);
push_up(fa);
}之后是区间修改：
void add(int fa,int x, int y, int val)
{
if (x <= t[fa].l and t[fa].r <= y)
{
if(val)
t[fa].ans = t[fa].lans = t[fa].rans = 0;
else
t[fa].ans = t[fa].lans = t[fa].rans = t[fa].r - t[fa].l + 1;
t[fa].debt = val;
return ;
}
push_down(fa);
int mid = (t[fa].l + t[fa].r) >> 1;
if (x <= mid) add(ls(fa),x,y,val);
if (y > mid) add(rs(fa),x, y, val);
push_up(fa);
}可不能忘了懒惰标记：
inline void push_down(int fa)
{
if(!t[fa].debt)
{
t[ls(fa)].debt = t[rs(fa)].debt = 0;
int mid = (t[fa].l + t[fa].r) >> 1;
t[ls(fa)].ans = t[ls(fa)].lans = t[ls(fa)].rans = mid - t[fa].l + 1;
t[rs(fa)].ans = t[rs(fa)].lans = t[rs(fa)].rans = t[fa].r - mid;
}
else if (t[fa].debt == 1)
{
t[ls(fa)].debt = t[rs(fa)].debt = 1;
t[ls(fa)].ans = t[ls(fa)].lans = t[ls(fa)].rans = 0;
t[rs(fa)].ans = t[rs(fa)].lans = t[rs(fa)].rans = 0;
}
t[fa].debt = -1;
}区间查找：
inline int query(int fa,int k)
{
push_down(fa);
if (t[fa].l == t[fa].r) return t[fa].l;
int mid = (t[fa].l + t[fa].r) >> 1;
if (t[ls(fa)].ans >= k)
return query(ls(fa),k);
if (t[ls(fa)].rans + t[rs(fa)].lans >= k)
return (mid - t[ls(fa)].rans + 1);
else
return query(rs(fa), k);
}这是不是就要结束了呢？
当然不是
最最最重要的还有判断是0的条件
我们知道，最上面的根节点所维护的ans就是全hotel的连续空闲的最长的区间长度，所以每次在询问之前，我们都要先看一看t[1].ans是不是大于所要查找的长度，如果要查找的区间长度比较长一点，那么就直接输出0就好了
我知道你们等了半天的代码了
那就满足你们：
#include<bits/stdc++.h>
using namespace std;
inline int get()
{
int s = 0,f = 1;
register char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-') f = -1;
ch = getchar();
}
while(isdigit(ch))
{
s = s *10 + ch - '0';
ch = getchar();
}
return s * f;
}
inline void openfile()
{freopen("t.txt","r",stdin);}
namespace xin
{
const int maxn = 5e4+10;
int n,m;
class segment
{
public:
int debt;
int lans,rans;
int ans;
int l,r;
}t[maxn * 4+10];
inline int max(int a,int b,int c)
{
int zhuan = a > b ? a : b;
return zhuan > c ? zhuan : c;
}
inline int ls(int fa)
{return fa<<1;}
inline int rs(int fa)
{return fa<<1|1;}
inline void push_up(int fa)
{
t[fa].ans = max(t[ls(fa)].rans + t[rs(fa)].lans , t[ls(fa)].ans , t[rs(fa)].ans);
int mid = t[fa].l + t[fa].r >>1;
if(t[ls(fa)].ans == mid - t[fa].l + 1)
t[fa].lans = t[ls(fa)].ans + t[rs(fa)].lans;
else
t[fa].lans = t[ls(fa)].lans;
if(t[rs(fa)].ans == t[fa].r - mid)
t[fa].rans = t[rs(fa)].ans + t[ls(fa)].rans;
else
t[fa].rans = t[rs(fa)].rans;
}
inline void push_down(int fa)
{
if(!t[fa].debt)
{
t[ls(fa)].debt = t[rs(fa)].debt = 0;
int mid = (t[fa].l + t[fa].r) >> 1;
t[ls(fa)].ans = t[ls(fa)].lans = t[ls(fa)].rans = mid - t[fa].l + 1;
t[rs(fa)].ans = t[rs(fa)].lans = t[rs(fa)].rans = t[fa].r - mid;
}
else if (t[fa].debt == 1)
{
t[ls(fa)].debt = t[rs(fa)].debt = 1;
t[ls(fa)].ans = t[ls(fa)].lans = t[ls(fa)].rans = 0;
t[rs(fa)].ans = t[rs(fa)].lans = t[rs(fa)].rans = 0;
}
t[fa].debt = -1;
}
inline void build(int fa,int l,int r)
{
t[fa].l = l; t[fa].r = r;
if(l == r)
{
t[fa].ans = t[fa].lans = t[fa].rans = 1;
t[fa].debt = -1;
return;
}
int mid = l + r >> 1;
build(ls(fa),l,mid); build(rs(fa),mid+1,r);
push_up(fa);
}
void add(int fa,int x, int y, int val)
{
if (x <= t[fa].l and t[fa].r <= y)
{
if(val)
t[fa].ans = t[fa].lans = t[fa].rans = 0;
else
t[fa].ans = t[fa].lans = t[fa].rans = t[fa].r - t[fa].l + 1;
t[fa].debt = val;
return ;
}
push_down(fa);
int mid = (t[fa].l + t[fa].r) >> 1;
if (x <= mid) add(ls(fa),x,y,val);
if (y > mid) add(rs(fa),x, y, val);
push_up(fa);
}
inline int query(int fa,int k)
{
push_down(fa);
if (t[fa].l == t[fa].r) return t[fa].l;
int mid = (t[fa].l + t[fa].r) >> 1;
if (t[ls(fa)].ans >= k)
return query(ls(fa),k);
if (t[ls(fa)].rans + t[rs(fa)].lans >= k)
return (mid - t[ls(fa)].rans + 1);
else
return query(rs(fa), k);
}
inline short main()
{
// openfile();
n = get(); m = get();
build(1,1,n);
while(m--)
{
register int op = get();
if(op == 1)
{
register int d = get();
if(t[1].ans >= d)
{
int zhuan = query(1,d);
printf("%d\n",zhuan);
add(1,zhuan,zhuan+d-1,1);
}
else
printf("0\n");
}
else
{
register int x = get(),d = get();
add(1,x,x+d-1,0);
}
}
return 0;
}
}
signed main() {return xin::main();}