首页 > 分享 > Vases and Flowers HDU

Vases and Flowers HDU

花匠小妙招
2024-12-19 14:34

题目

Alice有N个花瓶（标号为0~ N-1）。当她收到一些花时，她会随机的选择一个瓶子A，从它开始遍历A，A+1, A+2, …, N-1号瓶子，遇到空瓶子就放一朵花进去，直到花朵放完或没有瓶子，剩下的花将被丢弃。有时，她也会清理标号从A到B的花瓶(A <= B).花瓶里的花会被丢弃。
Input

第一行一个整数T，表示数据组数。
每组数据，第一行一个整数N(1 < N < 50001) and M(1 < M < 50001). N 是花瓶个数, M 是Alice的操作次数. 接下来M行行3个整数. 第一个整数 K(1 or 2). 如果K=1, 后面跟两个整数 A 和 F . 表示Alice 得到了F 朵花并且把它们放入从A 的花瓶里. 如果K= 2, 后跟两个整数 A 和 B. 表示Alice 清理的花瓶标号范围(A <= B).

Output
对于每个K=1的操作，输出第一朵和最后一朵花放置的花瓶标号。如果没有任何放花的位置，输出’Can not put any one.’.对于K=2的操作，输出丢弃花的个数.
每组数据后输出一个空行.
Sample Input

2
10 5
1 3 5
2 4 5
1 1 8
2 3 6
1 8 8
10 6
1 2 5
2 3 4
1 0 8
2 2 5
1 4 4
1 2 3

Sample Output

3 7
2
1 9
4
Can not put any one.

2 6
2
0 9
4
4 5
2 3

解释

在不改变线段树基本操作的情况下，如何实现从第a个位置开始放f朵花，多余的不要？
如果可以知晓a位置以后的空瓶数，如果空瓶数少于花数，那么插入花数就当做空瓶数。当空瓶数大于花数，如果不改变线段树的基本操作，必须得知道放花的最后位置与起始位置。起始位置为a。
对于最后位置如果在线段树进行更新，必须知道具体的区间位置，如果是通过左右子树层层查改，更加费时。所以通过不断区间查询得到区间空瓶数，再二分查找到具体的最后位置后，就可以用线段树的区间更新。
由于空瓶数随区间增大必然是单调不递减的，可以用线段树维护区间空瓶数，二分查找因此可以使用。但其实区间维护有花数，二分查找递减的，应该也可以做。

#include <cstdio> #include <cstring> #include <algorithm> #define maxn 50005 using namespace std; int n, m; struct node {int l, r;int sum; }num[maxn*4]; int lazy[maxn * 4]; void bulid(int l, int r, int ret) {num[ret].l = l;num[ret].r = r;num[ret].sum = r-l+1;lazy[ret] = -1;if (l == r) return;int m = (l + r) >> 1;bulid(l, m, ret << 1);bulid(m + 1, r, ret << 1 | 1); } void pushdown(int ret) {if (lazy[ret] != -1) {num[ret << 1].sum = (num[ret << 1].r - num[ret << 1].l + 1) * lazy[ret];num[ret << 1|1].sum = (num[ret << 1|1].r - num[ret << 1|1].l + 1) * lazy[ret];lazy[ret << 1] = lazy[ret << 1 | 1] = lazy[ret];lazy[ret] = -1;} } void update(int L, int R, int c, int ret) {if (L <= num[ret].l && num[ret].r <= R) {num[ret].sum = (num[ret].r - num[ret].l + 1) * c;lazy[ret] = c;return ;}pushdown(ret);int m = (num[ret].l + num[ret].r) >> 1;if (m >= L) update(L, R, c, ret << 1);if (m < R) update(L, R, c, ret << 1 | 1);num[ret].sum = num[ret << 1].sum + num[ret << 1 | 1].sum; } int query(int L, int R, int ret) {int ans = 0;if (L <= num[ret].l && num[ret].r <= R) {return num[ret].sum;}pushdown(ret);int m = (num[ret].l + num[ret].r) >> 1;if (m >= L) ans += query(L, R, ret << 1);if (m < R) ans += query(L, R, ret << 1 |1);return ans; } int find(int pos, int num) {int l = pos, r = n;int m;int ans;while (l <= r) {m = (l + r) >> 1;if (query(pos, m, 1) >= num) {r = m - 1;ans = m;}elsel = m + 1;}return ans; } int main() {int t, op;int A, F, L, R, cnt;scanf("%d", &t);while (t--){scanf("%d %d", &n, &m);bulid(1, n, 1);for (int i = 0; i < m; i++) {scanf("%d", &op);if (op == 1) {scanf("%d %d", &A, &F);A++;cnt = query(A, n, 1);if (cnt == 0) printf("Can not put any one.n");else {L = find(A, 1);R = find(A, min(cnt, F));update(L, R, 0, 1);printf("%d %dn", L-1, R-1);}}else {scanf("%d %d", &L, &R);L++;R++;printf("%dn", R - L + 1 -query(L,R,1));update(L, R, 1, 1);}}printf("n");}return 0; }

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105