第 14 章　标准库速查

配套例题：BISHI3 【模板】队列操作、BISHI6 【模板】整数优先队列、BISHI85 【模板】整数域二分 来源：菜鸟教程 Python3 标准库概览、operator 模块、math 模块、queue 模块

C++ 选手最大的心理落差往往在这里：Python 的标准库不是「STL 的替代品」， 而是一个更小但更快的子集。没有 set（有序集合）、没有 map（有序映射）、没有 lower_bound 成员函数， 但有 deque、Counter、heapq、bisect 这些足够覆盖 90% 笔试题的工具。

本章按模块整理，每个模块只列算法竞赛真正会用到的 API。 和第 13 章一起，构成 Python 竞赛的「工具箱」。

版本前提：本教程环境是 Python 3.9。 3.10+ 才有的 itertools.pairwise、bisect 的 key= 参数、int.bit_count() 在下文都会明确标出，不能使用。

---

14.1　竞赛标准导入清单

把这几行背下来，比什么都实用：

import sys
from collections import deque, defaultdict, Counter
from heapq import heappush, heappop, heapify, nlargest, nsmallest
from bisect import bisect_left, bisect_right, insort
from math import gcd, lcm, isqrt, inf, comb, perm, factorial
from itertools import accumulate, permutations, combinations, product, chain, groupby
from functools import lru_cache, reduce, cmp_to_key
from operator import itemgetter, attrgetter, add, mul, xor

---

14.2　collections

deque — 双端队列

最重要的容器，没有之一。list 的 pop(0) 和 insert(0, x) 是 \(O(n)\)， 在队列型题目里直接把复杂度推到 \(O(n^2)\)；deque 两端都是 \(O(1)\)。

from collections import deque

q = deque()                  # 空
q = deque([1, 2, 3])         # 从可迭代对象建
q = deque(maxlen=5)          # 定长，超出时自动从另一端挤出（滑动窗口偶尔有用）

q.append(x)                  # 右端入      O(1)
q.appendleft(x)              # 左端入      O(1)
q.pop()                      # 右端出      O(1)
q.popleft()                  # 左端出      O(1)
q[0], q[-1]                  # 两端取值    O(1)
len(q)                       # 长度        O(1)
q.extend(it) / q.extendleft(it)          # 批量入（extendleft 会逆序！）
q.rotate(k)                  # 循环右移 k 位（k 为负则左移）  O(k)
q.clear()

操作	list	deque
尾部 append / pop	\(O(1)\) 均摊	\(O(1)\)
头部插入 / 弹出	\(O(n)\)	\(O(1)\)
中间随机访问 a[i]	\(O(1)\)	\(O(n)\)
切片	支持	不支持
排序	a.sort()	不支持，要 sorted(q)

选择规则： - 当数组 / 栈用 → list（append + pop 就是栈）。 - 当队列 / 双端队列用 → deque。 - 需要随机访问下标 → list，deque 的 q[i] 是 \(O(n)\)。

BFS 一律用 deque；单调队列（滑动窗口最值）也一律用 deque。

Counter — 计数器

from collections import Counter

c = Counter("abracadabra")             # {'a':5, 'b':2, 'r':2, 'c':1, 'd':1}
c = Counter([1, 1, 2, 3])              # 对列表计数
c = Counter(words)                     # 对单词列表计数

c[x]                                   # 取计数，**不存在返回 0 而不是 KeyError**
c[x] += 1                              # 直接累加，不用先判断
c.most_common()                        # [(元素, 次数), ...] 按次数降序
c.most_common(3)                       # 前 3 个
c.total()                              # 所有计数之和（3.10+，3.9 用 sum(c.values())）
list(c.elements())                     # 按计数展开成元素序列

c1 + c2                                # 计数相加
c1 - c2                                # 相减（结果中非正数的项会被丢弃）
c1 & c2                                # 逐键取 min（多重集合交）
c1 | c2                                # 逐键取 max（多重集合并）

建 Counter 是 \(O(n)\) 且在 C 层完成，比手写 defaultdict(int) 循环快数倍。

most_common() 只保证按计数降序，不保证计数相同项的顺序（实际是插入序）。 题目要求「次数相同按字典序」时必须自己排：sorted(c, key=lambda w: (-c[w], w))。

