[SHOI2009] 会场预约

GitHub跳转原题关系图 Canvas 关系图返回列表

Fenwick 维护当前不相交线段的起点，并按秩寻找可能相交的前驱和后继。

启发题

启发记录： 值域小用 01桶+BIT 按秩查找替代平衡树，kth 的二进制提升是经典倍增模式

OJ: luogu

题目 ID: P2161

难度:普及+/提高-

标签:树状数组有序集合线段倍增桶权值线段树python

日期: 2026-07-16 21:00

题意

插入新区间时删除所有与它相交的旧区间并输出删除数；另支持查询当前区间数。

思路

暴力做法是什么？卡在哪？

对每个 A 操作扫描集合中所有区间判断是否相交，最坏 $O(n^2)$ （ $2\times10^5$ 次操作），必然超时。需要利用集合自身的结构，而不是每次都全量扫。

集合里有什么隐藏结构？

集合中的区间永远两两不交。按起点从小到大排序后，终点也严格递增——否则起点更小的区间终点更大，就会与后面的区间相交。所以整个集合等价于一条"起点有序、终点也单调"的序列，后续所有判断都可以利用这个单调性。

新区间会和哪些旧区间相交？

区间 $[s,e]$ 与 $[s',e']$ 相交当且仅当 $s' \le e$ 且 $e' \ge s$ 。拆成两类看：

起点 $\le s$ 的区间：终点递增，所以只有起点最大的那一条（终点也最大）可能满足 $e' \ge s$ ，检查它一条即可；
起点 $\ge s$ 的区间：只要起点 $\le e$ 就必然相交（它的终点 $\ge$ 自己的起点 $\ge s$ 自动成立），所以从起点最小的开始连续删，直到起点超过 $e$ 。

需要哪些集合操作？

插入、删除、查"起点 $\le x$ 的最大值"（前驱）、查"起点 $\ge x$ 的最小值"（后继）、统计数量。值域只有 $10^5$ ，用 Fenwick 在每个起点保存 0/1（是否存在区间），配合 kth 按秩查找就能模拟有序集合，不需要平衡树。

为什么 kth 可以这样跳跃？

kth(rank) 返回"第 rank 个 1"的位置，是"01 桶放在 Fenwick 上找第 k 个存在元素"的标准写法。它没有用"二分 + 前缀和"，而是用二进制提升直接跳：

Fenwick 节点 tree[x] 保存的是区间 $(x-\operatorname{lowbit}(x), x]$ 内 1 的个数，是线段和，不是单点值；
提升过程中 index 始终是当前步长 step 的倍数，所以 target = index + step 满足 $\operatorname{lowbit}(target) = step$ ，tree[target] 恰好覆盖"从 index 往后的下一整段"；
tree[target] < rank 说明第 rank 个 1 还在这一段之后，可以整段跳过：index = target; rank -= tree[target]；否则第 rank 个 1 就在这段之内，步长减半继续缩小范围；
循环结束时 index 是第 rank 个 1 前面最后一个位置，答案就是 index + 1。

这其实和"二分 + 前缀和比较"完全等价：rank 变量始终维护着 $rank - \text{prefix\_sum}(index)$ ，所以

tree[target] < rank \iff \text{prefix\_sum}(target) < rank

差别只是前缀和被增量维护成 O(1) 的段和，复杂度从 $O(\log^2 C)$ 降到 $O(\log C)$ 。

下面这张表追踪一次 kth(2)：值域为 10，位置 3 和 7 各有一个 1，结果应为 7。

step	target	`tree[target]`（覆盖区间）	比较	动作
8	8	2（ $(0,8]$ 内有 3、7）	$2<2$ 否	不跳
4	4	1（ $(0,4]$ 内有 3）	$1<2$ 是	index=4，rank=1
2	6	0（ $(4,6]$ 内无）	$0<1$ 是	index=6，rank=1
1	7	1（ $(6,7]$ 内有 7）	$1<1$ 否	不跳

返回 index+1=7。行是一次查询的每一轮，列依次是当前步长、试探节点、该节点段内 1 的个数、与剩余 rank 的比较结果和跳转动作。可以看到跳过的每一段都恰好被 tree[target] 完整覆盖，段与段首尾相接、不重不漏。

为什么 step 从不超过 n 的最大 2 的幂开始？

