传送门：HDU 2871 Memory Control

题目大意：
一开始，你拥有一条长度为n(n <= 50000)的连续内存。编号从1开始。
然后进行m(m <= 50000)次操作。操作共有4种。
1.Reset：将整条内存空间释放（清空所有内存块）。
2.New x：申请一块长度为x的连续内存块，成功输出起始编号，如果多解，左边优先；无解输出Reject New。
3.Free x：将编号为x的内存块占用的位置释放，如果x位置被占用，输出占用x的内存块的左右编号，否则输出Reject Free。
4.Get x：输出内存条中从左到右第x个内存块的起始编号。如果不足x个则输出Reject Get。

题目分析：
首先是定义部分。

<span style="font-size:18px;">int lmax[maxN] , mmax[maxN] , rmax[maxN] ;//前缀，最长连续子串，后缀
int lnum[maxM] , rnum[maxM] ;//插入的内存块占用的区间左右端点
int last[maxN] ;//区间内最后一个内存块的编号
int nnum[maxN] ;//区间内内存块的数量
int mark[maxN] ;//0：释放，1：占用</span>

区间合并问题。
本题和POJ 3667 Hotel（题解戳这里）类似，都是申请空间以及释放空间问题。
对于区间连续长度问题，我们可以维护前缀，后缀，以及最大连续子串，PushUp时不断合并就行了。
对于操作Reset，我们不用重新Build（也根本没这么想），直接将根结点标记一下就好了。
对于操作New，用和Hotel一样的方法，利用前缀，后缀及最大连续子串先找最左端点，输出答案后，更新一下（就是在区间中标记这个内存块的空间以被占用）记录这块内存块的左端点和右端点。
对于操作Free，直接查找到叶子节点看叶子节点属于哪个内存块就好。用last[]就行了（如果存在最后一个肯定是自己）。
对于操作Get，我们需要用到nnum[]以及flag，flag的作用主要是判断是否已经标记，因为每个内存块之需要标记一次，这样可以达到区间内内存块计数的作用。
这样问题就基本解决了。

PS：写完后四处看了一下，发现对于Free和Get用的好像是vector或是set的什么功能（反正我不清楚）？欺负我不会STL，只能笨笨的用线段树解决了。还有这题是可以Splay解决的，这个还没学，以后再说吧。
第一发就PE我会乱说→_→（说明写对了，因为早就不在乎能一次AC了）

代码如下：

<span style="font-size:14px;">#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std ;

#define rt l , r , o
#define ls ( o << 1 )
#define rs ( o << 1 | 1 )
#define lson l , m , ls
#define rson m + 1 , r , rs
#define mid ( ( l + r ) >> 1 )
#define root 1 , n , 1
#define clear( A , X ) memset ( A , X , sizeof A )
#define DEBUG 0

const int maxN = 200005 ;
const int maxM = 50005 ;

int lmax[maxN] , mmax[maxN] , rmax[maxN] ;//前缀，最长连续子串，后缀
int lnum[maxM] , rnum[maxM] ;//插入的内存块占用的区间左右端点
int last[maxN] ;//区间内最后一个内存块的编号
int nnum[maxN] ;//区间内内存块的数量
int mark[maxN] ;//0：释放，1：占用
char ch[10] ;
int L , R ;
int flag ;//用于插入计数元素，0：还没插入，1：已经插入

int max ( const int X , const int Y ) {
	return X > Y ? X : Y ;
}

int min ( const int X , const int Y ) {
	return X < Y ? X : Y ;
}

void Debug ( int o ) {
	printf ( "nnum[%d] = %d\n" , o , nnum[o] ) ;
}

void PushUp ( int l , int r , int o ) {
	int m = mid ;
	//前缀
	lmax[o] = lmax[ls] ;
	if ( lmax[o] == m - l + 1 ) lmax[o] += lmax[rs] ;
	//后缀
	rmax[o] = rmax[rs] ;
	if ( rmax[o] == r - m ) rmax[o] += rmax[ls] ;
	//最大连续子串
	mmax[o] = max ( mmax[ls] , mmax[rs] ) ;
	mmax[o] = max ( mmax[o] , rmax[ls] + lmax[rs] ) ;
	//计数及区间中排最后的内存块的编号
	nnum[o] = nnum[ls] + nnum[rs] ;
	if ( nnum[rs] ) last[o] = last[rs] ;
	else last[o] = last[ls] ;
}