c1 - c2 会丢弃计数 \(\le 0\) 的项，想要可能为负的差要用字典手算。

defaultdict — 带默认值的字典

from collections import defaultdict

g = defaultdict(list)                  # 值默认是 []，邻接表的标准写法
g[u].append(v)                         # 不需要先 if u not in g

cnt = defaultdict(int)                 # 值默认是 0
cnt[x] += 1

s = defaultdict(set)
s[k].add(v)

dp = defaultdict(lambda: -inf)         # 任意默认值用 lambda

工厂参数必须是「可调用对象」，写 defaultdict(0) 会 TypeError，要写 defaultdict(int)。

陷阱：读取不存在的键会「创建」它。

g = defaultdict(list)
if g[5]:                 # ← 这一句就把键 5 插进去了！
    ...
print(len(g))            # 1

只想查询不想创建时用 g.get(5) 或 5 in g。 在 DFS 里遍历 g 的同时访问 g[新键] 甚至会引发 RuntimeError: dictionary changed size during iteration。

dict.setdefault(k, default) 是不用 defaultdict 的等价写法，但每次都会构造默认值，更慢。

OrderedDict — 有序字典

Python 3.7 起普通 dict 已经保证插入顺序，所以 OrderedDict 只剩两个独有能力：

from collections import OrderedDict

od = OrderedDict()
od.move_to_end(k)                      # 把键移到末尾（last=False 移到开头）
od.popitem(last=False)                 # 从头部弹出（普通 dict 只能从尾部）

竞赛里唯一的用途是手写 LRU 缓存。其它场景直接用 dict（更快、更省内存）。

其它

from collections import namedtuple

Point = namedtuple("Point", "x y")
p = Point(1, 2)
p.x, p[0]                              # 都能访问

namedtuple 可读性好、可哈希、能排序（按字段顺序），但比裸元组慢。 竞赛里 \(n\) 大时用裸元组。

---

14.3　heapq — 优先队列

Python 的堆是函数式接口（操作列表），不是类。永远是最小堆。

import heapq

h = []
heapq.heappush(h, x)                   # 入堆      O(log n)
x = heapq.heappop(h)                   # 弹出最小   O(log n)
h[0]                                   # 查看最小   O(1)，不弹出
heapq.heapify(a)                       # 原地建堆   O(n)  ← 比逐个 push 的 O(n log n) 快
heapq.heappushpop(h, x)                # 先推后弹，一次调用
heapq.heapreplace(h, x)                # 先弹后推（堆必须非空）
heapq.nlargest(k, a, key=f)            # 前 k 大    O(n log k)
heapq.nsmallest(k, a, key=f)           # 前 k 小
list(heapq.merge(a, b))                # 归并多个已排序序列，惰性

最大堆：取负

h = []
heapq.heappush(h, -x)                  # 存进去取负
mx = -heapq.heappop(h)                 # 取出来再取负

也可以整体取负后 heapify：h = [-x for x in a]; heapq.heapify(h)。

存元组：按字典序比较

heapq.heappush(h, (dist, node))        # Dijkstra 的标准写法，按 dist 排序
heapq.heappush(h, (-w, i, obj))        # 权值降序；加 i 防止比较到 obj

堆里最隐蔽的 RE：元组的前几项相等时，Python 会继续比较后面的项。 如果后面是一个没有 __lt__ 的对象，就会 TypeError: '<' not supported between instances of 'Foo' and 'Foo'。 对策：在对象前面插一个唯一递增的序号（如上面的 i），保证永远比不到对象本身。

没有「删除任意元素」

heapq 只能弹最小值。需要删除中间元素时用懒删除：

h = []
removed = Counter()                    # 记录待删除的值

def lazy_pop():
    while h and removed[h[0]] > 0:
        removed[heapq.heappop(h)] -= 1
    return heapq.heappop(h)

需要「有序集合」（std::set 的完整功能）时，Python 没有内建替代品， 方案见 116-平衡树与有序集合。

不要用 queue.PriorityQueue。它是为多线程设计的，每次操作都要加锁， 比 heapq 慢 3–5 倍。queue 模块整个在竞赛里都不该出现。 同理，queue.Queue 也不要用，队列用 collections.deque。

