HDU – 4553 约会安排（[线段树] 区间合并+区间更新）

1. op 1 选择占用最左边的长度为x的连续区间
   1. 有则输出区间最左端位置
   2. 无则输出无
2. op 2 选择占用最左边的长度为x的连续区间
   1. 有则输出区间最左端位置
   2. 无则可以将op1操作占用的空间视作空位，然后选择占用最左边的长度为x的连续区间（未被op2占用的op1占用的空间仍然被op1占用）
      1. 有则ok
      2. 无则GG
3. op 3 清空区间[a,b]内的占用

• medium==整段长度 与 medium==0分别代表了整段空闲以及整段占用，在修改时标记，查询时往下传递即可

#include<stdio.h>
#include<string.h>
#include<map>
#include<vector>
#include<iostream>
#include<algorithm>
#include<queue>
#include<deque>
#include<cmath>
#define ll long long
#define ls p<<1
#define rs p<<1|1
using namespace std;
const int maxn = 1e6+10;
struct Node {
	int l;
	int r;
	int medium;
	int prefix;
	int suffix;
} a[maxn<<2],b[maxn<<2];
void build(int p,int l,int r) {
	a[p].prefix=a[p].suffix=a[p].medium=r-l+1;
	a[p].l=l,a[p].r=r;
	b[p].prefix=b[p].suffix=b[p].medium=r-l+1;
	b[p].l=l,b[p].r=r;
	if(l==r) {
		return ;
	}
	int mid=(l+r)>>1;
	build(p<<1,l,mid);
	build(p<<1|1,mid+1,r);
}
void pushup(int p) {
	int m=(a[p].l+a[p].r)>>1;
	a[p].prefix=a[ls].prefix;//左子树的左连续区间肯定是父亲节点左连续区间的一部分
	a[p].suffix=a[rs].suffix;//或者说父亲节点的右连续区间肯定包括右子树的右连续区间
	a[p].medium=max(max(a[ls].medium,a[rs].medium),a[ls].suffix+a[rs].prefix);
	//父亲节点的最长连续区间要么是左子树的最长连续区间 要么右子树的最长连续区间  要么左子树右连续+右子树左连续
	if(a[ls].prefix==m-a[p].l+1) a[p].prefix+=a[rs].prefix;
	//如果左子树的左连续长度为整个左子树的长度，那么父亲节点的左连续区间得加上 右子树的左连续区间
	if(a[rs].suffix==a[p].r-m)   a[p].suffix+=a[ls].suffix;//同理
    // 
	b[p].prefix=b[ls].prefix;
	b[p].suffix=b[rs].suffix;
	b[p].medium=max(max(b[ls].medium,b[rs].medium),b[ls].suffix+b[rs].prefix);
	if(b[ls].prefix==m-a[p].l+1) b[p].prefix+=b[rs].prefix;
	if(b[rs].suffix==a[p].r-m)   b[p].suffix+=b[ls].suffix;
}
void pushdown(int l,int r,int p) { //下推标记
	int m=(l+r)>>1;
	if(a[p].medium==r-l+1) { //学习操作的下推
		a[ls].prefix=a[ls].suffix=a[ls].medium=m-l+1;
		a[rs].prefix=a[rs].suffix=a[rs].medium=r-m;
	} else if(a[p].medium==0) { //约人操作的下推
		a[ls].prefix=a[ls].suffix=a[ls].medium=0;
		a[rs].prefix=a[rs].suffix=a[rs].medium=0;
	}
	if(b[p].medium==r-l+1) {
		b[ls].prefix=b[ls].suffix=b[ls].medium=m-l+1;
		b[rs].prefix=b[rs].suffix=b[rs].medium=r-m;
	} else if(b[p].medium==0) {
		b[ls].prefix=b[ls].suffix=b[ls].medium=0;
		b[rs].prefix=b[rs].suffix=b[rs].medium=0;
	}
}
void change(int l,int r,int p,int x) {
	if(l<=a[p].l&&a[p].r<=r) {//只会发生区间更新呢
		if(x==1)//基友，更新树A
			a[p].prefix=a[p].medium=a[p].suffix=0;
		else if(x==0)//女神，更新树A和B中对应区间为0
			b[p].prefix=b[p].medium=b[p].suffix=a[p].prefix=a[p].medium=a[p].suffix=0;//要同时修改两个区间
		else//学习，更新树A和B中对应区间值为区间长度
			b[p].prefix=b[p].medium=b[p].suffix=a[p].prefix=a[p].medium=a[p].suffix=a[p].r-a[p].l+1;//同时修改两个
		return;
	}
	pushdown(a[p].l,a[p].r,p);//常规懒惰
	int m=(a[p].l+a[p].r)>>1;
	if(l<=m) change(l,r,ls,x);
	if(r>m) change(l,r,rs,x);
	pushup(p);//常规回溯后总结
}
int ask(int p,int x,int op) {//ask询问的是位置，只会出现在最长连续满足条件的区间左子树右连续的左端点 
	if(a[p].l==a[p].r) return a[p].l;//单个区间内直接返回就完事了
	pushdown(a[p].l,a[p].r,p);//常规懒惰
	int m=(a[p].l+a[p].r)>>1;
	if(op) { //基友
		if(a[ls].medium>=x)//左子树最长连续长度满足 x，最左端的点肯定在左子树
			return ask(ls,x,op);
		else if(a[ls].suffix+a[rs].prefix>=x)
			//左子树的右区间+右子树的左区间 长度满足x ，左端点肯定是 左子树右区间的起始点
			//没错，这里就是安全出口
			return m-a[ls].suffix+1;
		else//否则在右子树
			return ask(rs,x,op);
	} else { //女神
		if(b[ls].medium>=x)
			return ask(ls,x,op);
		else if(b[ls].suffix+b[rs].prefix>=x)
			return m-b[ls].suffix+1;
		else
			return ask(rs,x,op);
	}
}
int main() {
	char ch[10];
	int t,n,m,l,r,k;
	scanf("%d",&t);
	for(int ppp=1; ppp<=t; ppp++) {
		printf("Case %d:\n",ppp);
		scanf("%d%d",&n,&m);
		build(1,1,n);
		while(m--) {
			scanf("%s",ch);
			if(ch[0]=='D') {
				scanf("%d",&l);
				if(a[1].medium>=l) { //存在长度大等于x的连续空区间
					k=ask(1,l,1);
					printf("%d,let's fly\n",k);
					change(k,k+l-1,1,1);//最后一个1代表屌丝，只影响屌丝不影响女神区间
				} else
					printf("fly with yourself\n");
			} else if(ch[0]=='N') {
				scanf("%d",&l);
				if(a[1].medium>=l) {//如果存在不影响屌丝区间的区间
					k=ask(1,l,1);//在基友区间中查找
					printf("%d,don't put my gezi\n",k);
					change(k,k+l-1,1,0);//同时影响女神区间
				} else if(b[1].medium>=l) {//如果不存在则需要干掉屌丝
					k=ask(1,l,0);//在女神区间中查找
					printf("%d,don't put my gezi\n",k);
					change(k,k+l-1,1,0);//同时影响屌丝区间
				} else
					printf("wait for me\n");
			} else {
				scanf("%d%d",&l,&r);
				change(l,r,1,2);
				printf("I am the hope of chinese chengxuyuan!!\n");
			}
		}
	}
	return 0;
}