清点人数

题目描述

$n$ 节车厢初始没人。处理 $k$ 个事件：B m p 表示第 $m$ 节上车 $p$ 人，C m p 表示下车 $p$ 人，A m 询问前 $m$ 节车厢总人数。每次询问的 $m$ 严格递增，主任只往前走不回头。数据范围 $1\le n,k\le 5\times10^5$ 。

思路

用 pos 记录主任已走到的车厢，total 维护前 pos 节人数和。A m 时把 pos 一路推进到 $m$ 并累加经过车厢的净人数；B/C 若 $m\le pos$ 直接改 total，否则先记在对应车厢。指针只前进，总推进次数不超过 $n$ ，时间复杂度 $O(n+k)$ 。

参考代码

Python 版：

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#!/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-09-30 16:54
# update_at: 2026-09-30 16:54

import sys

A = b'A'  # 事件类型：A 询问 / B 上车 / C 下车
B = b'B'


def walk_sweep(events: list[tuple[bytes, int, int]], n: int) -> list[str]:
    """指针扫描所有事件：主任只向前走，返回每次 A 的前缀和答案。

    询问的 m 单调不减，所以主任的位置 pos 只增不减；把答案拆成两半维护——
    已走过的前缀和存 total，还没走到的车厢净人数存 cnt，两者互不重叠。
    """
    cnt = [0] * (n + 1)  # 各车厢净人数（仅对未走过的位置有意义）
    pos = 0              # 主任当前位置：前 pos 节车厢已被点过
    total = 0            # 前 pos 节车厢的人数和
    out: list[str] = []

    for op, m, p in events:
        if op == A:
            while pos < m:  # 一站一站往前走，累计新经过的车厢
                pos += 1
                total += cnt[pos]
            out.append(str(total))
        else:
            delta = p if op == B else -p
            if m <= pos:  # 车厢已被走过：直接修正前缀和
                total += delta
            else:         # 还没走到：先记在车厢上，等指针经过时再累加
                cnt[m] += delta
    return out


def solve() -> None:
    data = iter(sys.stdin.buffer.read().split())
    n = int(next(data))
    k = int(next(data))

    events: list[tuple[bytes, int, int]] = []
    for _ in range(k):
        op = next(data)
        m = int(next(data))
        p = int(next(data)) if op != A else 0  # A 只有一个 m
        events.append((op, m, p))

    print('\n'.join(walk_sweep(events, n)))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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-06 00:42
 * update_at: 2026-10-06 00:42
 */

#include <iostream>
#include <cstdio>
using namespace std;

typedef long long ll;

const int MAXN = 500005; // 车厢数上限

ll cnt[MAXN]; // 未走过车厢的净人数

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

    int n, k;
    cin >> n >> k;

    char op;
    int m, p;
    int pos = 0;    // 主任已走到第几节车厢
    ll total = 0;   // 前 pos 节车厢的人数和
    for (int i = 0; i < k; ++i) {
        cin >> op >> m;
        if (op == 'A') {
            // 询问：把指针一站一站推进到 m，累计新经过车厢的人数
            while (pos < m) {
                ++pos;
                total += cnt[pos];
            }
            cout << total << '\n';
        } else {
            cin >> p;
            ll delta = (op == 'B') ? p : -p;
            if (m <= pos) {
                // 车厢已被走过：直接修正已统计的前缀和
                total += delta;
            } else {
                // 还没走到：先记在车厢上，等指针经过时再累加
                cnt[m] += delta;
            }
        }
    }
    return 0;
}

目录

题目描述

思路

参考代码