poj3667

この問題はノードごとに3つの追加情報があります.
1.左端点をはじめ最長連続アイドル
2.右端点をはじめとする(左へ)最長アイドル
3.当該区間の総最長空き
肝心なのは一番左のセグメントを探す上で、最初のノードが一番長い区間のmax<必要な長さ出力0である場合
それから左を考えてから左を考え、右を迎えてから右を考えます.

#include <iostream>
#include <string.h>
#define Max(a,b) (a)>(b)?(a):(b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1

using namespace std;

const int MAXN=50005;

struct segtree{
	int l,r,max;
	int len;
	int cov;
}seg[MAXN<<2];

void pushdown(int rt)
{
	if(seg[rt].cov!=-1){
		seg[rt<<1].cov = seg[rt<<1|1].cov = seg[rt].cov;
		if(seg[rt].cov)
		  seg[rt<<1].l=seg[rt<<1|1].l=seg[rt<<1].r=seg[rt<<1|1].r=seg[rt<<1].max=seg[rt<<1|1].max=0;
		else{
			seg[rt<<1].l=seg[rt<<1].r=seg[rt<<1].len;
			seg[rt<<1|1].l=seg[rt<<1|1].r=seg[rt<<1|1].len;
		}
		seg[rt].cov=-1;
	}
	
}

void pushup(int rt)
{
	seg[rt].l=seg[rt<<1].l;
	seg[rt].r=seg[rt<<1|1].r;
	if(seg[rt].l==seg[rt<<1].len)
	  seg[rt].l+=seg[rt<<1|1].l;
	if(seg[rt].r==seg[rt<<1|1].len)
	  seg[rt].r+=seg[rt<<1].r;
	seg[rt].max=Max(Max(seg[rt<<1].max,seg[rt<<1|1].max),seg[rt<<1].r+seg[rt<<1|1].l);
}

void build(int l,int r,int rt)
{
	seg[rt].l=seg[rt].r=seg[rt].max=seg[rt].len=r-l+1;
	seg[rt].cov=-1;
	if(l==r)
	{
		return;
	}
	int m= r+l >>1;
	build(lson);
	build(rson);
}

void update(int val,int a,int b,int l,int r,int rt)
{
	if(a<=l && b>=r){
		if(val)
		  seg[rt].l=seg[rt].r=seg[rt].max=0;
		else
		  seg[rt].l=seg[rt].r=seg[rt].max=seg[rt].len;
		seg[rt].cov=val;
		return;
	}
	int m=(r+l)>>1;
	pushdown(rt);
	if(a<=m)
	  update(val,a,b,lson);
	if(b>m)
	  update(val,a,b,rson);
	pushup(rt);
}

int query(int num,int l,int r,int rt)
{
	if(l==r)
	  return l;
	int ret,m = r+l >>1;
	pushdown(rt);
	if(seg[rt<<1].max>=num)
	  ret =query(num,lson);
	else if(seg[rt<<1].r+seg[rt<<1|1].l>=num)
	  ret = m-seg[rt<<1].r+1;
	else ret= query(num,rson);
	pushup(rt);
	return ret;
}

int main()
{
	int n,m,k,x,y;
	while(cin>>n>>m)
	{
		build(1,n,1);
		while(m--)
		{
			cin>>k;
			if(k==1)
			{
				cin>>x;
				if(seg[1].max<x)
				  cout<<"0"<<endl;
			    else
				{
					int tp = query(x,1,n,1);
					cout<<tp<<endl;
					update(1,tp,tp+x-1,1,n,1);
				}

			}
			else
			{
				cin>>x>>y;
				update(0,x,x+y-1,1,n,1);
			}


		}
	}
	return 0;
}