「Meteors」流星

形式化题目

环上有 $M$ 个位置，第 $j$ 个位置属于国家 $A_j$ （国家编号 $1 \sim N$ ，一个国家可以拥有多个位置）。

接下来有 $K$ 场陨石雨，第 $i$ 场给环上从 $L_i$ 顺时针到 $R_i$ 的每个位置加 $A_i$ ；若 $L_i > R_i$ 则该区间是 $[L_i, M] \cup [1, R_i]$ 。

记 $\text{cnt}(c, t)$ 为国家 $c$ 在前 $t$ 场雨后收到的总量。对每个国家 $c$ ，求

\min \{\, t : \text{cnt}(c, t) \geqslant P_c \,\}

若到第 $K$ 场结束仍不足则输出 NIE。 $1 \leqslant N, M, K \leqslant 3 \times 10^5$ ， $1 \leqslant P_c \leqslant 10^9$ ， $1 \leqslant A_i < 10^9$ 。

以样例为例，三个国家分别拥有 $1$ 段、 $1$ 段、 $2$ 段，逐场累加后：

累计场次	国家 1（段 1,4）	国家 2（段 3）	国家 3（段 2,5）	需求
1	8	0	8	10 / 5 / 7
2	9	1	9
3	11	3	11
答案	3	NIE	1

国家 2 只有第 3 段，三场雨里只有第 2 场覆盖到它，共 3 < 5，所以是 NIE。

正解

思路

为什么不逐国二分。 对固定的国家 $c$ ，“前 $t$ 场够不够"关于 $t$ 单调（雨量都是正数），所以可以二分。但直接二分会把同一场雨反复重算：单国判定要 $O(t \log M)$ ，总复杂度 $O(NK\log M) \approx 10^{16}$ ，不可行。真正的浪费不在"二分了几次”，而在同一场雨被每个国家各算一遍。

关键观察：同一轮里，所有国家的答案区间互不相交。

整体二分让所有国家同时二分：每个国家维护一个答案区间 $[\text{lo}_c, \text{hi}_c]$ ，每轮取中点 $\text{mid}_c$ 判定，然后区间折半。由于所有区间每轮长度都减半，同一轮里它们的深度完全相同，于是这些区间把 $[1, K+1]$ 切成互不相交的若干段：

