Day1. Food Court

又是做了很久，有几个关键点没有想出来。

第一个关键点是，如何处理从队伍头部移走人数？

第二个关键点，现在知道每一个查询对应的是第几个元素，也知道每次操作加入的颜色和数量，怎么处理查询？

Code

实现的时候，用了 AtCoder Library 的线段树

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
#include <iostream>
#include <vector>
using i64         = long long;
constexpr i64 inf = 1e18;
constexpr int N   = 3e5 + 5;
using namespace atcoder;

int n, m, q;

//  EXPLAIN: seg1 for maintaining the total people come into queue
//  EXPLAIN: seg3 for maintain out/in-source customer at time axis along Restaurant axis.
struct S {
    i64 max;
};
struct F1 {
    i64 add;
};
S op1(S a, S b) { return {std::max(a.max, b.max)}; }
S e1() { return {0}; }
S mp1(F1 f, S s) { return {s.max + f.add}; }
F1 cp1(F1 a, F1 b) { return {a.add + b.add}; }
F1 id1() { return {0}; }
lazy_segtree<S, op1, e1, F1, mp1, cp1, id1> seg1(N), seg3(N);

//  EXPLAIN: seg2 for maintain current # of people in queue
struct F2 {
    i64 add, max;
};
S mp2(F2 f, S s) { return {std::max(f.max, s.max + f.add)}; }
F2 cp2(F2 a, F2 b) { return {a.add + b.add, std::max(b.max + a.add, a.max)}; }
F2 id2() { return {0, 0}; }
lazy_segtree<S, op1, e1, F2, mp2, cp2, id2> seg2(N);

//  EXPLAIN: Scan line
struct Segment {
    i64 timing, delta; //  INFO: this is for scan line.
};
i64 color[N];
int mark[N];
i64 ans[N];
std::vector<Segment> scan[N], query[N];

int main() {
    std::cin >> n >> m >> q;

    for (int i = 1, op; i <= q; i++) {
        std::cin >> op;
        if (op == 1) {
            int l, r;
            i64 k;
            std::cin >> l >> r >> color[i] >> k;
            seg1.apply(l, r + 1, {k});
            seg2.apply(l, r + 1, {k, -inf});
            scan[l].push_back({i, k}), scan[r + 1].push_back({i, -k});
        } else if (op == 2) {
            int l, r;
            i64 k;
            std::cin >> l >> r >> k;
            seg2.apply(l, r + 1, {-k, 0});
        } else {
            i64 a, b;
            std::cin >> a >> b;
            mark[i] = true;
            query[a].push_back({i, b + seg1.get(a).max - seg2.get(a).max});
        }
    }

    for (int i = 1; i <= n; i++) {
        for (auto [T, D] : scan[i]) seg3.apply(T, q + 1, {D});
        for (auto [T, req] : query[i]) {
            // std::cerr << " query[" << i << "][" << T << "] = " << req << '\n';
            ans[T] = seg3.max_right(0, [&](S s) { return s.max < req; });
        }
    }

    for (int i = 1; i <= q; i++) {
        if (!mark[i]) continue;
        //      std::cerr << "ans[" << i << "] = " << ans[i] << '\n';
        std::cout << (ans[i] > i ? 0 : color[ans[i]]) << '\n';
    }
}