hdu 4614 Vases and Flowers

写了一个星期了，时不时拿出来写一下，一直WA，今天总算是AC了，呜呜呜~~~

一开始想直接裸线段树，发现案例对不上，觉得二分一下右端点找最右边的就可以了

然后就自闭了啊，从线段树改成权值线段树，一直想直接求出端点，然后就自闭了一个星期

今天换了种方法，直接对左端点和右端点做两次二分，然后就A了。（我自闭了。

1、下标从0开始

2、题目要找的是，满足题意的左端点的最大值和右端点的最小值。

3、建议对左右端点二分。

4、一个案例多加一个换行。

Code：

#include <bits/stdc++.h>
#define ll long long
#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 = 50005;
struct node
{
	int l;
	int r;
	int mark;
	int sum;
}que[MAXN * 4];
int n, m, ql, qr;
int val;
void up(int k)
{
	que[k].sum = que[k << 1].sum + que[k << 1 | 1].sum;
}
void down(int k)
{
	if (que[k].mark == 1)
	{
		que[k << 1].mark = que[k].mark;
		que[k << 1].sum = que[k << 1].r - que[k << 1].l + 1;
		que[k << 1 | 1].mark = que[k].mark;
		que[k << 1 | 1].sum = que[k << 1 | 1].r - que[k << 1 | 1].l + 1;
		que[k].mark = -1;
	}
	else if (que[k].mark == 0)
	{
		que[k << 1].mark = que[k].mark;
		que[k << 1].sum = 0;
		que[k << 1 | 1].mark = que[k].mark;
		que[k << 1 | 1].sum = 0;
		que[k].mark = -1;
	}
}
void build(int left = 1, int right = n, int k = 1)
{
	que[k].l = left;
	que[k].r = right;
	que[k].mark = -1;
	que[k].sum = 0;
	if (left == right)
		return;
	imid;
	build(lson);
	build(rson);
}
void update(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return;
	if (ql <= left && right <= qr)
	{
		que[k].mark = val;
		que[k].sum = (que[k].r - que[k].l + 1) * val;
		return;
	}
	down(k);
	imid;
	update(lson);
	update(rson);
	up(k);
}
int query(int left = 1, int right = n, int k = 1)
{
	if (qr < left || right < ql)
		return 0;
	if (ql <= left && right <= qr)
		return que[k].sum;
	down(k);
	imid;
	return query(lson) + query(rson);
}
int op, a, b;
bool judge(int k)
{
	qr = k;
	int ans = query();
	if (ans + b <= k - ql + 1)
		return true;
	return false;
}
int main()
{
	int T, cas = 1;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d%d", &n, &m);
		build();
		while (m--)
		{
			scanf("%d%d%d", &op, &a, &b);
			if (op == 2)
			{
				a++;
				b++;
				ql = a;
				qr = b;
				int ans = query();
				val = 0;
				update();
				printf("%d\n", ans);
			}
			else
			{
				a++;

				ql = a;
				qr = n;
				//后面能不能放
				int ans = query();
				if (ans == n - a + 1)
				{
					printf("Can not put any one.\n");
					continue;
				}

				b = min(b, n - a + 1 - ans);

				//二分左端点
				ql = a;
				int l = a, r = n;
				while (l + 1 < r)
				{
					qr = (l + r) / 2;
					if (query() == qr - ql + 1)
						l = qr;
					else
						r = qr;
				}
				qr = l;
				if (query() == qr - ql + 1)
					qr = r;
				//二分右端点
				ql = qr;
				l = ql, r = n;
				while (l + 1 < r)
				{
					qr = (l + r) / 2;
					if (qr - ql + 1 - query() < b)
						l = qr;
					else
						r = qr;
				}
				qr = l;
				if (qr - ql + 1 - query() < b)
					qr = r;

				printf("%d %d\n", ql - 1, qr - 1);
				val = 1;
				update();
			}
		}
		//不要忘了换行
		printf("\n");
	}
}