[\text{lo}_c, \text{hi}_c] \cap [\text{lo}_{c'}, \text{hi}_{c'}] = \varnothing \quad (c \neq c')

这一步的意义是：每场雨在本轮只归属一个节点，不同节点的区间加互不干扰。那么"每个节点各做一次区间加"就可以拼接成一个数组任务，一次性交给 numpy。

text

1
2
3环上位置:  ... 每个位置属于某个国家
雨 i:      归属节点 v_i = 满足 lo_v <= i <= hi_v 的那个 v
本轮:      节点 v 内，把 i <= mid_v 的雨做区间加，再查 v 里各国的太空站

把区间加转成差分事件。 区间 $[a, b]$ 加 $v$ 等价于" $a$ 处 $+v$ 、 $b+1$ 处 $-v$ "（ $b = M$ 时不需要撤销事件）。跨环的 $[L, M] \cup [1, R]$ 拆成两段，各自生成差分事件，共用同一个节点。

把所有事件按 (节点, 位置) 排序，节点内的位置前缀和就是每个位置收到的雨量。用组合键 节点 * (M+1) + 位置 排序，就能让"先按节点分组、再按位置升序"一次 argsort 完成。

节点内前缀和怎么算。 全局 cumsum 之后，把每个节点块首之前的累计量减掉即可。块首位置用 np.searchsorted(ev_node, ev_node, side="left") 一次求出——同一节点的事件在排序后连续，所以这个 searchsorted 就是"每个元素所属块的起点"。

查询与归并。 每个太空站是一个查询 (节点, 位置)，二分找它前面最后一个不晚于它的事件，该处的前缀和就是它收到的雨量。最后用 np.bincount(qcid, weights=…) 把同一国家所有太空站加起来。

判定与转移照标准整体二分： $S \geqslant \text{res}_c$ 则 hi = mid，否则 res -= S、lo = mid + 1。残留需求 res 保证了右半段的判定仍等价于"前 $t$ 场总量 $\geqslant P_c$ "。lo 收敛到 $K+1$ 即为 NIE。

代码

cpp

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
141
142
143
144
145
146
147
148
149/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */
// 陨石雨：整体二分，把同一轮里所有国家的区间一起处理，用排序 + 节点内前缀和批量算收集量。
#include <cstdio>
#include <vector>
#include <algorithm>

typedef long long ll;

const ll CAP = 2000000000LL; // 单个太空站的收集量上限（远超任何国家的需求 10^9）

struct E3 {
    ll node; // 该事件属于哪个二分节点
    ll pos;  // 位置
    ll delta; // 差分增量
};

bool e3_less(const E3& a, const E3& b) {
    if (a.node != b.node) return a.node < b.node;
    return a.pos < b.pos;
}

ll n, m, k;
std::vector<ll> own, need, rl, rr, ra;
std::vector<ll> lo, hi, res;
std::vector<std::vector<ll> > stations; // 每个国家的太空站位置（1 基）

int main() {
    if (scanf("%lld %lld", &n, &m) != 2) return 0; // 空输入安全返回
    own.assign(m + 1, 0);
    for (ll i = 1; i <= m; i++) scanf("%lld", &own[i]);
    need.assign(n + 1, 0);
    for (ll i = 1; i <= n; i++) scanf("%lld", &need[i]);
    scanf("%lld", &k);
    rl.assign(k + 1, 0);
    rr.assign(k + 1, 0);
    ra.assign(k + 1, 0);
    for (ll i = 1; i <= k; i++) scanf("%lld %lld %lld", &rl[i], &rr[i], &ra[i]);

    stations.assign(n + 1, std::vector<ll>());
    for (ll i = 1; i <= m; i++) stations[own[i]].push_back(i);

    lo.assign(n + 1, 1);
    hi.assign(n + 1, k + 1); // hi = k+1 表示到 K 场雨结束仍不够
    res.assign(n + 1, 0);
    for (ll i = 1; i <= n; i++) res[i] = need[i];

    std::vector<ll> act;
    for (ll i = 1; i <= n; i++) {
        if (lo[i] < hi[i]) act.push_back(i);
    }

    std::vector<ll> keys, uniq, node_lo, node_hi, node_mid, nidx;
    std::vector<E3> ev;
    std::vector<ll> cum;

    while (!act.empty()) {
        keys.clear();
        for (size_t t = 0; t < act.size(); t++) {
            ll c = act[t];
            keys.push_back(lo[c] * (k + 2) + hi[c]);
        }
        uniq = keys;
        std::sort(uniq.begin(), uniq.end());
        uniq.erase(std::unique(uniq.begin(), uniq.end()), uniq.end());

        ll nn = (ll)uniq.size();
        node_lo.assign(nn, 0);
        node_hi.assign(nn, 0);
        node_mid.assign(nn, 0);
        for (ll i = 0; i < nn; i++) {
            node_lo[i] = uniq[i] / (k + 2);
            node_hi[i] = uniq[i] % (k + 2);
            node_mid[i] = (node_lo[i] + node_hi[i]) >> 1;
        }
        nidx.assign(act.size(), 0);
        for (size_t t = 0; t < act.size(); t++) {
            nidx[t] = std::lower_bound(uniq.begin(), uniq.end(), keys[t]) - uniq.begin();
        }

        // 每场雨落在哪个节点；只保留落在该节点左半边（编号 ≤ mid）的雨
        ev.clear();
        for (ll j = 1; j <= k; j++) {
            ll idx = std::upper_bound(node_lo.begin(), node_lo.end(), j) - node_lo.begin() - 1;
            if (idx < 0 || j > node_mid[idx]) continue;
            ll left = rl[j], right = rr[j], val = ra[j];
            E3 e;
            e.node = idx; e.pos = left; e.delta = val; ev.push_back(e);
            if (left > right) { // 环形区间跨过 m，拆成 [left, m] 与 [1, right]
                e.node = idx; e.pos = 1; e.delta = val; ev.push_back(e);
            }
            if (right < m) {
                e.node = idx; e.pos = right + 1; e.delta = -val; ev.push_back(e);
            }
        }
        std::sort(ev.begin(), ev.end(), e3_less);
        cum.assign(ev.size(), 0);
        for (size_t i = 0; i < ev.size(); i++) {
            // 累加要按节点清零：同节点内才是前缀和
            cum[i] = ev[i].delta + ((i > 0 && ev[i].node == ev[i - 1].node) ? cum[i - 1] : 0);
        }

        for (size_t t = 0; t < act.size(); t++) {
            ll c = act[t];
            ll nd = nidx[t];
            ll S = 0;
            for (size_t s = 0; s < stations[c].size(); s++) {
                ll p = stations[c][s];
                // 本节点内最后一个不晚于 p 的事件
                ll lo_i = std::lower_bound(ev.begin(), ev.end(), E3{nd, 0, 0}, e3_less) - ev.begin();
                ll pos = lo_i;
                ll len = (ll)ev.size();
                // 同节点内按 pos 二分
                ll a = lo_i, b = len;
                while (a < b) {
                    ll mid = (a + b) >> 1;
                    if (ev[mid].node == nd && ev[mid].pos <= p) a = mid + 1;
                    else b = mid;
                }
                pos = a - 1;
                ll got = (pos >= lo_i && pos < len && ev[pos].node == nd) ? cum[pos] : 0;
                if (got > CAP) got = CAP;
                S += got;
            }
            if (S >= res[c]) {
                hi[c] = node_mid[nd];
            } else {
                res[c] -= S;
                lo[c] = node_mid[nd] + 1;
            }
        }

        act.clear();
        for (ll i = 1; i <= n; i++) {
            if (lo[i] < hi[i]) act.push_back(i);
        }
    }

    for (ll i = 1; i <= n; i++) {
        if (lo[i] == k + 1) printf("NIE\n");
        else printf("%lld\n", lo[i]);
    }
    return 0;
}

python

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#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 19:14
# update_at: 2026-10-01 19:45

import sys

import numpy as np

NIE = "NIE"  # 到第 K 场雨结束仍然凑不够的国家输出它
CAP = 2 * 10**9  # 单个太空站的收集量上限：已经远超任何国家的需求 10^9，再大也不会改变判定


def collect(
    lo: np.ndarray,
    hi: np.ndarray,
    own: np.ndarray,
    l: np.ndarray,
    r: np.ndarray,
    a: np.ndarray,
    k: int,
    m: int,
) -> tuple[np.ndarray, np.ndarray, np.ndarray]:
    """一轮整体二分：算出每个活跃国家在左边那半场雨里能收到多少样本量。

    活跃国家当前的答案区间 [lo, hi] 就是一个"节点"。同一轮里所有国家的区间深度相同，
    所以这些区间把 [1, k+1] 切成互不相交的几段，一场雨只属于唯一节点，可以一起算。
    返回 (act, mid, S)：act 是活跃国家下标，mid 是各自节点的二分中点，S 是收集量。
    """
    act = np.nonzero(lo < hi)[0]
    # 节点用 lo*(k+2)+hi 编码；unique 后按 lo 升序，正好可以二分定位一场雨属于哪个节点
    uniq, inv = np.unique(lo[act] * (k + 2) + hi[act], return_inverse=True)
    node_lo, node_hi = uniq // (k + 2), uniq % (k + 2)
    node_mid = (node_lo + node_hi) >> 1
    mid = node_mid[inv]

    op = np.arange(1, k + 1)  # 雨的编号，1 基
    node_of = np.searchsorted(node_lo, op, side="right") - 1  # 每场雨落在哪个节点
    # 已经定完答案的国家会让区间出现空洞，落在空洞里的雨不属于任何节点（node_of = -1）
    keep = (node_of >= 0) & (op <= node_mid[node_of])  # 只保留每条二分路径的左半边
    op, node_of = op[keep], node_of[keep]
    left, right, val = l[op - 1], r[op - 1], a[op - 1]
    wrap = left > right  # 环形区间跨过 m，拆成 [left, m] 和 [1, right]

    # 区间加 → 差分：left 处 +val；跨环时在 1 处再 +val；right 之后 -val
    tail = right < m
    ev_node = np.concatenate([node_of, node_of[wrap], node_of[tail]])
    ev_pos = np.concatenate([left, np.ones(int(wrap.sum()), np.int64), right[tail] + 1])
    ev_del = np.concatenate([val, val[wrap], -val[tail]])

    key = ev_node * (m + 1) + ev_pos  # 同节点内按位置升序
    order = np.argsort(key, kind="stable")
    ev_node, ev_key, ev_del = ev_node[order], key[order], ev_del[order]
    cum = np.cumsum(ev_del)
    # 累加要按节点清零：减去"该节点块首之前"的累计，就是节点内的前缀和
    head = np.searchsorted(ev_node, ev_node, side="left")
    cum_in = cum - (cum[head] - ev_del[head])

    # 只问活跃国家的太空站落在哪
    live = np.zeros(lo.size, bool)
    live[act] = True
    own0 = own - 1
    station = live[own0]
    qpos = np.nonzero(station)[0] + 1
    qcid = own0[station]
    node_of_country = np.zeros(lo.size, np.int64)
    node_of_country[act] = inv
    qnode = node_of_country[qcid]

    qkey = qnode * (m + 1) + qpos
    j = np.searchsorted(ev_key, qkey, side="right") - 1  # 节点内最后一个不晚于该位置的事件
    hit = j >= 0  # 前面没有任何事件时不能取 cum_in[0] 硬凑
    j = np.where(hit, j, 0)
    found = hit & (ev_node[j] == qnode)  # 该事件确实属于本节点
    got = np.where(found, cum_in[j], 0)
    # 一个国家最多有 m 个太空站，逐个累加会到 10^19 撑爆 int64；先按 CAP 截断，
    # 由于任何国家的需求都不超过 10^9 < CAP，截断不会改变 "S >= res" 的结论。
    got = np.minimum(got, CAP)
    # 同一国家有多个太空站：按国家求和（总量 ≤ 3×10^5 * 2×10^9 < 2^53，float64 精确）
    total = np.bincount(qcid, weights=got.astype(np.float64), minlength=lo.size)
    return act, mid, total[act].astype(np.int64)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)                         # 国家数
    m = next(data)                         # 轨道段数
    own = np.array([next(data) for _ in range(m)], dtype=np.int64)      # 第 i 段轨道属于哪个国家
    need = np.array([next(data) for _ in range(n)], dtype=np.int64)     # 第 i 个国家想收集的样本量
    k = next(data)                         # 雨的场数
    rain = np.array([[next(data), next(data), next(data)] for _ in range(k)], dtype=np.int64)  # 每场雨 (L, R, A)
    left, right, amount = rain[:, 0], rain[:, 1], rain[:, 2]

    lo = np.ones(n, np.int64)              # 答案区间 [lo, hi]
    hi = np.full(n, k + 1, np.int64)       # hi = k+1 表示到 K 场雨结束仍不够
    res = need.copy()                      # 还没被满足的需求，雨量按二分逐段扣
    act = np.nonzero(lo < hi)[0]
    while act.size:
        act, mid, S = collect(lo, hi, own, left, right, amount, k, m)
        ok = S >= res[act]                 # 够：答案在左半边；不够：扣掉雨量去右半边
        hi[act[ok]] = mid[ok]
        res[act[~ok]] -= S[~ok]
        lo[act[~ok]] = mid[~ok] + 1
        act = np.nonzero(lo < hi)[0]

    print("\n".join(NIE if v == k + 1 else str(int(v)) for v in lo))


