欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

HDU 4614 Vases and Flowers (线段树+成段更新+找位置)

程序员文章站 2022-05-11 19:33:54
...

题意:有N个花瓶(标号为0~ N-1)。操作1:当她收到F朵花时,她会随机的选择一个瓶子A,从它开始遍历A,A+1, A+2, …, N-1号瓶子,遇到空瓶子就放一朵花进去,直到花朵放完或没有瓶子,剩下的花将被丢弃,输出放的起点和终点。操作2:清理标号从A到B的花瓶(A <= B),花瓶里的花会被丢弃,输出丢弃的花数量。

题解:线段树+成段更新+找位置
我们用1表示空瓶子,0表示放了花。
操作2很好做,就是区间查询,再用区间大小减去空瓶子数量,就是花的数量。然后进行区间更新。

对于操作1,由于我们要找到从A~N-1中第一个空瓶子,我们可以这样做:
先找到0~A-1中空瓶子的数量cnt。
再找到空瓶子数量等于cnt+1的那一个点,以及等于cnt+F的一个点,他们就是起点和终点。注意空瓶子可能不够放F朵花。

还有就是懒惰标记那,有置1、置0两种操作。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;
//成段更新
const int MAXN = 5e4 + 5;
int sum[MAXN << 2], add[MAXN << 2];
struct Node {
    int l, r;
    int mid() { return (l + r) >> 1; }
} tree[MAXN << 2];

void PushDown(int rt, int m) {
    if (add[rt]) {
        add[rt << 1] = add[rt];
        add[rt << 1 | 1] = add[rt];
        if (add[rt] == -1) sum[rt << 1] = sum[rt << 1 | 1] = 0;
        else {
            sum[rt << 1] = add[rt] * (m - (m >> 1));
            sum[rt << 1 | 1] = add[rt] * (m >> 1);
        }
        add[rt] = 0;
    }
}
void build(int l, int r, int rt) {
    tree[rt].l = l;
    tree[rt].r = r;
    add[rt] = 0;
    if (l == r) {
        sum[rt] = 1;  //1表示空花瓶
        return;
    }
    int m = tree[rt].mid();
    build(l, m, rt << 1);
    build(m + 1, r, rt << 1 | 1);
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
void update(int c, int l, int r, int rt) {
    if (tree[rt].l == l && r == tree[rt].r) {
        add[rt] = c;
        if (c == -1) sum[rt] = 0;
        else sum[rt] = c * (r - l + 1);
        return;
    }
    if (tree[rt].l == tree[rt].r) return;
    PushDown(rt, tree[rt].r - tree[rt].l + 1);
    int m = tree[rt].mid();
    if (r <= m) update(c, l, r, rt << 1);
    else if (l > m) update(c, l, r, rt << 1 | 1);
    else {
        update(c, l, m, rt << 1);
        update(c, m + 1, r, rt << 1 | 1);
    }
    sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
}
int query(int l, int r, int rt) {
    if (l == tree[rt].l && r == tree[rt].r) {
        return sum[rt];
    }
    PushDown(rt, tree[rt].r - tree[rt].l + 1);
    int m = tree[rt].mid();
    int res = 0;
    if (r <= m) res += query(l, r, rt << 1);
    else if (l > m) res += query(l, r, rt << 1 | 1);
    else {
        res += query(l, m, rt << 1);
        res += query(m + 1, r, rt << 1 | 1);
    }
    return res;
}
int queryPos(int x, int rt) {   //找到第x个1的位置
    if (tree[rt].l == tree[rt].r) return tree[rt].l;
    PushDown(rt, tree[rt].r - tree[rt].l + 1);
    int res = 0;
    if(sum[rt << 1] >= x) res = queryPos(x, rt << 1);
    else res = queryPos(x - sum[rt << 1], rt << 1 | 1);
    return res;
}
int t, n, m, id, x, y;
int main() {
	scanf("%d", &t);
	while (t--) {
		scanf("%d%d", &n, &m);
        build(1, n, 1);
        while (m--) {
            scanf("%d%d%d", &id, &x, &y);
            if (id == 1) {
                int kong = query(x + 1, n, 1);
                if (kong == 0) {
                    puts("Can not put any one.");  //没有空瓶子
                    continue;
                }
                y = min(kong, y);
                int cnt = 0;
                if (x) cnt = query(1, x, 1);  //[1,x-1]空花瓶个数
                int st = queryPos(cnt + 1, 1);
                int ed = queryPos(cnt + y, 1);
                update(-1, st, ed, 1);
                printf("%d %d\n", st - 1, ed - 1);
            }
            else {
                printf("%d\n", y - x + 1 - query(x + 1, y + 1, 1));
                update(1, x + 1, y + 1, 1);
            }
        }
        puts("");
	}
	return 0;
}