hdu4614 Vases and Flowers

题意：
$Alice$Alice有 $n$n个花瓶，编号从 $0\sim n$0∼n。每个花瓶可以插一朵花，每当他收到 $F$F朵花时，她将随机选择一个编号为 $A$A的花瓶，从这个花瓶开始往后到第 $n-1$n−1个花瓶，每当花瓶没有花时，可以将一朵花插在这个花瓶上。（当 $A\sim n-1$A∼n−1的花瓶都插满花了但是F朵花没有插完，也会停止）。

操作1：选择编号为A的花瓶，插入F朵花，当一朵都插不了时，输出 $"Cannotputanyone."$"Can not put any one."。否则输出插入的 $k$k朵花所在花瓶的首尾编号。
操作2：将编号为 $A\sim B$A∼B的花瓶全部清空，输出清空的花的数量。

题解：
线段树每个叶节点为 $1$1表示该点可用，0表示不可用。
每次查询首尾位置时二分从 $A\sim n$A∼n答案。

代码：

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N = 5e4 + 10;
int n, m, T;
struct Node{
	int l, r;
	int sum, add;
}tr[N << 2];

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

void build(int u, int l, int r) {
	tr[u] = {l, r, 1, -1};
	if(l == r) return ;
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
	pushup(u);
}

void pushdown(int u) {
	Node &root = tr[u], &left = tr[u << 1], &right = tr[u << 1 | 1];
	if(root.add != -1) {
		left.sum = (left.r - left.l + 1) * root.add;
		right.sum = (right.r - right.l + 1) * root.add;
		left.add = right.add = root.add;
		root.add = -1;
	}
}

int query(int u, int l, int r) {
	if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
	
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	int res = 0;
	if(l <= mid) res += query(u << 1, l, r);
	if(r > mid) res += query(u << 1 | 1, l, r);
	return res; 
}

void modify(int u, int l, int r, int c) {
	if(tr[u].l >= l && tr[u].r <= r) {
		tr[u].sum = (tr[u].r - tr[u].l + 1) * c;
		tr[u].add = c;
		return ;
	}
	
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if(l <= mid) modify(u << 1, l, r, c);
	if(r > mid) modify(u << 1 | 1, l, r, c);
	pushup(u);
}

int b_s(int A, int x) {
	int l = A, r = n;
	while(l < r) {
		int mid = l + r >> 1;
		if(query(1, A, mid) >= x) r = mid;
		else l = mid + 1;
	}
	return l;
}

int main()
{
	scanf("%d", &T);
	while(T--) {
		scanf("%d%d", &n, &m);
		build(1, 1, n);
		
		while(m--) {
			int op; scanf("%d", &op);
			if(op == 1) {
				int A, F;
				scanf("%d%d", &A, &F); A++;
				int cnt = query(1, A, n);
				if(cnt == 0) {
					puts("Can not put any one.");
					continue;
				}
				
				int l = b_s(A, 1);
				int r = b_s(A, min(F, cnt));
				modify(1, l, r, 0);
				printf("%d %d\n", l - 1, r - 1);
			}
			
			else {
				int A, B;
				scanf("%d%d", &A, &B); A++, B++;
				int res = query(1, A, B);
				res = B - A + 1 - res;
				printf("%d\n", res);
				modify(1, A, B, 1);
			}
		}
                puts("");
	}
	return 0;
}