if __name__ == "__main__":
    solve()

复杂度

每轮 $O((N + K + M)\log(N + K + M))$ （瓶颈是排序），共 $\lceil \log_2(K+1) \rceil \approx 19$ 轮，总时间

O\big((N + K + M)\log K \log(N + K + M)\big)

空间 $O(N + K + M)$ 。与标准整体二分同阶；多出的那一个 $\log$ 来自排序，但 numpy 的排序常数极小，实测最坏一组（ $N = 233410$ ， $M = K = 3 \times 10^5$ ）0.91 s、248 MB。

实现里的两个坑

坑 1：空洞节点。 一旦有国家先定出答案，节点区间就出现空洞。落在空洞里的雨会被 searchsorted 定位到 $-1$ ——而 numpy 里 -1 是合法索引（取最后一个元素），雨会被静默加到别的节点上。必须先过滤 node_of >= 0。

坑 2：数值溢出。 位置前缀和可达 $\sum A_i \approx 3 \times 10^{14}$ （int64 安全），但一个国家最多有 $3 \times 10^5$ 个太空站，逐站相加到 $10^{19}$ 会撑爆 int64，float64 也超过 $2^{53}$ 失去整数精度（实测 astype(np.int64) 直接抛警告并给出垃圾值）。

处理方式是按需求上限截断：任何国家的需求 $P_c \leqslant 10^9$ ，所以对每个太空站的雨量取 min(got, 2*10**9)。截断后单国总和 $\leqslant 3 \times 10^5 \times 2 \times 10^9 = 6 \times 10^{14} < 2^{53}$ ，float64 精确；而 res <= 10^9 < 2*10**9，所以 S >= res 的判定完全不变。