---

14.4　bisect — 有序数组二分

import bisect

bisect.bisect_left(a, x)               # 第一个 >= x 的位置（C++ 的 lower_bound）
bisect.bisect_right(a, x)              # 第一个 >  x 的位置（C++ 的 upper_bound）
bisect.bisect(a, x)                    # bisect_right 的别名
bisect.insort_left(a, x)               # 插入并保持有序
bisect.insort_right(a, x)
bisect.bisect_left(a, x, lo, hi)       # 限定搜索区间

前提：a 必须已经升序排好。不排序直接用，结果是错的但不会报错。

四个必背用法

a.sort()

# 1. x 是否存在
i = bisect_left(a, x)
exists = i < len(a) and a[i] == x

# 2. 有多少个元素 < x
bisect_left(a, x)

# 3. 有多少个元素 == x
bisect_right(a, x) - bisect_left(a, x)

# 4. 有多少个元素落在闭区间 [l, r]
bisect_right(a, r) - bisect_left(a, l)

第 4 条就是 BISHI85 的完整解法。

需求	C++	Python
第一个 \(\ge x\)	lower_bound	bisect_left
第一个 \(> x\)	upper_bound	bisect_right
最后一个 \(< x\)	lower_bound(...) - 1	bisect_left(a, x) - 1
最后一个 \(\le x\)	upper_bound(...) - 1	bisect_right(a, x) - 1

两个坑： 1. insort 是 \(O(n)\)，因为列表插入要搬移元素。查找是 \(O(\log n)\) 但插入不是。 循环里频繁 insort 会退化成 \(O(n^2)\)，\(n = 10^5\) 就危险了。 2. bisect 的 key= 参数是 Python 3.10 才有的，3.9 不能用。 要按 key 二分，只能另外建一个 key 数组：

keys = [t[0] for t in a]                   # 提前抽出关键字
i = bisect_left(keys, x)

对元组数组还有个技巧：bisect_left(a, (x,)) 利用元组比较找第一个第 0 项 \(\ge x\) 的位置。

二分答案（对答案而非数组二分）是另一回事，见 44-二分。

---

14.5　itertools

全部返回迭代器（惰性），需要列表要显式 list(...)。

累积与展平

from itertools import accumulate, chain

list(accumulate([1, 2, 3, 4]))                 # [1, 3, 6, 10]      前缀和
list(accumulate(a, initial=0))                 # [0, 1, 3, 6, 10]   3.8+，带前导 0
list(accumulate(a, max))                       # 前缀最大值
list(accumulate(a, lambda x, y: x * y % MOD))  # 自定义二元函数

list(chain(a, b, c))                           # 拼接多个序列
list(chain.from_iterable(mat))                 # 展平二维列表

accumulate(a, initial=0) 是求前缀和的最快写法——比推导式和循环都快， 而且长度正好是 \(n+1\)，符合前缀和的下标习惯：

pre = list(accumulate(a, initial=0))
# 区间 [l, r) 的和 = pre[r] - pre[l]

排列组合枚举

from itertools import permutations, combinations, combinations_with_replacement, product

list(permutations([1, 2, 3]))                  # 全排列，6 个元组
list(permutations([1, 2, 3], 2))               # 排列数 A(3,2)，6 个
list(combinations([1, 2, 3], 2))               # 组合 C(3,2)：(1,2),(1,3),(2,3)
list(combinations_with_replacement("ab", 2))   # 可重组合：aa, ab, bb
list(product([0, 1], repeat=3))                # 笛卡尔积：000, 001, ..., 111
list(product(a, b))                            # 两个序列的所有配对

都按输入顺序生成，所以输入有序 → 输出天然字典序（BISHI78 全排列就靠这条）。

product(range(k), repeat=n) 是枚举 \(k^n\) 种状态的标准写法， 比手写 \(n\) 层循环短得多，且速度接近。

分组

from itertools import groupby

for key, grp in groupby(a):                    # 按「相邻且相等」分组
    print(key, len(list(grp)))
