Vases And Flowers

Problem Statement

给定n个瓶子，编号从0~n-1，一开始所有瓶子都是空的每个瓶子最多插入一朵花，实现以下两种类型的操作操作 1 from flower : 一共有flower朵花，从from位置开始依次插入花朵，已经有花的瓶子跳过如果一直到最后的瓶子，花也没有用完，就丢弃剩下的花朵返回这次操作插入的首个空瓶的位置和最后空瓶的位置如果从from开始所有瓶子都有花，打印"Can not put any one." 操作 2 left right : 从left位置开始到right位置的瓶子，变回空瓶，返回清理花朵的数量will be discarded.

Solving

将有花的花瓶位置上的值设置为1，没有花的花瓶则为0，一段区间中所有花瓶中花的数量即为这段区间的区间和，对于这个问题我们可以用线段树来维护，上述即为操作二的实现原理，现在我们来详细分析以下操作一如何用线段树进行维护：

显然的，如果给定的位置后面所有的花瓶里都有花，即没有任何空位放置新的花朵，此时直接输出Can not put any one,在程序中体现为Length = (n - 1) - l + 1 == st.querySum(1,l,n-1)

随后我们定义 leftzero 为后面所有花瓶中空花瓶的总数，其中cnt为输入值，表示从from位置往后插cnt朵花，此后有两种情况：

cnt <= leftzero 意为剩余的花瓶足够插下cnt总数的花朵，所以此时的左右边界为 第一次插花的位置与第cnt次插花的位置
cnt > leftzero 意为剩余的花瓶不足以插上总数为cnt的花朵，此时的左右边界为 第一次插花的位置与第leftzero次插花的位置

现在我们的问题就到了如何获取第X次插花位置上，对于[from,n -1]找到第X次插花位置，可以使用二分进行求解：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


    auto check = [&](int l,int r,int x)//二分判断函数
    {
        return (r - l + 1) - st.querySum(1,l,r) >= x;//判断[l,r]的区间内是否至少有x个空花瓶
    };
    auto findright = [&](int l,int x)//找到l向后第X个空花瓶的位置
    {
        int left = l,right = n-1,mid;
        while(left+1<right)
        {
            mid = (left + right) >> 1;
            if(check(l,mid,x)) right = mid;
            else left = mid; 
        }
        if(!check(l,left,x))
        {
            left = right;
        }
        return left;//最后的左边界即为第X个空花瓶的位置
    };

对此得到所有需要的数据，我们只需要在线段树中维护一个区间覆盖的功能，插上和清理的花的区间按区间模拟即可：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79


const int N = 5e4+10;
struct SegTree 
{
	... ...
public:
    // Build Section
    SegTree(const vector<int>& _arr) : arr(_arr) 
    {
        build(1, 0, (int)arr.size()-1);//下标从0开始
    }
	... ... 
};
void solve()
{
    int n,m;
    cin >> n >> m;
    vector<int> arr(n,0);
    SegTree st(arr);
    auto check = [&](int l,int r,int x)//二分判断函数
    {
        return (r - l + 1) - st.querySum(1,l,r) >= x; 
    };
    auto findright = [&](int l,int x)//找到l向后第x个零的位置
    {
        int left = l,right = n-1,mid;
        while(left+1<right)
        {
            mid = (left + right) >> 1;
            if(check(l,mid,x)) right = mid;
            else left = mid; 
        }
        if(!check(l,left,x))
        {
            left = right;
        }
        return left;
    };
    while(m--)
    {
        int op;
        cin >> op;
        if(op==1)
        {   
            int l,cnt;
            int left,right;
            cin >> l >> cnt;
            int len = n - l;
            int occupied = st.querySum(1,l,n-1);
            int leftzero = len - occupied;
            if(len==occupied)
            {
                cout << "Can not put any one." << endl;
                continue;
            }
            if(leftzero <= cnt)
            {
                right = findright(l,leftzero);
                left = findright(l,1);
                cout << left << ' ' << right << endl;
                st.updateSet(1,left,right,1);//插上花的地方区间覆盖为 1
                continue;
            }
            else
            {
                right = findright(l,cnt);
                left = findright(l,1);
                cout << left << ' ' << right << endl;
                st.updateSet(1,left,right,1);
            }
        }
        if(op==2)
        {
            int l,r;
            cin >> l >> r;
            cout << st.querySum(1,l,r) << endl;
            st.updateSet(1,l,r,0);//清理完花，区间的花的数量均修改为0
        }
    }
}