学步园

题意：n个点m次操作，1：从st处开始向右找出最多的0，使0变1 。2：使连续一段区间的1都变0

主要是区间更新及区间查询，更新就是找出区间记录下来的x就行了，查询的时候由于查找的区间是不连续的，因此需要根据区间内1的数量，确定更新的起点和终点，然后普通的成端更新就可以了

#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

#define lson l, mid, rt << 1
#define rson mid + 1, r, rt << 1 | 1
#define pi acos(-1.0)
#define eps 1e-8
typedef long long ll;
const int inf = 0x3f3f3f3f;
const int N = 50050;

struct node{
	int l, r;
	int len, x, add;
}tr[N << 2];
//x 剩下的位置来插花
//add = 1表示有插花，0表示没处理，-1表示清理过
//所以在pushdown的时候，没处理过或者重新清理过的x都为len，有插花x则为0
int n, m;
int st, ed;

void build( int l, int r, int rt )
{
	tr[rt].l = l;
	tr[rt].r = r;
	tr[rt].add = 0;
	tr[rt].len = ( r - l + 1);
	tr[rt].x = tr[rt].len;
	if( l == r )
		return;
	int mid = ( l + r ) >> 1;
	build( lson );
	build( rson );
}

void pushup( int rt )
{
	tr[rt].x = tr[rt<<1].x + tr[rt<<1|1].x;
}

void down( int rt )
{
	tr[rt<<1|1].add = tr[rt<<1].add = tr[rt].add;
	if( tr[rt].add == -1 || tr[rt].add == 0 )
	{
		tr[rt<<1].x = tr[rt<<1].len;
		tr[rt<<1|1].x = tr[rt<<1|1].len;
	}
	else
		tr[rt<<1].x = tr[rt<<1|1].x = 0;
	tr[rt].add = 0;
}

void find_st( int aim, int rt )
{
	if( !tr[rt].x )
		return;
	if( tr[rt].l == tr[rt].r )
	{
		if( tr[rt].l <= aim && tr[rt].x )
			st = tr[rt].l;
		return;
	}
	if( tr[rt].add )
		down( rt );
	int mid = ( tr[rt].l + tr[rt].r ) >> 1;
	if( aim > mid )
		find_st( aim, rt << 1 | 1);
	else
	{
		find_st( aim, rt << 1 );
		if( st == -1 )
			find_st( mid+1, rt << 1 | 1 );
	}
	pushup( rt );
}

int query( int l, int r, int rt )	//计算区间内空花盆数量
{
	if( l <= tr[rt].l && tr[rt].r <= r )
	{
		return tr[rt].x;
	}
	if( tr[rt].add )
		down( rt );
	int mid = ( tr[rt].l + tr[rt].r ) >> 1, ans;
	if( r <= mid )
		ans = query( l, r, rt << 1 );
	else if( l > mid )
		ans = query( l, r, rt << 1 | 1 );
	else
		ans = query( lson ) + query( rson );
	pushup( rt );
	return ans;
}

void insert( int l, int r, int rt )	//插入花
{
	if( l <= tr[rt].l && tr[rt].r <= r )
	{
		tr[rt].add = 1;
		tr[rt].x = 0;
		return;
	}
	if( tr[rt].add )
		down( rt );
	int mid = ( tr[rt].l + tr[rt].r ) >> 1;
	if( r <= mid )
	{
		insert( l, r, rt << 1 );
	}
	else if( l > mid )
	{
		insert( l, r, rt << 1 | 1 );
	}
	else
	{
		insert( lson );
		insert( rson );
	}
	pushup( rt );
}

int update( int l, int r, int rt )	//清理
{
	int ans;
	if( l <= tr[rt].l && tr[rt].r <= r )
	{
		tr[rt].add = -1;
		ans = tr[rt].len - tr[rt].x;
		tr[rt].x = tr[rt].len;
		return ans;
	}
	if( tr[rt].add )
		down( rt );
	int mid = ( tr[rt].l + tr[rt].r ) >> 1;
	if( r <= mid )
		ans = update( l, r, rt << 1 );
	else if( l > mid )
		ans = update( l, r, rt << 1 | 1 );
	else
		ans = update( lson ) + update( rson );
	pushup( rt );
	return ans;
}

int main()
{
	int tot;
	scanf("%d", &tot);
	while( tot-- )
	{
		scanf("%d%d", &n, &m);
		int op, s, cnt;
		build( 0, n-1, 1 );
		while( m-- )
		{
			scanf("%d%d%d", &op, &s, &cnt);
			if( op == 1 )
			{
				st = ed = -1;
				int cur = query( s, n-1, 1 );
				if( cur == 0 )
				{
					puts("Can not put any one.");
					continue;
				}
				if( cur < cnt )
					cnt = cur;
				find_st( s, 1 );	//第一个位置
				int l = s, r = n-1;
				//二分确定区间最后一个位置
				while( l <= r )
				{
					int mid = ( l + r ) >> 1;
					if( query( s, mid, 1 ) < cnt )
						l = mid + 1;
					else
						r = mid - 1;
				}
				ed = l;
				insert( st, ed, 1 );
				printf("%d %d\n", st, ed );
			}
			else
			{
				printf("%d\n", update( s, cnt, 1 ));
			}
		}
		puts("");
	}
	return 0;
}