31 - __builtin_clz(n) 是 n 的最高二进制位，1 << 它 就是 $2^{\lfloor\log_2 n\rfloor}$ 。只有从 2 的幂开始并不断减半，才能保证"index 是当前 step 的倍数"这个不变量从第一步就成立；从更大的 2 的幂开始会被 target <= n 挡掉（结果仍对，但没必要），从非 2 的幂开始则 $\operatorname{lowbit}(target) \ne step$ ，节点段覆盖就不对了。

为什么总复杂度仍是 $O(n\log C)$ ？

每个区间最多被删除一次，而总插入数 $\le n$ ，所以所有删除合计 $O(n)$ ；每次查找/修改 $O(\log C)$ 。

集合中的旧区间始终两两不交，因此按起点有序。日期上界只有 $10^5$ ，Fenwick 在每个起点保存是否存在区间，end_at[start] 保存终点。

先找起点不超过新左端的最后一条，检查它是否延伸到左端；再反复找第一个起点不小于左端的区间，直到起点超过新右端。每条被删线段都做一次 Fenwick 删除，最后加入新区间。

Python 知识

Fenwick 的 kth(rank) 用二进制提升实现动态集合按秩查找。
bytes 操作码直接与 b"B" 比较。
所有历史删除总数不超过插入总数，循环总成本仍是线性的删除次数乘对数。

代码

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#include <bits/stdc++.h>
using namespace std;

// 单点加、前缀和、区间和、按秩查找（模拟有序集合）。
// 下标必须从 1 开始。
template <typename T>
struct Fenwick {
    int n = 0;
    vector<T> tree;

    Fenwick(int n = 0) { init(n); }

    void init(int size) {
        n = size;
        tree.assign(n + 1, 0);
    }

    static int lowbit(int x) { return x & -x; }

    void add(int pos, T value) {
        for (int i = pos; i <= n; i += lowbit(i)) {
            tree[i] += value;
        }
    }

    T prefix_sum(int pos) const {
        T answer = 0;
        for (int i = pos; i > 0; i -= lowbit(i)) {
            answer += tree[i];
        }
        return answer;
    }

    T range_sum(int left, int right) const {
        return prefix_sum(right) - prefix_sum(left - 1);
    }

    // 第 rank 个 1 的位置（rank 从 1 开始），用于动态集合按秩查找
    int kth(int rank) const {
        int index = 0;
        int step = 1 << (31 - __builtin_clz(n));
        while (step) {
            int target = index + step;
            if (target <= n && tree[target] < rank) {
                index = target;
                rank -= tree[target];
            }
            step >>= 1;
        }
        return index + 1;
    }

    // 教学版 kth_ver2：用 range_sum 显式求"下一段"的和，替代 O(1) 的 tree[target]。
    // 二进制提升的不变量是 index 始终为 step 的倍数，所以 tree[target]
    // 覆盖的区间 (index, index+step] 恰好可以用 range_sum(index+1, target) 算出来。
    // 结果与 kth 完全相同，但每轮多花 O(log n) 算段和，整体 O(log^2 n)，只用于对比理解。
    int kth_ver2(int rank) const {
        int index = 0;
        int step = 1 << (31 - __builtin_clz(n));
        while (step) {
            int target = index + step;
            if (target <= n) {
                int segment_sum = range_sum(index + 1, target); // (index, index+step] 内 1 的个数
                if (segment_sum < rank) {
                    index = target;
                    rank -= segment_sum;
                }
            }
            step >>= 1;
        }
        return index + 1;
    }
};

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

    const int MAX = 100000;
    Fenwick<int> bit(MAX);       // 每个起点位置是否有区间（0/1）
    vector<int> end_at(MAX + 1); // end_at[start] 保存该起点区间的终点
    int active = 0;              // 当前区间数

    int n;
    cin >> n;
    while (n--) {
        char op;
        cin >> op;
        if (op == 'B') {
            cout << active << '\n';
            continue;
        }
        int l, r;
        cin >> l >> r;
        int removed = 0;
        // 起点 <= l 的区间中，只有最后一个可能延伸到 l
        int before = bit.prefix_sum(l);
        if (before) {
            int start = bit.kth(before);
            if (end_at[start] >= l) {
                bit.add(start, -1);
                end_at[start] = 0;
                active--;
                removed++;
            }
        }
        // 起点 >= l 的区间，只要起点 <= r 就必然相交（终点 >= 起点 >= l）
        while (bit.range_sum(l, MAX) > 0) {
            int start = bit.kth(bit.prefix_sum(l - 1) + 1);
            if (start > r) {
                break;
            }
            bit.add(start, -1);
            end_at[start] = 0;
            active--;
            removed++;
        }
        bit.add(l, 1);
        end_at[l] = r;
        active++;
        cout << removed << '\n';
    }

    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
