Vases and Flowers

​ Alice is so popular that she can receive many flowers everyday. She has N vases numbered from 0 to N-1. When she receive some flowers, she will try to put them in the vases, one flower in one vase. She randomly choose the vase A and try to put a flower in the vase. If the there is no flower in the vase, she will put a flower in it, otherwise she skip this vase. And then she will try put in the vase A+1, A+2, …, N-1, until there is no flower left or she has tried the vase N-1. The left flowers will be discarded. Of course, sometimes she will clean the vases. Because there are too many vases, she randomly choose to clean the vases numbered from A to B(A <= B). The flowers in the cleaned vases will be discarded.

思路

此题一看，区间查询+区间修改，好的线段树，先看看更简单的操作2，可以确定我们要维护一个区间和，表示花的数量，然后讲区间置$0$。然后是操作1，从A位置开始插花，插完B朵或者插到插满为止，如果A已经插了花我们肯定要往后找可以插的位置，如果到最后一个花瓶都没有插下去就输出”Can not put any one”。我们需要解决的问题就是找到插的第一朵花的位置，我们可以先查询$[A, N]$的区间和，看是否可以插，同样我们可以利用区间和和空花瓶的数量关系，通过二分找到第一朵花的位置和最后一朵花的位置。最后区间置$1$。

tips: 板子是$[1, n]$，题目是$[0, n - 1]$，注意一下坐标映射，还有输出格式

code

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
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
#include<bits/stdc++.h>
using namespace std;

const int N = 5e4+10;;

struct SegTree {
    int l, r;
    int sum, lazy;
}tr[N << 2];

int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9')
    {
        if(ch == '-') f = -1;
        ch = getchar();
    }   
    while(ch >= '0' && ch <= '9')
    {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}

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

void pushdown(int u)
{
    if(tr[u].lazy != -1)
    {
        tr[u << 1].lazy = tr[u << 1 | 1].lazy = tr[u].lazy;
        tr[u << 1].sum = (tr[u << 1].r - tr[u << 1].l + 1) * tr[u].lazy;
        tr[u << 1 | 1].sum = (tr[u << 1 | 1].r - tr[u << 1 | 1].l + 1) * tr[u].lazy;
        tr[u].lazy = -1;   
    }
}

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

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

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

int findPos(int l,int r,int c){
    while(l < r) 
    {
        int mid = (l + r) >> 1;
        int len = mid - l + 1;
        int sum = query(1, l, mid);
        if(len - sum >= c) r = mid;
        else
        {
            l = mid + 1;
            c -= (len - sum);
        }
    }
    return l;
}

void solve()
{
    int n = read(), m = read();
    build(1, 1, n);int opt, a, b;
    for(int i = 0; i < m; i ++ )
    {
        
        opt = read(), a = read(), b = read();
        if(opt == 1) 
        {
            a++;
            int sum = query(1, a, n);
            if(sum == n - a + 1)  printf("Can not put any one.\n");
            else if(sum >= n - a + 1 - b){
                int l = findPos(a, n, 1);
                int r = findPos(a, n, n - a + 1 - sum);
                modify(1, l, r, 1);
                printf("%d %d\n", l - 1, r - 1);
            }
            else 
            {   
                int l = findPos(a, n, 1);
                int r =  findPos(a, n, b);
                modify(1, l, r, 1);
                printf("%d %d\n", l - 1, r - 1);
            }
        } 
        else 
        {
            a++, b++;
            int res = query(1, a, b);
            modify(1, a, b, 0);
            printf("%d\n", res);
        }
    }
    printf("\n");
}

int main()
{
    int T;
    T = read();
    while(T -- ) solve();
    return 0;
}