记录编号	385671	评测结果	AAAAAAAAAA
题目名称	[HAOI 2013]软件安装	最终得分	100
用户昵称	kZime	是否通过	通过
代码语言	C++	运行时间	0.184 s
提交时间	2017-03-22 09:09:37	内存使用	8.33 MiB

/*kZime*/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <stack>
#include <cstdlib>
#include <algorithm>
#define MAXN
using namespace std;
inline int read() {
	int k = 0, f = 1; char c = getchar();
	for(; !isdigit(c); c = getchar())if(c == '-') f = -1;
	for(; isdigit(c); c = getchar()) k = k * 10 + c - '0';
	return k * f;
}
/*-----------------------------------------------------------------------------*/

int n, m;

class segtree {
public:
	int l, r, lm, rm, m, mp, tag; //mp指的是最长区间的起始位置
	segtree() {
		tag = -1;
	}
	void in(int _l, int _r, int _ml, int _mr, int _m, int _mp, int _tag) {
		l = _l;
		r = _r;
		lm = _ml;
		rm = _mr;
		m = _m;
		mp = _mp;
		tag = _tag;
	}
}nd[300050];

void build(int x, int l, int r) {//检查过
	if(l == r) {
		nd[x].in(l, r, 1, 1, 1, l, -1);
 	}
	else {
		int mid = (l + r) / 2;
		int len = r - l + 1;
		build(x << 1, l, mid);
		build(x << 1 | 1, mid + 1, r);
		nd[x].in(l, r, len, len, len, l, -1);
  	}
}

void push_down(int k) {
	if(nd[k].tag == 1) {//该区间以占满
		nd[k].lm = nd[k].rm = nd[k].m = nd[k].mp = -1;
		nd[k << 1].tag = 1;
		nd[k << 1 | 1].tag = 1;
		nd[k].tag = -1;
	}
	if(nd[k].tag == 0) {//该空间被清空
		nd[k << 1].tag = nd[k << 1 | 1].tag = 0;
		nd[k].lm = nd[k].rm = nd[k].m = (nd[k].r - nd[k].l + 1);
		nd[k].mp = nd[k].l;
		nd[k].tag = -1;
	}
	
}

void push_up(int k) {
	push_down(k);
	push_down(k << 1);
	push_down(k << 1 | 1);
	int x1 = nd[k << 1].m , x2 = nd[k << 1].rm + nd[k << 1 | 1].lm, x3 = nd[k << 1 | 1].m;
	if(x1 >= x2 && x1 >= x3) {//注意！！！！！这3个判断是有优先级的
		nd[k].m = x1;
		nd[k].mp = nd[k << 1].mp;
	}
	else if(x2 >= x3) {
		nd[k].m = x2;
		nd[k].mp = nd[k << 1].r - nd[k << 1].rm + 1;
	}
	else {
		nd[k].m = x3;
		nd[k].mp = nd[k << 1 | 1].mp;
	}
	
//	nd[k].lm = nd[k << 1].lm;
//	if(nd[k << 1].lm == nd[k << 1].r - nd[k << 1].l + 1) {
//		nd[k].lm = max(nd[k].lm, nd[k << 1].lm + nd[k << 1 | 1].lm);
//	}
//	nd[k].rm = nd[k << 1 | 1].rm;
//	if(nd[k << 1 | 1].rm == nd[k << 1 | 1].r - nd[k << 1 | 1].l + 1) {
//		nd[k].rm = max(nd[k].rm, nd[k << 1].rm + nd[k << 1 | 1].rm);//一定要用max（）函数，因为rm可能为-1
//	}
	
	
	int lenl = nd[k << 1].r - nd[k << 1].l + 1;
	int lenr = nd[k << 1 | 1].r - nd[k << 1 | 1].l + 1;
	nd[k].lm = nd[k << 1].lm;
	if(nd[k << 1].lm == lenl) {
		nd[k].lm = max(nd[k].lm, nd[k << 1].lm + nd[k << 1 | 1].lm);
	}
  nd[k].rm = nd[k << 1 | 1].rm;
	if(nd[k << 1 | 1].rm == lenr) {
		nd[k].rm = max(nd[k].rm, nd[k << 1 | 1].rm + nd[k << 1].rm);    
	}
	
}

int query() {
	push_down(1);
	return nd[1].m;
}

int get_the_smallest_mp (int k, int len) {
	push_down(k);
	if(nd[k].m < len) return 0;
	else if(nd[k].lm >= len) return nd[k].l;
	else if(nd[k << 1].m >= len) return get_the_smallest_mp(k << 1, len);
	else if (nd[k << 1].rm >= 0 && nd[k << 1 | 1].lm >= 0 && nd[k << 1].rm + nd[k << 1 | 1].lm >= len) return (nd[k << 1].r - nd[k << 1].rm + 1);
	else return get_the_smallest_mp(k << 1 | 1, len);
}

void change(int k, int l, int r, int tag) {
	push_down(k);
	if(l <= nd[k].l && nd[k].r <= r) {
		nd[k].tag = tag;
		return;
	}
	else if(l > nd[k].r || r < nd[k].l) {
		return;
	}
	change(k << 1, l, r, tag);
	change(k << 1 | 1, l, r, tag);
	push_up(k);
}

int main() {
#ifndef MYLAB
	freopen("haoi13t4.in", "r", stdin);
	freopen("haoi13t4.out", "w", stdout);
#else
	freopen("in.txt", "r", stdin);
#endif

	n = read();
	m = read();
	
	build(1, 1, n);
	
//	for(int i = 1; i <= 25; i++) {
//		printf("%d \nl : %d, r : %d\n", i, nd[i].l, nd[i].r);
//	}
	
	for(int i = 1; i <= m; i++) {
		int type = read();
		if(type == 1) {//安装应用
		    int len = read();
//		    printf("query() = %d\n", query());
			if(query() < len) {
				printf("0\n");
			}
			else {
				int sm =get_the_smallest_mp(1, len);
				printf("%d\n", sm);
				change(1, sm, sm + len - 1, 1);//tag 1 是占用该内存
			}
		}
		else {
			int x = read();
			int len = read();
			change(1, x, x + len - 1, 0);//tag 0 清空
		}
	}
	return 0;
}