「一本通 4.1 例 3」校门外的树

题目描述

一条长为 $n$ 的道路上有 $m$ 个操作 $(K, l, r)$ ： $K=1$ 表示在 $[l, r]$ 之间种上一种树，每次操作种的树种互不相同，且每个位置都可以重复种树； $K=2$ 表示询问 $[l, r]$ 之间有多少种树。输入第一行为 $n, m$ ，接下来 $m$ 行每行三个整数 $K, l, r$ ；对每个 $K=2$ 的操作输出一行答案。数据范围： $1 \le n, m \le 5 \times 10^4$ ，保证 $l, r > 0$ 。样例：输入 5 4、1 1 3、2 2 5、1 2 4、2 3 5，输出 1、2（先种 $[1,3]$ 后问 $[2,5]$ 得 $1$ ，再种 $[2,4]$ 后问 $[3,5]$ 得 $2$ ）。

思路

每种树只在一段上种一次且无删除，问题就是在线统计与询问区间相交的线段条数；由 $[L,R]$ 与 $[l,r]$ 相交 $\Leftrightarrow L \le r$ 且 $R \ge l$ ，容斥后得答案 $= \#\{L \le r\} - \#\{R < l\}$ ，用两棵分别按左端点、右端点计数的树状数组在线维护即可，复杂度 $O(m \log n)$ 。

参考代码

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

import sys


def add(bit: list[int], i: int) -> None:
    """树状数组 bit 在下标 i 处 +1（下标 = 坐标 + 1）。"""
    while i < len(bit):
        bit[i] += 1
        i += i & -i


def count_le(bit: list[int], i: int) -> int:
    """树状数组 bit 中下标不超过 i 的个数，即坐标不超过 i - 1 的个数。"""
    s = 0
    while i:
        s += bit[i]
        i -= i & -i
    return s


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    road_len, m = next(data), next(data)

    ops: list[tuple[int, int, int]] = []
    for _ in range(m):
        k, l, r = next(data), next(data), next(data)
        ops.append((k, l, r))

    # 下标比坐标大 1（题面保证坐标 > 0），长度覆盖最大坐标 + 1 与向上更新的祖先下标
    size = max(road_len + 1, max(max(l, r) for _, l, r in ops) + 1) + 1
    by_left = [0] * size   # 按左端点计数：下标 i 对应左端点 i - 1
    by_right = [0] * size  # 按右端点计数：下标 i 对应右端点 i - 1

    out: list[str] = []
    for k, l, r in ops:
        if k == 1:  # 种树：这个新种类的段 [l, r] 登记到两棵计数树
            add(by_left, l + 1)
            add(by_right, r + 1)
        else:  # 询问：与 [l, r] 相交的段 = 左端点 <= r 的段 - 右端点 < l 的段
            intersect = count_le(by_left, r + 1) - count_le(by_right, l)
            out.append(str(intersect))

    print('\n'.join(out))


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
53
54
55/**
 * 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
 */

// 每次种的树种类都不同且没有删除，所以"问区间里有多少种树"
// 等价于"问有多少条已插入的线段与询问区间相交"。
// 一条线段 [L, R] 与 [l, r] 相交 <=> L <= r 且 R >= l，
// 用容斥可以化成两个前缀计数：答案 = #{L <= r} - #{R < l}。
// 两棵树状数组分别按左端点、右端点计数即可在线维护。

#include <cstdio>

typedef long long ll;

const int MAXN = 50005;

int n, m;
ll bit_left[MAXN];  // 按左端点计数：插入 [l, r] 时下标 l+1 处 +1（下标 = 坐标+1）
ll bit_right[MAXN]; // 按右端点计数：插入 [l, r] 时下标 r+1 处 +1

// 树状数组在 x 处 +1
void add(ll bit[], int x) {
    for (; x <= n + 1; x += x & (-x))
        bit[x] += 1;
}

// 树状数组求下标 1..x 的前缀和
ll sum(ll bit[], int x) {
    ll s = 0;
    for (; x > 0; x -= x & (-x))
        s += bit[x];
    return s;
}

int main() {
    scanf("%d %d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int k, l, r;
        scanf("%d %d %d", &k, &l, &r);
        if (k == 1) {
            // 种树：这个新种类是一段 [l, r]，登记到两棵计数树
            add(bit_left, l + 1);
            add(bit_right, r + 1);
        } else {
            // 与 [l, r] 相交 = 左端点 <= r 的段 - 右端点 < l 的段
            ll ans = sum(bit_left, r + 1) - sum(bit_right, l);
            printf("%lld\n", ans);
        }
    }
    return 0;
}