66import sys


MAXIMUM = 100000
input = sys.stdin.buffer.readline
tree = [0] * (MAXIMUM + 1)
end_at = [0] * (MAXIMUM + 1)
active = 0


def add(index, delta):
    while index <= MAXIMUM:
        tree[index] += delta
        index += index & -index


def prefix(index):
    result = 0
    while index:
        result += tree[index]
        index -= index & -index
    return result


def kth(rank):
    index = 0
    step = 1 << (MAXIMUM.bit_length() - 1)
    while step:
        target = index + step
        if target <= MAXIMUM and tree[target] < rank:
            index = target
            rank -= tree[target]
        step >>= 1
    return index + 1


answers = []
for _ in range(int(input())):
    operation = input().split()
    if operation[0] == b"B":
        answers.append(str(active))
        continue
    left, right = map(int, operation[1:])
    removed = 0
    before = prefix(left)
    if before:
        start = kth(before)
        if end_at[start] >= left:
            add(start, -1)
            end_at[start] = 0
            active -= 1
            removed += 1
    while prefix(MAXIMUM) > prefix(left - 1):
        start = kth(prefix(left - 1) + 1)
        if start > right:
            break
        add(start, -1)
        end_at[start] = 0
        active -= 1
        removed += 1
    add(left, 1)
    end_at[left] = right
    active += 1
    answers.append(str(removed))

print("\n".join(answers))

复杂度

每次查找/修改 $O(\log C)$ ，所有删除合计 $O(n)$ ，总时间 $O(n\log C)$ ，空间 $O(C)$ ，其中 $C=10^5$ 。

总结

值域较小时，Fenwick 加按秩查询可以替代平衡树维护动态有序起点集合。

P2161 [SHOI2009] 会场预约

题目背景

形式化题意：

你需要维护一个在数轴上的线段的集合 $S$ ，支持两种操作：

A l r 表示将 $S$ 中所有与线段 $[l,r]$ 相交的线段删去，并将 $[l,r]$ 加入 $S$ 中。

B 查询 $S$ 中的元素数量。

对于 A 操作，每次还需输出删掉的元素个数。

题目描述

PP 大厦有一间空的礼堂，可以为企业或者单位提供会议场地。

这些会议中的大多数都需要连续几天的时间（个别的可能只需要一天），不过场地只有一个，所以不同的会议的时间申请不能够冲突。也就是说，前一个会议的结束日期必须在后一个会议的开始日期之前。所以，如果要接受一个新的场地预约申请，就必须拒绝掉与这个申请相冲突的预约。

一般来说，如果 PP 大厦方面事先已经接受了一个会场预约（例如从 $10$ 日到 $15$ 日），就不会再接受与之相冲突的预约（例如从 $12$ 日到 $17$ 日）。

不过，有时出于经济利益，PP 大厦方面有时会为了接受一个新的会场预约，而拒绝掉一个甚至几个之前预订的预约。于是，礼堂管理员 QQ 的笔记本上经常记录着这样的信息：（本题中为方便起见，所有的日期都用一个整数表示）例如，如果一个为期 $10$ 天的会议从 $90$ 日开始到 $99$ 日，那么下一个会议最早只能在 $100$ 日开始。（此处前后矛盾，若无法理解请参考形式化描述。）

最近，这个业务的工作量与日俱增，礼堂的管理员 QQ 希望参加 SHTSC 的你替他设计一套计算机系统，方便他的工作。这个系统应当能执行下面两个操作：

A 操作：有一个新的预约是从 $start$ 日到 $end$ 日，并且拒绝掉所有与它相冲突的预约。执行这个操作的时候，你的系统应当返回为了这个新预约而拒绝掉的预约个数，以方便 QQ 与自己的记录相校对。

B 操作：请你的系统返回当前的仍然有效的预约的总数。

输入格式

第一行一个正整数 $n$ ，表示操作个数。
接下来 $n$ 行，每行表示一个操作，都是上面两种中的一个。

输出格式

输出 $n$ 行，每行一个整数，表示对应操作的答案。

输入输出样例 #1

输入 #1

text

输出 #1

text

说明/提示

【数据范围】
对于 $100\%$ 的数据， $1\le n \le 2\times 10^5$ ， $1\le l \le r \le 10^5$ 。

[SHOI2009] 会场预约

目录

题意

思路

Python 知识

代码

复杂度

总结