HDU 4553 约会安排

当一个基友来找小明时，小明就根据“首次适应算法”来找一段空闲的时间来和基友约好，如果找到，就说“X,let’s fly”（此处，X为开始时间），否则就说“fly with yourself”；
　　当女神来找小明时，先使用一次“首次适应算法”，如果没有找到，小明就冒着木叽叽的风险无视所有***丝基友的约定，再次使用“无视基友首次适应算法”，两次只要有一次找到，就说“X,don’t put my gezi”（此处，X为开始时间），否则就说“wait for me”
　　当然，我们知道小明不是一个节操负无穷的人，如果和女神约会完，还有剩余时间，他还是会和原来约好的基友去dota的。（举个例子：小西（***丝）和小明约好在1~5这个时间单位段内打dota，这时候，女神来和小明预约长度为3的时间段，那么最终就是1~3小明去和女神约会，搞定后在4~5和小西打dota）
　　小明偶尔也会想要学习新知识，此时小明就会把某一个时间区间的所有已经预定的时间全部清空用来学习并且怒吼“I am the hope of chinese chengxuyuan!!”，不过小明一般都是三分钟热度，再有人来预定的话，小明就会按耐不住寂寞把学习新知识的时间分配出去。

https://cn.vjudge.net/problem/HDU-4553

求区间长度大于等于 K 的左端点的最小值 + 区间合并

//https://cn.vjudge.net/problem/HDU-4553
/*
 * queds线段树维护***丝和女神的空闲时间
 * quens线段树维护女神的空闲时间，
 * 因为要求区间最长空闲时间小于等于K的最左端点，
 * 在查询的时候，可以满足题意的最长空闲时间是横跨左右子区间的，
 * 所以每个线段需要维护左最长和右最长，还有区间最长，这样就可以处理上述情况
 * 如果这个人是女神的话，无论是计算哪棵树，最后都要更新两个区间（因为他是女神
 * 下面的代码以 1 表示空闲， 0 表示被占有
 */
#include <bits/stdc++.h>
#define sc scanf
#define pr printf
#define lson left,mid,k<<1
#define rson mid+1,right,k<<1|1
#define imid int mid=(left+right)/2;
using namespace std;
const int MAXN = 1e5 + 5;
struct node
{
	int l;
	int r;
	int mark;
	int lmaxn;
	int rmaxn;
	int mmaxn;
}quens[MAXN * 4], queds[MAXN * 4];
int n, m, ql, qr, val;
void upns(int k)
{
	quens[k].lmaxn = quens[k << 1].lmaxn;
	if (quens[k << 1].lmaxn == quens[k << 1].r - quens[k << 1].l + 1)
		quens[k].lmaxn += quens[k << 1 | 1].lmaxn;
	quens[k].rmaxn = quens[k << 1 | 1].rmaxn;
	if (quens[k << 1 | 1].rmaxn == quens[k << 1 | 1].r - quens[k << 1 | 1].l + 1)
		quens[k].rmaxn += quens[k << 1].rmaxn;
	quens[k].mmaxn = max(quens[k << 1].mmaxn, quens[k << 1 | 1].mmaxn);
	quens[k].mmaxn = max(quens[k].mmaxn, quens[k << 1].rmaxn + quens[k << 1 | 1].lmaxn);
}
void downns(int k)
{
	if (quens[k].mark != -1)
	{
		quens[k << 1].lmaxn = (quens[k << 1].r - quens[k << 1].l + 1) * quens[k].mark;
		quens[k << 1].rmaxn = (quens[k << 1].r - quens[k << 1].l + 1) * quens[k].mark;
		quens[k << 1].mmaxn = (quens[k << 1].r - quens[k << 1].l + 1) * quens[k].mark;
		quens[k << 1].mark = quens[k].mark;
		quens[k << 1 | 1].lmaxn = (quens[k << 1 | 1].r - quens[k << 1 | 1].l + 1) * quens[k].mark;
		quens[k << 1 | 1].rmaxn = (quens[k << 1 | 1].r - quens[k << 1 | 1].l + 1) * quens[k].mark;
		quens[k << 1 | 1].mmaxn = (quens[k << 1 | 1].r - quens[k << 1 | 1].l + 1) * quens[k].mark;
		quens[k << 1 | 1].mark = quens[k].mark;
		quens[k].mark = -1;
	}
}
void buildns(int left = 1, int right = n, int k = 1)
{
	quens[k].l = left;
	quens[k].r = right;
	quens[k].mark = -1;
	if (left == right)
	{
		quens[k].lmaxn = 1;
		quens[k].rmaxn = 1;
		quens[k].mmaxn = 1;
		return;
	}
	imid;
	buildns(lson);
	buildns(rson);
	upns(k);
}
void updatens(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		quens[k].mark = val;
		quens[k].lmaxn = val * (quens[k].r - quens[k].l + 1);
		quens[k].rmaxn = val * (quens[k].r - quens[k].l + 1);
		quens[k].mmaxn = val * (quens[k].r - quens[k].l + 1);
		return;
	}
	downns(k);
	imid;
	updatens(lson);
	updatens(rson);
	upns(k);
}
int queryns(int left = 1, int right = n, int k = 1)
{
	if (left == right)
		return left;
	imid;
	downns(k);
	if (quens[k << 1].mmaxn >= val)
		return queryns(lson);
	else if (quens[k << 1].rmaxn + quens[k << 1 | 1].lmaxn >= val)
		return mid - quens[k << 1].rmaxn + 1;
	else
		return queryns(rson);
}

