HDU 2871（Memory Control）

题目分析：题目有4个操作：Reset指清空整个线段树，即题目所说的清空整个内存块；New N就是申请N个最靠左边的连续内存块，Free x操作是释放包含x的连续内存块，Get x，就是获得第x个内存块的起始节点，如果不深刻去体会，也许会认为要改造serch函数，其实仔细看看，事实是这样的：这里的建树，查询，更新都是与经典类型HOTEL里的一样的，如果不懂您可以看一下我另外一片博客，在这里我们已经解决了，1）查找包含x的区间的起始位置，2）申请一个长度为N的最靠左的连续区间，返回起点。然后我们会发挥已经解决的问题，我们用vector存取所有申请过的空间，删除所有释放的空间，查询第n个区间也是非常easy。关键在于vector可以在中间进行查询，增减！！这也是该题所要求的一个一个知识点。

#include<iostream>
#include<cstring>
#include<cstdio>
#include<vector>
using namespace std;

struct node{
	int a,b,lv,rv,cav;
	int flag;
}s[200000];

struct block{
	int x,y;
};

vector<block>vic;

int len(int num){
	return s[num].b-s[num].a+1;
}

void init(int num){
	s[num].lv=s[num].rv=s[num].cav=s[num].flag?0:len(num);
}

int Build(int x,int y,int num){
	s[num].a=x;	s[num].b=y;
	s[num].lv=s[num].rv=s[num].cav=len(num);
	s[num].flag=num==1?0:-1;
	if(x==y)
		return 0;
	int mid=(x+y)/2;
	Build(x,mid,num+num);
	Build(mid+1,y,num+num+1);
}

int search(int l,int num){
	if(s[num].a==s[num].b&&l==1)
		return s[num].a;
	if(s[num].flag!=-1){
		s[num+num].flag=s[num+num+1].flag=s[num].flag;
		init(num+num);	init(num+num+1);
		s[num].flag=-1;
	}
	if(s[num+num].cav>=l)
		return search(l,num+num);
	else if(s[num+num].rv+s[num+num+1].lv>=l)
		return s[num+num].b-s[num+num].rv+1;
	else if(s[num+num+1].cav>=l)
		return search(l,num+num+1);
	else return 0;
}

int modify(int x,int y,int flag,int num){
	if(x<=s[num].a&&y>=s[num].b){
		s[num].flag=flag;
		init(num);
		return 0;
	}
	if(s[num].flag!=-1){
		s[num+num+1].flag=s[num+num].flag=s[num].flag;
		s[num].flag=-1;
		init(num+num);	init(num+num+1);
	}
	int mid=(s[num].a+s[num].b)/2;
	if(x<=mid)
		modify(x,y,flag,num+num);	
	if(y>=mid+1)
		modify(x,y,flag,num+num+1);
	s[num].lv=s[num+num].lv;
	s[num].rv=s[num+num+1].rv;
	s[num].cav=max( max(s[num+num].cav,s[num+num+1].cav),s[num+num].rv+s[num+num+1].lv );
	if(s[num].lv==len(num+num))
		s[num].lv+=s[num+num+1].lv;
	if(s[num].rv==len(num+num+1))
		s[num].rv+=s[num+num].rv;
}

int count(int t){
	int beg=0,end=vic.size()-1;
	while(beg<=end){
		int mid=(beg+end)/2;
		if(vic[mid].x<=t)
			beg=mid+1;
		else
			end=mid-1;
	}
	return end;
}

int main(){
	int m,n,t,pos;
	char c[20];
	while(scanf("%d %d",&n,&m)!=EOF){
		Build(1,n,1);
		vic.clear();//一定要注意清空，不然您会wa的莫名其妙
		while(m--){
			scanf("%s",c);
			if(!strcmp(c,"Reset")){
				modify(1,n,0,1);
				vic.clear();
				printf("Reset Now\n");
			}
			else if(!strcmp(c,"New")){
				scanf("%d",&t);
				if(t>s[1].cav){
					printf("Reject New\n");
					continue;	
				}
				int id=search(t,1);
				if(id){
					modify(id,id+t-1,1,1);
					printf("New at %d\n",id);
				        pos=count(id)+1;
					block tempt;
					tempt.x=id;	tempt.y=id+t-1;
					vic.insert(vic.begin()+pos,tempt);
				}
				else
					printf("Reject New\n");
			}
			else if(!strcmp(c,"Free")){
				scanf("%d",&t);
				if(vic.size())
					 pos=count(t);
				else    pos=-1;
				if(pos==-1||vic[pos].y<t)
					printf("Reject Free\n");
				else{
					printf("Free from %d to %d\n",vic[pos].x,vic[pos].y);
					modify(vic[pos].x,vic[pos].y,0,1);
					vic.erase(vic.begin()+pos,vic.begin()+pos+1);
				}
				
			}
			else {
				int t;
                		scanf("%d",&t);
                		if(t<= vic.size()&&t> 0)
                    			printf("Get at %d\n" , vic[t-1].x);
               			 else
                    			printf("Reject Get\n");
			}			
		}
		printf("\n");
	}
	return 0;
}