hdu 4614 선분 트 리 + 2 분

제목: n 개의 꽃병, m 개의 조작, 꽃병 안에 꽃 이 있 고 빈 것 이 있 습 니 다.1. 조작 은 a 부터 오른쪽으로 b 송이 의 꽃 을 넣 는 것 입 니 다. 꽃병 에 있 는 것 은 넣 지 않 고 건 너 뛰 며 a 오른쪽 에 꽃 이 가득 놓 일 때 까지 나머지 는 버 렸 습 니 다.이번 꽃의 시작 위 치 를 출력 합 니 다.
구 와 조작 은 선분 트 리 로 해결 할 수 있 습 니 다. 조작 1 의 시작 위 치 는 2 분 구 를 통 해 구 할 수 있 습 니 다.

#include 
#include 
#include 
#include 
#include 
#define rep(i, j, k) for(int i = j; i <= k; i++)
#define maxn 100009

using namespace std;

int n, m, a[maxn * 8], is[8 * maxn];

void build (int x, int l, int r)
{
	if (l == r)
	{
		a[x] = 1;
		is[x] = -1;
		return;
	}
	int mid = (l + r) >> 1;
	build (2 * x, l, mid);
	build (2 * x + 1, mid + 1, r);
	a[x] = a[2 * x] + a[2 * x + 1];
	is[x] = -1;
	return;
}

int ask (int x, int l, int r, int la, int ra)
{
	if (l > ra || r < la)
		return 0;
	if (la <= l && r <= ra)
	{
		if (is[x] == 0)
			return 0;
		if (is[x] == 1)
			return r - l + 1;
		return a[x];
	}
	int mid = (l + r) >> 1;
	if (is[x] != -1)
	{
		is[2 * x] = is[2 * x + 1] = is[x];
		a[2 * x] = is[x] * (mid - l + 1);
		a[2 * x + 1] = is[x] * (r - mid);
		a[x] = is[x] * (r - l + 1);
		is[x] = -1;
	}
	return ask (2 * x, l, mid, la, ra) + ask (2 * x + 1, mid + 1, r, la, ra);
}

void set (int x, int l, int r, int la, int ra, int color)
{
	//printf ("========== set (%d %d) %d %d ==%d
", l, r, la, ra, color);
	if (l > ra || r < la)
		return;
	if (la <= l && r <= ra)
	{
		is[x] = color;
		a[x] = color * (r - l + 1);
		return;
	}
	int mid = (l + r) >> 1;
	if (is[x] != -1)
	{
		is[2 * x] = is[2 * x + 1] = is[x];
		a[2 * x] = is[x] * (mid - l + 1);
		a[2 * x + 1] = is[x] * (r - mid);
		a[x] = is[x] * (r - l + 1);
		is[x] = -1;
	}
	set (2 * x, l, mid, la, ra, color);
	set (2 * x + 1, mid + 1, r, la, ra, color);
	a[x] = a[2 * x] + a[2 * x + 1];
}

void print (int x, int l, int r)
{
//	printf (" %d    (%d, %d) == %d  ->   %d
", x, l, r, a[x], is[x]);
	if (l == r)
		return;
	int mid = (l + r) >> 1;
	print (2 * x, l, mid);
	print (2 * x + 1, mid + 1, r);
}

void debug ()
{
	printf ("==================================================
");
	print (1, 1, n);
}

int main ()
{
	int ti;
	cin >> ti;
	rep (f1, 1, ti)
	{
		cin >> n >> m;
		build (1, 1, n);
		while (m--)
		{
			//printf (" (ask 1-n) %d
", ask (1, 1, n, 1, n));
			//debug ();
			int col, x, y;
			scanf ("%d%d%d", &col, &x, &y);
			if (col == 1)
			{
				x++;
				int Max = ask (1, 1, n, x, n), L, R;
				//printf ("Max -----------------------------------%d
", Max);
				if (Max == 0)
				{
					printf ("Can not put any one.
");
					continue;
				}

				int l = x, r = n;
				while (l <= r)
				{
					int mid = (l + r) >> 1;
					int p = ask (1, 1, n, x, mid);
					if (p == 1)
						L = mid;
					if (p >= 1)
						r = mid - 1;
					else
						l = mid + 1;
				}
				/*if (Max <= y)
				{
					printf ("%d %d
", L - 1, n - 1);
					set (1, 1, n, L, n, 0);
					continue;
				}*/

				//last
				l = L, r = n;
				while (l <= r)
				{
					int mid = (l + r) >> 1;
					int p = ask (1, 1, n, L, mid);
					//printf ("er fen %d ----    %d
", mid, p);
					if (p == min (y, Max) )
						R = mid;
					if (p >= min (y, Max) )
						r = mid - 1;
					else
						l = mid + 1;
				}
				printf ("%d %d
", L - 1, R - 1);
				set (1, 1, n, L, R, 0);
				//printf ("ask ------ %d
", ask (1, 1, n, L, R));
			}
			else
			{
				x++, y++;
				printf ("%d
", y - x + 1 - ask (1, 1, n, x, y));
				set (1, 1, n, x, y, 1);
			}
		}
		
			printf ("
");
	}
	return 0;
}