总结

整体二分的教学版本常写成递归：solve(国家集合, 雨的区间[l, r])，每层把 [l, mid] 的雨加进树状数组、判定、再回滚。本题换了一个视角——既然同一轮里所有节点互不相交，就把递归的每一层摊平成一个大数组任务，用一次排序 + 一次前缀和 + 一次二分代替树状数组。这是把 $O((N+M+K)\log K\log M)$ 的分治在 Python 里落地的关键：算法不变，只是把"逐元素操作"改写成"整段向量操作"。

要看懂这份代码，只需要抓住三句话：节点是答案区间、雨按节点归属、节点内做一次前缀和。其余全是 numpy 的表达技巧。

图示解析

下图给出"每轮摊平"的数据流：所有雨按所属节点被分成互不相交的几组，各组内部独立做区间加，再与本国太空站汇合。

flowchart TD
    S["本轮活跃国家<br/>各自的答案区间 (lo, hi)"] --> U["按区间去重成节点<br/>np.unique"]
    U --> A["每场雨 i 定位到唯一节点<br/>searchsorted(node_lo, i)"]
    A --> K{"i <= mid(node) ?"}
    K -->|否| D["丢弃（属于右半段）"]
    K -->|是| E["生成差分事件<br/>(节点, 位置, ±A)"]
    E --> F["拼接各国太空站查询<br/>(节点, 位置)"]
    F --> G["按 节点*(M+1)+位置 排序"]
    G --> H["节点内位置前缀和<br/>= 每个位置的雨量"]
    H --> I["bincount 按国家汇总"]
    I --> J{"S >= res ?"}
    J -->|是| L["hi = mid"]
    J -->|否| R["res -= S, lo = mid + 1"]
    L --> N["lo == hi 则定答案<br/>lo == K+1 则 NIE"]
    R --> N

要点有三：（1） 节点去重后，雨到节点的映射是一次 searchsorted，不是循环；（2） 节点*(M+1)+位置 这个组合键让"按节点分组 + 组内按位置排序"合并成一次排序；（3） 组内前缀和靠"减去块首之前的累计量"实现，searchsorted 一次性求出所有块首，因此整个流程没有逐元素的 Python 循环。

「Meteors」 流星

目录

形式化题目

正解

思路

代码

复杂度

实现里的两个坑

总结

图示解析