void upds(int k)
{
	queds[k].lmaxn = queds[k << 1].lmaxn;
	if (queds[k << 1].lmaxn == queds[k << 1].r - queds[k << 1].l + 1)
		queds[k].lmaxn += queds[k << 1 | 1].lmaxn;
	queds[k].rmaxn = queds[k << 1 | 1].rmaxn;
	if (queds[k << 1 | 1].rmaxn == queds[k << 1 | 1].r - queds[k << 1 | 1].l + 1)
		queds[k].rmaxn += queds[k << 1].rmaxn;
	queds[k].mmaxn = max(queds[k << 1].mmaxn, queds[k << 1 | 1].mmaxn);
	queds[k].mmaxn = max(queds[k].mmaxn, queds[k << 1].rmaxn + queds[k << 1 | 1].lmaxn);
}
void downds(int k)
{
	if (queds[k].mark != -1)
	{
		queds[k << 1].lmaxn = (queds[k << 1].r - queds[k << 1].l + 1) * queds[k].mark;
		queds[k << 1].rmaxn = (queds[k << 1].r - queds[k << 1].l + 1) * queds[k].mark;
		queds[k << 1].mmaxn = (queds[k << 1].r - queds[k << 1].l + 1) * queds[k].mark;
		queds[k << 1].mark = queds[k].mark;
		queds[k << 1 | 1].lmaxn = (queds[k << 1 | 1].r - queds[k << 1 | 1].l + 1) * queds[k].mark;
		queds[k << 1 | 1].rmaxn = (queds[k << 1 | 1].r - queds[k << 1 | 1].l + 1) * queds[k].mark;
		queds[k << 1 | 1].mmaxn = (queds[k << 1 | 1].r - queds[k << 1 | 1].l + 1) * queds[k].mark;
		queds[k << 1 | 1].mark = queds[k].mark;
		queds[k].mark = -1;
	}
}
void buildds(int left = 1, int right = n, int k = 1)
{
	queds[k].l = left;
	queds[k].r = right;
	queds[k].mark = -1;
	if (left == right)
	{
		queds[k].lmaxn = 1;
		queds[k].rmaxn = 1;
		queds[k].mmaxn = 1;
		return;
	}
	imid;
	buildds(lson);
	buildds(rson);
	upds(k);
}
void updateds(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		queds[k].mark = val;
		queds[k].lmaxn = val * (queds[k].r - queds[k].l + 1);
		queds[k].rmaxn = val * (queds[k].r - queds[k].l + 1);
		queds[k].mmaxn = val * (queds[k].r - queds[k].l + 1);
		return;
	}
	downds(k);
	imid;
	updateds(lson);
	updateds(rson);
	upds(k);
}
int queryds(int left = 1, int right = n, int k = 1)
{
	if (left == right)
		return left;
	imid;
	downds(k);
	if (queds[k << 1].mmaxn >= val)
		return queryds(lson);
	else if (queds[k << 1].rmaxn + queds[k << 1 | 1].lmaxn >= val)
		return mid - queds[k << 1].rmaxn + 1;
	else
		return queryds(rson);
}
char op[10];
int t1, t2;
int main()
{
	int T, cas = 1;
	sc("%d", &T);
	while (T--)
	{
		sc("%d%d", &n, &m);
		pr("Case %d:\n", cas++);
		buildns();
		buildds();
		while (m--)
		{
			sc("%s", op);
			if (op[0] == 'D')
			{
				scanf("%d", &t1);
				if (queds[1].mmaxn >= t1)
				{
					val = t1;
					ql = queryds();
					qr = ql + t1 - 1;
					val = 0;
					updateds();
					pr("%d,let's fly\n", ql);
				}
				else
				{
					pr("fly with yourself\n");
				}
			}
			else if (op[0] == 'N')
			{
				scanf("%d", &t1);
				if (queds[1].mmaxn >= t1)
				{
					val = t1;
					ql = queryds();
					qr = ql + t1 - 1;
					val = 0;
					updateds();
					updatens();
					pr("%d,don't put my gezi\n", ql);
				}
				else if (quens[1].mmaxn >= t1)
				{
					val = t1;
					ql = queryns();
					qr = ql + t1 - 1;
					val = 0;
					updateds();
					updatens();
					pr("%d,don't put my gezi\n", ql);
				}
				else
				{
					pr("wait for me\n");
				}
			}
			else
			{
				sc("%d%d", &ql, &qr);
				val = 1;
				updateds();
				updatens();
				printf("I am the hope of chinese chengxuyuan!!\n");
			}
		}
	}
}
/*
5 6
DS 3
NS 3
NS 4
STUDY!! 1 5
DS 4
NS 2
*/