Gym102452I - Incoming Asteroids

#题面

#题目描述

The International Coalition to Prevent Catastrophes (ICPC) recently discovered several small asteroids in a nearby galaxy. If these asteroids hit the Earth, it will lead to a terrible disaster. So it is important for the ICPC to fully study the orbit trajectories of these asteroids. The ICPC consists of many member states, and due to the difference in development, they may have different goals in the study.

Orbits of Comet Kohoutek and the Earth. Public domain.

The ICPC has marked $n$ astronomy observatories around the world, labelled by $1,2,\cdots,n$. According to the ICPC’s prediction, there will be $m$ events of two types, detailed below:

• 「1 y k q[1…k]」 ($1\leq y\leq 10^6$, $1\leq k\leq 3$, $1\leq q_i\leq n\text{ for } 1 \le i \le k$): A new member of the ICPC joins the study, whose goal is to gather at least $y$ minutes of video of the asteroids in total. The new member has $k$ cameras and is going to install exactly one camera in each astronomy observatory labelled by $q_1,q_2,\dots,q_k$. It is guaranteed that these $k$ integers $q_1,q_2,\dots,q_k$ are pairwise distinct. Let $p$ be the number of events of type 1 before this event, then this member is assigned the ID of $p+1$.
• 「2 x y」 ($1\leq x\leq n$, $1\leq y\leq 10^6$): Each the camera installed at the $x$-th astronomy observatory successfully gathers $y$ minutes of asteroid video. You need to report the number of ICPC members whose goals are just reached after this event, and the IDs of these members. Note that you shouldn’t count the members whose goals have already been reached before this event.

You are an employee at the ICPC and your leader asks you to write a program to simulate these events, so that the ICPC may make appropriate preparations for the study.

#输入格式

The input contains only a single case.

The first line of the input contains two integers $n$ and $m$ ($1 \leq n,m \leq 2\cdot 10^5$), denoting the number of astronomy observatories and the number of events. Each of the next $m$ lines describes an event in formats described in the statement above, except that some parameters are encrypted in order to enforce online processing.

Let $last$ be the number of members you report in the last event of the second type. Note that $last=0$ before the first event of the second type is processed. For events of the first type, $y$ and $q_i \ (1\le i \le k)$ are encrypted. The actual values of $y$ and $q_i$ are $y\oplus last$ and $q_i\oplus last$. For events of the second type, $x,y$ are encrypted. The actual values of $x,y$ are $x\oplus last$, $y \oplus last$. In the expressions above, the symbol 「$\oplus$」 denotes the bitwise exclusive-or operation. Also note that the constraints described in the statement above apply to the corresponding parameters only after decryption, the encrypted values are not subject to those constraints.

#输出格式

For each event of the second type, print a single line. In this line, print an integer $cnt$ first, denoting the number of ICPC members whose goals are just reached after this event. Then print $cnt$ ascending integers, denoting the IDs of these ICPC members.

#输入输出样例

样例输入 #1

3 5
1 5 3 1 2 3
2 2 1
1 2 2 1 2
2 3 1
2 1 3

样例输出 #1

0
0
2 1 2

#思路

对于每一个观测者可以设置提醒闹钟，在 $\lceil \frac{y}{k} \rceil$ 后检查是否满足结束条件。然后对于每一个观测站使用 std::set 或者 std::priority_queue 维护其闹钟序列即可。

#代码

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

#include <iostream>
#include <cmath>
#include <functional>
#include <queue>
#include <set>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2e5 + 5;

int n, m, lst, cnt;
long long a[N], b[N];
std::priority_queue<
    std::pair<long long, int>,
    std::vector<std::pair<long long, int>>,
    std::greater<std::pair<long long, int>>>
    q[N];
std::vector<int> ids[N];

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    while (m--) {
        int op;

        cin >> op;

        if (op == 1) {
            int y, k;

            cin >> y >> k;

            a[++cnt] = y ^= lst;
            int v = std::ceil(static_cast<double>(y) / k);

            for (int i = 1, x; i <= k; i++) {
                cin >> x;

                ids[cnt].emplace_back(x ^= lst);
                a[cnt] += b[x];
                q[x].emplace(b[x] + v, cnt);
            }
        } else {  // op == 2
            int x, y;
            std::set<int> ans;

            cin >> x >> y;

            b[x ^= lst] += y ^= lst;

            while (!q[x].empty() && q[x].top().first <= b[x]) {
                int id = q[x].top().second;
                q[x].pop();

                if (!a[id]) continue;

                long long rest = a[id];
                for (int p : ids[id]) {
                    rest -= b[p];
                }

                if (rest <= 0) {
                    ans.emplace(id);
                    a[id] = 0;
                } else {
                    int v = std::ceil(static_cast<double>(rest) / ids[id].size());

                    for (int p : ids[id]) {
                        q[p].emplace(b[p] + v, id);
                    }
                }
            }

            cout << (lst = ans.size());
            for (int x : ans) cout << ' ' << x;
            cout << endl;
        }
    }

    return 0;
}

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 <cmath>
#include <functional>
#include <set>
#include <utility>
#include <vector>

using std::cin;
using std::cout;
const char endl = '\n';

const int N = 2e5 + 5;

int n, m, lst, cnt;
long long a[N], b[N];
std::set<std::pair<long long, int>> q[N];
std::vector<std::pair<int, std::set<std::pair<long long, int>>::iterator>> ids[N];

int main() {
    std::ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;

    while (m--) {
        int op;

        cin >> op;

        if (op == 1) {
            int y, k;

            cin >> y >> k;

            a[++cnt] = y ^= lst;
            int v = std::ceil(static_cast<double>(y) / k);

            for (int i = 1, x; i <= k; i++) {
                cin >> x;

                x ^= lst;
                ids[cnt].emplace_back(x, q[x].emplace(b[x] + v, cnt).first);
                a[cnt] += b[x];
            }
        } else {  // op == 2
            int x, y;
            std::set<int> ans;

            cin >> x >> y;

            b[x ^= lst] += y ^= lst;

            while (!q[x].empty() && q[x].begin()->first <= b[x]) {
                int id = q[x].begin()->second;

                long long rest = a[id];
                for (auto o : ids[id]) {
                    rest -= b[o.first];
                    q[o.first].erase(o.second);
                }

                if (rest <= 0) {
                    ans.emplace(id);
                    ids[id].clear();
                } else {
                    int v = std::ceil(static_cast<double>(rest) / ids[id].size());

                    for (auto &o : ids[id]) {
                        o.second = q[o.first].emplace(b[o.first] + v, id).first;
                    }
                }
            }

            cout << (lst = ans.size());
            for (int x : ans) cout << ' ' << x;
            cout << endl;
        }
    }

    return 0;
}