一共n个盒子， 两种操作， 第一种是给出两个数x, y， 从第x个盒子开始放y朵花， 一个盒子只能放一朵， 如果某个盒子已经有了， 那么就跳过这个盒子放下面的盒子。 直到花放完了或者到了最后一个盒子。 输出放的第一朵花和最后一朵花的坐标， 如果一朵也没法放， 输出Can not put any one.
第二种操作， 给出l, r， 求l, r区间内有多少朵花， 输出， 并且将l, r内的盒子全部变空。
思路： 第二种操作比较简单， 区间查询然后区间置0就可以。
第一种操作， 首先查询[x, n]内一共有多少个盒子是空的， 如果全是满的， 直接输出Can not put any one. 设num为空盒子的数量， 那么显然y = min(y, num)。
接下来的问题就是找左右端点， 我是用的二分寻找左右端点， 具体的细节可以看代码。
#include <iostream>
#include <vector>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <string>
#include <queue>
#include <stack>
#include <bitset>
using namespace std;
#define pb(x) push_back(x)
#define ll long long
#define mk(x, y) make_pair(x, y)
#define lson l, m, rt<<1
#define mem(a) memset(a, 0, sizeof(a))
#define rson m+1, r, rt<<1|1
#define mem1(a) memset(a, -1, sizeof(a))
#define mem2(a) memset(a, 0x3f, sizeof(a))
#define rep(i, n, a) for(int i = a; i<n; i++)
#define fi first
#define se second
typedef pair<int, int> pll;
const double PI = acos(-1.0);
const double eps = 1e-;
const int mod = 1e9+;
const int inf = ;
const int dir[][] = { {-, }, {, }, {, -}, {, } };
const int maxn = 5e4+;
int sum[maxn<<], cnt[maxn<<], n;
void pushUp(int rt) {
sum[rt] = sum[rt<<]+sum[rt<<|];
}
void pushDown(int rt, int m) {
if(~cnt[rt]) {
cnt[rt<<] = cnt[rt<<|] = cnt[rt];
sum[rt<<] = cnt[rt]*(m-(m>>));
sum[rt<<|] = cnt[rt]*(m>>);
cnt[rt] = -;
}
}
void update(int L, int R, int l, int r, int rt, int val) {
if(L<=l&&R>=r) {
cnt[rt] = val;
sum[rt] = val*(r-l+);
return ;
}
pushDown(rt, r-l+);
int m = l+r>>;
if(L<=m)
update(L, R, lson, val);
if(R>m)
update(L, R, rson, val);
pushUp(rt);
}
int query(int L, int R, int l, int r, int rt) {
if(L<=l&&R>=r) {
return sum[rt];
}
pushDown(rt, r-l+);
int m = l+r>>, ret = ;
if(L<=m)
ret += query(L, R, lson);
if(R>m)
ret += query(L, R, rson);
return ret;
}
int bin(int l, int r, int val) {
int ans, pos = l;
while(l<=r) {
int m = l+r>>;
if(m-pos+-query(pos, m, , n, )>=val) {
r = m-;
ans = m;
} else {
l = m+;
}
}
return ans;
}
int main()
{
int t, m, x, y, sign;
cin>>t;
while(t--) {
scanf("%d%d", &n, &m);
mem1(cnt);
mem(sum);
while(m--) {
scanf("%d%d%d", &sign, &x, &y);
x++;
if(sign == ) {
int num = query(x, n, , n, );
if(num == n-x+) {
puts("Can not put any one.");
continue;
}
y = min(y, n-x+-num);
int l = bin(x, n, );
int r = bin(l, n, y);
printf("%d %d\n", l-, r-);
update(l, r, , n, , );
} else {
y++;
printf("%d\n", query(x, y, , n, ));
update(x, y, , n, , );
}
}
cout<<endl;
}
return ;
}