void PushDown ( int l , int r , int o ) {
	if ( ~mark[o] ) {
		int m = mid ;
		mark[ls] = mark[rs] = mark[o] ;
		last[ls] = last[rs] = last[o] ;
		nnum[ls] = nnum[o] ;
		nnum[rs] = 0 ;
		lmax[ls] = mmax[ls] = rmax[ls] = ( mark[o] ? 0 : m - l + 1 ) ;
		lmax[rs] = mmax[rs] = rmax[rs] = ( mark[o] ? 0 : r - m ) ;
		mark[o] = -1 ;
	}
}


void Update ( int x , int i , int l , int r , int o ) {
	if ( L <= l && r <= R ) {
		mark[o] = x ;
		lmax[o] = mmax[o] = rmax[o] = ( x ? 0 : r - l + 1 ) ;
		if ( !flag && x ) nnum[o] = 1 , flag = 1 ;
		else nnum[o] = 0 ;
		last[o] = ( x ? i : 0 ) ;
		return ;
	}
	PushDown ( rt ) ;
	int m = mid ;
	if ( L <= m ) Update ( x , i , lson ) ;
	if ( m <  R ) Update ( x , i , rson ) ;
	PushUp ( rt ) ;
	
#if DEBUG
	Debug ( o ) ;
#endif

}

int New ( int x , int l , int r , int o ) {
	if ( l == r ) return l ;
	PushDown ( rt ) ;
	int m = mid ;
	if ( mmax[ls] >= x ) return New ( x , lson ) ;
	else if ( rmax[ls] + lmax[rs] >= x ) return m - rmax[ls] + 1 ;
	else return New ( x , rson ) ;
}

int Get ( int x , int l , int r , int o ) {
	if ( l == r ) return last[o] ;
	PushDown ( rt ) ;
	int m = mid ;
	if ( nnum[ls] == x ) return last[ls] ;
	else if ( nnum[ls] > x ) return Get ( x , lson ) ;
	else return Get ( x - nnum[ls] , rson ) ;
}

int Free ( int x , int l , int r , int o ) {
	if ( l == r ) return last[o] ;
	PushDown ( rt ) ;
	int m = mid ;
	if ( x <= m ) return Free ( x , lson ) ;
	else return Free ( x , rson ) ;
}

void Build ( int l , int r , int o ) {
	mark[o] = -1 ;
	if ( l == r ) {
		lmax[o] = mmax[o] = rmax[o] = 1 ;
		nnum[o] = last[o] = 0 ;
		return ;
	}
	int m = mid ;
	Build ( lson ) ;
	Build ( rson ) ;
	PushUp ( rt ) ;
}

void work () {
	int n , m , x , l , r ;
	while ( ~scanf ( "%d%d" , &n , &m ) ) {
		Build ( root ) ;
		for ( int i = 1 ; i <= m ; ++ i ) {
			scanf ( "%s" , ch ) ;
			if ( ch[0] == 'R' ) {
				L = 1 , R = n ;
				Update ( 0 , 0 , root ) ;
				printf ( "Reset Now\n" ) ;
			}
			if ( ch[0] == 'N' ) {
				scanf ( "%d" , &x ) ;
				if ( mmax[1] < x ) printf ( "Reject New\n" ) ;
				else {
					lnum[i] = New ( x , root ) ;
					rnum[i] = lnum[i] + x - 1 ;
					printf ( "New at %d\n" , lnum[i] ) ;
					L = lnum[i] , R = rnum[i] ;
					flag = 0 ;
					Update ( 1 , i , root ) ;
				}
			}
			if ( ch[0] == 'G' ) {
				scanf ( "%d" , &x ) ;
				if ( nnum[1] < x ) printf ( "Reject Get\n" ) ;
				else {
					int ans = Get ( x , root ) ;
					printf ( "Get at %d\n" , lnum[ans] ) ;
				}
			}
			if ( ch[0] == 'F' ) {
				scanf ( "%d" , &x ) ;
				int ans = Free ( x , root ) ;
				if ( 0 == ans ) printf ( "Reject Free\n" ) ;
				else {
					printf ( "Free from %d to %d\n" , lnum[ans] , rnum[ans] ) ;
					L = lnum[ans] , R = rnum[ans] ;
					Update ( 0 , 0 , root ) ;
				}
			}
		}
		printf ( "\n" ) ;
	}
}
int main () {
	work () ;
	return 0 ;
}</span>