for key, grp in groupby(a, key=lambda x: x // 10):
    ...

groupby 只分「相邻」的组，不会先排序！ 要全局分组必须先 a.sort(key=同一个 key)。这是从 SQL 的 GROUP BY 迁移过来的最大误区。

另外 grp 是迭代器，下一次循环时会失效，需要保留必须立刻 list(grp)。

游程编码（RLE）一行搞定：

rle = [(k, len(list(g))) for k, g in groupby(s)]

其它

from itertools import islice, count, cycle, repeat, compress, starmap, zip_longest

list(islice(it, 5))                    # 取迭代器的前 5 个，不复制
list(islice(it, 2, 8))                 # 切片式取用
for i in count(1):                     # 1, 2, 3, ... 无限计数
for x in cycle(a):                     # 无限循环 a
list(repeat(0, 5))                     # [0,0,0,0,0]
list(zip_longest(a, b, fillvalue=0))   # 补齐版 zip，不截断

itertools.pairwise 是 Python 3.10 才加的，3.9 环境下要用：

for x, y in zip(a, a[1:]):     # 相邻元素对

---

14.6　math

常量

math.pi, math.e, math.inf, math.nan, math.tau

求距离/面积一律用 math.pi，不要手写 3.14159（见 PIO17）。 math.inf 是 DP / 最短路初始化的标配。

竞赛高频函数

函数	说明	版本
gcd(*ints)	最大公约数，3.9 起支持多参数	3.5+
lcm(*ints)	最小公倍数	3.9+
isqrt(n)	整数平方根（精确，向下取整）	3.8+
comb(n, k)	组合数 \(\binom{n}{k}\)（精确大整数）	3.8+
perm(n, k)	排列数 \(A_n^k\)	3.8+
factorial(n)	阶乘（精确大整数）	—
prod(it)	连乘	3.8+
floor(x) / ceil(x)	下取整 / 上取整，返回 int	—
log2(x) / log(x[, base]) / log10(x)	对数	—
hypot(*coords)	欧几里得范数	—
dist(p, q)	两点距离	3.8+
fsum(it)	高精度浮点求和	—
degrees / radians	角度弧度互转	—

import math

math.gcd(12, 18, 24)                   # 6，3.9 起可以多参数
math.lcm(4, 6)                         # 12，3.9 新增
math.isqrt(10 ** 18)                   # 1000000000，精确
math.comb(50, 25)                      # 精确大整数，无需取模
math.floor(-7 / 2)                     # -4，返回 int

陷阱清单： - math.pow 只返回 float，且不支持三参数取模。求幂一律用 ** 或内置 pow。 - math.sqrt 返回 float，大整数会丢精度。整数平方根用 isqrt。 - math.log2(2**53 + 1) 可能不精确。判断 2 的幂用 n > 0 and n & (n - 1) == 0—— 2 的幂在二进制里只有一个 1，减 1 后该位变 0、右边全变 1，两者按位与必为 0； n > 0 这个前提不能省，因为 0 & -1 也等于 0，会把 0 误判成 2 的幂。 - math.factorial / math.comb 算的是精确值。\(n\) 上万时数字巨大且很慢， 模意义下的组合数要用「预处理阶乘 + 逆元」（见 84-组合数学）。 - math.ceil(a / b) 会走浮点，大整数不精确。整数上取整用 -(-a // b)： // 永远向下取整，先取负让「向下」落到相反的一侧，算完再取负翻回来，就成了向上取整。

---

14.7　functools

from functools import lru_cache, cache, reduce, cmp_to_key, partial, total_ordering

lru_cache / cache — 记忆化

@lru_cache(maxsize=None)               # 竞赛一律 maxsize=None
def dp(i, j):
    ...

@cache                                 # 3.9+，等价于 lru_cache(maxsize=None)
def dp(i, j):
    ...

dp.cache_clear()                       # 多组数据之间必须清空！
dp.cache_info()                        # 命中统计，本地调试用

注意点	说明
参数必须可哈希	传 list 会 TypeError，转 tuple
多组数据要 cache_clear()	否则第二组用上第一组的缓存，全错
不解决递归深度	深度大仍会 RecursionError
有额外开销	每次调用要建元组 + 查字典，热点场景不如手写数组 DP

性能提示：@lru_cache 的常数比自己开二维数组做递推大 2–4 倍。 状态空间 \(\le 10^6\) 时很方便；再大就要改写成迭代递推。

reduce — 折叠

from functools import reduce
from operator import xor, mul, and_, or_

reduce(xor, a, 0)                      # 全体异或
reduce(mul, a, 1)                      # 全体乘积（不如 math.prod）
reduce(math.gcd, a)                    # 全体 gcd
reduce(lambda x, y: x * y % MOD, a, 1) # 带模的连乘

reduce(f, it, init)：把 f 依次作用到累积值和下一个元素上。 配 operator 里的 C 函数才快，配 lambda 就是普通循环的速度。

cmp_to_key — 比较函数转 key

见 12-自定义排序。 一句话：慢 8–15 倍，只在比较规则无法表示成单元素 key 时用。

partial — 固定部分参数

from functools import partial
f = partial(pow, 2)                    # f(x) == pow(2, x)

竞赛里少用，知道即可。

---

14.8　decimal 与 fractions

decimal — 精确十进制

from decimal import Decimal, getcontext, ROUND_HALF_UP

getcontext().prec = 50                 # 设置有效数字位数（默认 28）

d = Decimal("1.005")                   # ✅ 从字符串构造，精确
d = Decimal(1.005)                     # ❌ 先经过 float，已经不准了
d.quantize(Decimal("0.00"), rounding=ROUND_HALF_UP)   # 严格四舍五入到 2 位

竞赛用途：严格保留小数位数（round 和 %f 用的是银行家舍入，见 PIO14）、 高精度小数运算。

Decimal 比 float 慢 50–100 倍，只在真正需要精确时用。

fractions — 精确分数

from fractions import Fraction

Fraction(1, 3) + Fraction(1, 6)        # Fraction(1, 2)，自动约分
Fraction("0.25")                       # Fraction(1, 4)
f.numerator, f.denominator             # 分子分母
f.limit_denominator(1000)              # 限制分母大小的最佳逼近

用途：概率/期望题要求输出既约分数、避免浮点误差的比较。 极慢（每次运算都要求 gcd），\(n\) 大时改用「分子分母分开算 + 最后约分」。

见 23-浮点与科学计数法。

---

14.9　random

import random

random.seed(42)                        # 固定种子，保证可复现
random.random()                        # [0, 1) 的浮点
random.randint(a, b)                   # [a, b] 的整数，**两端都闭**
random.randrange(a, b)                 # [a, b) 的整数，和 range 一致
random.choice(a)                       # 随机取一个元素
random.shuffle(a)                      # 原地打乱
random.sample(a, k)                    # 不放回抽 k 个
random.getrandbits(64)                 # 随机 64 位整数

竞赛里的三个用途：

1. 对拍：写数据生成器（见 01-语法与执行模型）。
2. 防卡哈希：字符串哈希的底数用随机质数，避免被构造数据卡（见 36-哈希与字符串哈希）。
3. 随机化算法：随机增量法、Pollard-Rho 分解。

randint(a, b) 包含 b，randrange(a, b) 不包含 b。这两个混用是常见 bug。

---

14.10　sys

import sys

data = sys.stdin.buffer.read().split()          # 最快的读入
sys.stdout.write(s)                             # 最快的输出
for line in sys.stdin:                          # 按行迭代到 EOF
sys.stdin.readline()                            # 读一行（保留 '\n'）

sys.setrecursionlimit(1 << 20)                  # 提高递归深度上限
sys.maxsize                                     # 解释器索引类型的上限（约 9.2e18），常借来当 INF
                                                #   Python 的 int 本身没有上限，这不是「最大整数」
sys.exit()                                      # 立即退出
sys.argv                                        # 命令行参数
sys.set_int_max_str_digits(0)                   # 解除 int(str) 的位数限制（3.11+）

sys.maxsize 与 math.inf 的取舍：

场景	用
结果要保持 int 类型（下标、位运算、取模）	sys.maxsize 或一个足够大的常量如 10 ** 18
只做浮点比较、允许 inf 参与运算	math.inf

math.inf 参与整数运算会把结果变成 float，进而丢精度。 最短路 / DP 的初始值建议用 10 ** 18 这样的整数常量，不要用 math.inf。

I/O 的完整讨论见 20-输入输出处理。

---

14.11　例题

BISHI3　【模板】队列操作（简单）

空队列，依次执行 \(n\ (1 \le n \le 10^5)\) 个操作： 1 x 入队；2 出队（空则输出 ERR_CANNOT_POP）； 3 查询队首（空则输出 ERR_CANNOT_QUERY）；4 输出队列长度。 题面见 BISHI3 原题（牛客）。

import sys
from collections import deque


def main():
    data = sys.stdin.buffer.read().split()
    p = 0
    n = int(data[p]); p += 1
    q = deque()
    out = []
    for _ in range(n):
        op = data[p]; p += 1
        if op == b"1":
            q.append(data[p]); p += 1        # 直接存 bytes，省一次 int 转换
        elif op == b"2":
            if q:
                q.popleft()                  # O(1)
            else:
                out.append("ERR_CANNOT_POP")
        elif op == b"3":
            out.append(q[0].decode() if q else "ERR_CANNOT_QUERY")
        else:
            out.append(str(len(q)))
    sys.stdout.write("\n".join(out) + "\n")


main()

要点：

• deque.popleft() 是 \(O(1)\)，list.pop(0) 是 \(O(n)\)。 \(n = 10^5\) 时后者最坏 \(5 \times 10^9\) 次元素搬移，必然 TLE。 这是 Python 竞赛最常见的 TLE 原因之一，另一个是拿 list 做 in 判断。
• 变长操作行：2/3/4 后面没有参数，所以不能按固定步长推进游标， 必须读到 op 后再决定要不要多读一个 token。token 流天然支持这一点—— 换行位置对它毫无影响。
• data 里是 bytes，所以比较要写 op == b"1"。 也可以在读入时统一 int(op)，但直接比 bytes 更快。 存入队列的 x 也保持 bytes，查询时才 .decode()，省下 \(10^5\) 次 int()。
• 输出攒在 out 里最后一次写。

BISHI6　【模板】整数优先队列（简单）

空多重集合，\(n\ (1 \le n \le 10^6)\) 个操作： 1 x 插入；2 输出最小元素；3 删除一个最小元素。 题面见 BISHI6 原题（牛客）。

\(n\) 到了 \(10^6\)，读入和输出的常数成为主要矛盾：

import sys
from heapq import heappush, heappop


def main():
    data = sys.stdin.buffer.read().split()
    p = 0
    n = int(data[p]); p += 1
    h = []
    out = []
    for _ in range(n):
        op = data[p]; p += 1
        if op == b"1":
            heappush(h, int(data[p])); p += 1
        elif op == b"2":
            out.append(h[0])                 # 查看堆顶，O(1)，不弹出
        else:
            heappop(h)
    sys.stdout.write("\n".join(map(str, out)) + "\n")


main()

要点：

• from heapq import heappush, heappop，不要写 heapq.heappush。 后者每次调用都要做一次模块属性查找，\(10^6\) 次下差别可观（约 10%）。
• 查询最小值用 h[0]，不要 heappop 后再 heappush。前者 \(O(1)\)，后者 \(O(\log n)\)。
• 一律用 sys.stdin.buffer.read()。\(10^6\) 行用 input() 读要 5 秒以上，直接 TLE。
• 不要用 queue.PriorityQueue。它带线程锁，\(10^6\) 次操作会慢 3–5 倍。
• 总复杂度 \(O(n \log n)\)，Python 大约 2–3 秒。这题时限「其他语言 6 秒」，能过。 如果卡得更紧，可以把主循环按操作类型拆开、把 int() 挪出热点——但那属于卡常范畴了。 （heapq 的 C 实现只接受 list，传 array 会直接抛 TypeError。）

元素是 int 而不是元组，所以不存在「比较到不可比对象」的问题。 一旦需要按自定义规则排序，就要给类写 __lt__，见 15-面向对象与迭代器生成器。

BISHI85　【模板】整数域二分（简单）

长度 \(n\ (1 \le n \le 2\times10^5)\) 的数组，\(q\ (1 \le q \le 2\times10^5)\) 次查询， 每次给 \(l, r\)，问有多少个元素落在 \([l, r]\) 内。 题面见 BISHI85 原题（牛客）。

排序一次 + 每次查询两个二分，总复杂度 \(O((n + q)\log n)\)：

import sys
from bisect import bisect_left, bisect_right


def main():
    data = sys.stdin.buffer.read().split()
    n, q = int(data[0]), int(data[1])
    a = sorted(map(int, data[2:2 + n]))          # 必须先排序！
    p = 2 + n
    out = []
    for _ in range(q):
        l = int(data[p]); r = int(data[p + 1]); p += 2
        out.append(bisect_right(a, r) - bisect_left(a, l))
    sys.stdout.write("\n".join(map(str, out)) + "\n")


main()

要点：

• bisect_right(a, r) - bisect_left(a, l) 就是区间 \([l, r]\) 内的元素个数。 推导：bisect_right(a, r) = 有多少个 \(\le r\)；bisect_left(a, l) = 有多少个 \(< l\)；相减即得。
• 两个函数不能互换。写成 bisect_left(a, r) - bisect_left(a, l) 会漏掉所有等于 \(r\) 的元素；写成 bisect_right(a, r) - bisect_right(a, l) 会漏掉所有等于 \(l\) 的元素。边界是这题唯一的难点。
• 题目没说 \(l \le r\)。如果 \(l > r\)，上式自然返回负数——保险起见可以 max(0, ...)，或者读入后 if l > r: l, r = r, l。防御性写法不花钱。
• 数组不会变（只有查询没有修改），所以排一次序就够。 如果带修改，就要上树状数组 / 线段树，见 39-树状数组与线段树。
• \(a_i\) 可以是负数，bisect 完全不受影响（它只依赖 <）。

完整题解：BISHI3、BISHI6、BISHI85

---

14.12　本章速查

需求	模块 · API	复杂度
队列 / 双端队列 / BFS	collections.deque 的 append/popleft	\(O(1)\)
栈	list 的 append/pop	\(O(1)\)
计数 / 词频	collections.Counter(a)	\(O(n)\)
邻接表	defaultdict(list)	—
优先队列	heapq.heappush / heappop / h[0]	\(O(\log n)\) / \(O(1)\)
建堆	heapq.heapify(a)	\(O(n)\)
最大堆	存 -x	—
前 \(k\) 大	heapq.nlargest(k, a)	\(O(n\log k)\)
lower_bound	bisect.bisect_left	\(O(\log n)\)
upper_bound	bisect.bisect_right	\(O(\log n)\)
区间 \([l,r]\) 计数	bisect_right(a,r) - bisect_left(a,l)	\(O(\log n)\)
前缀和	list(accumulate(a, initial=0))	\(O(n)\)
展平二维	chain.from_iterable(mat)	\(O(n)\)
全排列 / 组合	permutations / combinations	—
枚举 \(k^n\) 状态	product(range(k), repeat=n)	—
相邻分组 / RLE	groupby（只分相邻，需先排序）	\(O(n)\)
记忆化	@lru_cache(maxsize=None)，多组数据记得 cache_clear()	—
折叠	reduce(operator.xor, a, 0)	\(O(n)\)
gcd / lcm	math.gcd（两参数 3.5+，多参数 3.9+）/ math.lcm（3.9+）	对数级
整数平方根	math.isqrt(n)	—
组合数（精确）	math.comb(n, k)	—
严格四舍五入	Decimal(...).quantize(..., ROUND_HALF_UP)	—
精确分数	fractions.Fraction	很慢
快读快写	sys.stdin.buffer.read().split() / sys.stdout.write	—
整数 INF	10 ** 18 或 sys.maxsize（别用 math.inf）	—

禁用清单	原因
list.pop(0)	\(O(n)\)，用 deque.popleft()
queue.Queue / queue.PriorityQueue	带线程锁，慢 3–5 倍
bisect(..., key=...)	3.10+ 才有，3.9 不能用
itertools.pairwise	3.10+ 才有，用 zip(a, a[1:])
math.pow	只返回 float
math.factorial(10**6)	精确大整数，慢且占内存
循环里 bisect.insort	插入是 \(O(n)\)，整体 \(O(n^2)\)