记录编号	274039	评测结果	AAAAAAAAAA
题目名称	[HAOI 2013]软件安装	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	0.182 s
提交时间	2016-06-26 12:07:31	内存使用	4.27 MiB

#include <vector>
#include <list>
#include <queue>
#include <algorithm>
#include <functional>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <cmath>
using namespace std;
#define MAXN (50005)

class segtree
{
private:
	struct node
	{
		int max;
		int lmax, rmax;  
		int lR, rL;   //指的是节点向左/右延伸的l,r
		int lazy;  //当前标记 -1表示无标记，1空闲，0被占用
		node()
		{
			lazy = -1;
		}
		void set(int f, int t, int flag)
		{
			if(flag)
			{
				lmax = rmax = max = t-f+1;
				lR = t;
				rL = f;
			}else
			{
				lmax = rmax = max = 0;
				lR = f-1;
				rL = t+1;
			}
		}
	}ns[MAXN << 2];
	int start, end;
	#define left(x) (x<<1)
	#define right(x) ((x<<1)|1)
	#define mid(x, y) ((x+y)>>1)
	#define ls left(c), f, mid(f, t)
	#define rs right(c), mid(f,t)+1, t
	void build_(int c, int f, int t)
	{
		ns[c].set(f, t, true);
		if(f != t)
		{
			build_(ls);
			build_(rs);
		}
	}
	void pushdown(int c, int f, int t)
	{
		ns[left(c)].set(f, mid(f,t), ns[c].lazy);
		ns[right(c)].set(mid(f,t)+1, t, ns[c].lazy);
		ns[left(c)].lazy = ns[right(c)].lazy = ns[c].lazy; 
		ns[c].lazy = -1;
	}
public:
	segtree(int f, int t)
	{
		start = f;
		end = t;
	}
	void build()
	{
		build_(1, start, end);
	}
	int ask(int c, int f, int t, int len)
	{
		if(f == t)return f;
		if(ns[c].lazy != -1)pushdown(c, f, t);
		if(ns[left(c)].max >= len)return ask(ls, len); //应题目要求，先查左边
		if(ns[left(c)].rmax+ns[right(c)].lmax >= len)return ns[left(c)].rL;
		return ask(rs, len);
	}
	void set(int c, int f, int t, int sf, int st, int flag)
	{
		if(sf <= f && st >= t) //设置的区间完全包含当前节点
		{
			ns[c].set(f, t, flag);
			ns[c].lazy = flag;
		}else
		{
			if(sf > t || st < f)return;
			if(ns[c].lazy != -1)pushdown(c, f, t);
			set(ls, sf, st, flag);
			set(rs, sf, st, flag);
			//从左，右，跨越中点中选出最大的....
			ns[c].max = max(ns[left(c)].max, max(ns[right(c)].max, ns[left(c)].rmax+ns[right(c)].lmax));
			
			//pushup，更新当前节点信息
			if(ns[left(c)].lmax == mid(f, t)-f+1)
			{
				ns[c].lmax = ns[left(c)].lmax + ns[right(c)].lmax;
				ns[c].lR = ns[right(c)].lR;
			}else
			{
				ns[c].lmax = ns[left(c)].lmax;
				ns[c].lR = ns[left(c)].lR;
			}
			if(ns[right(c)].rmax == t-(mid(f,t)))
			{
				ns[c].rmax = ns[left(c)].rmax + ns[right(c)].rmax;
				ns[c].rL = ns[left(c)].rL;
			}else
			{
				ns[c].rmax = ns[right(c)].rmax;
				ns[c].rL = ns[right(c)].rL;
			}
		}
	}
	int maxf()
	{
		return ns[1].max;
	}
};

int main()
{
	freopen("haoi13t4.in", "r", stdin);
	freopen("haoi13t4.out", "w", stdout);
	int n, m;
	scanf("%d %d", &n, &m);
	segtree s(1, n);
	s.build();
	while(m--)
	{
		int op,f,t,len;
		scanf("%d", &op);
		if(op == 1)
		{
			scanf("%d", &len);
			if(s.maxf() >= len)
			{
				printf("%d\n", f = s.ask(1, 1, n, len));
				s.set(1, 1, n, f, f + len-1, 0);
			}else
				puts("0");
		}else
		{
			scanf("%d %d", &f, &t);
			s.set(1, 1, n, f, f+t-1, 1);
		}
	}
	return 0;
}