Python Bisect, Sys, Iteration 复习

Bisect¶

bisect 是 Python 标准库中专门用于 二分查找（Binary Search） 的模块。它的核心作用是在 有序列表 中寻找插入点，或者在不破坏顺序的情况下进行插入。

使用 bisect 的前提：列表必须是已经排序好的（升序）。

1. 核心函数对比：`bisect_left` vs `bisect_right`¶

这是最常用的两个函数，它们决定了当遇到 重复元素 时，插入位置是在左边还是右边。

(1) `bisect_left(list, x)`¶

功能：返回第一个 大于或等于 x 的元素的索引。
直观理解：如果 x 已经在列表中，返回它左侧的索引；如果不在，返回它应该被插入的位置。

(2) `bisect_right(list, x)` (等同于 `bisect`)¶

功能：返回第一个 严格大于 x 的元素的索引。
直观理解：如果 x 已经在列表中，返回它右侧的索引。

举例说明：¶

import bisect

arr = [1, 3, 3, 3, 5]
x = 3

idx_left = bisect.bisect_left(arr, x)   # 结果是 1 (第一个 3 的位置)
idx_right = bisect.bisect_right(arr, x) # 结果是 4 (5 的位置，即最后一个 3 的右侧)

print(f"Left index: {idx_left}")
print(f"Right index: {idx_right}")

2. 插入函数：`insort_left` 和 `insort_right`¶

如果你不仅想知道位置，还想**真的把元素塞进去**，就用 insort 系列。

bisect.insort_left(arr, x)：查找位置并原地插入 x。
bisect.insort_right(arr, x)：查找位置并原地插入 x（重复元素插在右边）。

注意：insort 的时间复杂度是 \(O(n)\)，因为虽然查找是 \(O(\log n)\)，但列表插入元素（移动后续内存）是 \(O(n)\)。

3. 高级参数：`lo`, `hi` 和 `key`¶

从 Python 3.10 开始，bisect 变得更加强大：

(1) 限定范围：`lo` 和 `hi`¶

你可以只在列表的某个区间内进行二分查找。

# 只在索引 2 到 5 之间查找
idx = bisect.bisect_left(arr, x, lo=2, hi=5)

(2) 关键字查找：`key` (非常有用)¶

如果你的列表里存的是对象或元组，你可以指定比较的字段。

# 按照元组的第一个元素进行二分查找
data = [(1, 'apple'), (3, 'banana'), (5, 'cherry')]
idx = bisect.bisect_left(data, 3, key=lambda x: x[0]) 
# 结果是 1，对应 (3, 'banana')

4. 经典应用场景¶

场景 A：成绩/区间映射 (等效于很多 `if-elif`)¶

假设你要根据分数给学生打等级（A, B, C, D, F）：

def grade(score):
    breakpoints = [60, 70, 80, 90]
    grades = 'FDCBA'
    # 找到分数所在的区间索引
    i = bisect.bisect_right(breakpoints, score)
    return grades[i]

print([grade(s) for s in [55, 62, 77, 95]])
# 输出: ['F', 'D', 'C', 'A']

场景 B：最长上升子序列 (LIS)¶

正如你之前提到的，tails[bisect_left(tails, x)] = x 是优化 LIS 的神来之笔。

场景 C：查找元素是否存在¶

虽然 x in arr 也可以，但对于有序大数组，二分查找更快：

def exists(arr, x):
    i = bisect.bisect_left(arr, x)
    return i != len(arr) and arr[i] == x

总结¶

查位置：bisect_left (找左边界), bisect_right (找右边界)。
塞元素：insort_left, insort_right。
优势：在 \(O(\log n)\) 时间内完成查找，比遍历快得多。
记住：列表必须是**有序**的，否则结果毫无意义。

ask: 如果 list 中所有元素都严格小于 x 呢？

这是一个非常关键的边界情况。

如果 list 中的**所有元素都严格小于 x**，那么 bisect_left 和 bisect_right 的表现如下：

1. 返回值：`len(list)`¶

无论你使用 bisect_left 还是 bisect_right，它们都会返回该列表的 长度 \(n\)。

原因： 二分查找的目标是找到一个插入点，使得插入 \(x\) 后列表依然有序。如果 \(x\) 比列表中现有的所有数都大，那么它唯一能待的地方就是列表的**最后面**（即索引为 \(n\) 的位置）。

2. 代码示例演示¶

import bisect

arr = [1, 2, 3, 4, 5]
x = 10  # 10 显然大于数组中所有元素

idx_left = bisect.bisect_left(arr, x)
idx_right = bisect.bisect_right(arr, x)

print(f"List length: {len(arr)}") # 输出: 5
print(f"Left index: {idx_left}")   # 输出: 5
print(f"Right index: {idx_right}") # 输出: 5

3. 在不同场景下的含义¶

这个返回值 len(list) 在不同的算法逻辑中有着不同的“信号”作用：

场景 A：最长上升子序列 (LIS) 优化¶

这是最常用的场景。如果你在维护 tails 数组： * 如果 bisect_left 返回了 len(tails)，说明当前元素 \(x\) 比之前所有的末尾都大。 * 动作： tails.append(x)。这代表最长上升子序列的**长度增加了 1**。

场景 B：查找并访问元素¶

如果你拿到索引后紧接着去访问列表，比如 arr[idx]，就会导致 IndexError: list index out of range。 * 正确做法： 永远先检查索引是否越界。

idx = bisect.bisect_left(arr, x)
if idx < len(arr):
    print(f"找到了第一个 >= {x} 的数: {arr[idx]}")
else:
    print(f"{x} 比数组里所有的数都大！")

场景 C：查找“最后一个小于 x 的元素”¶

如果你想找数组中比 \(x\) 小的最大那个数，通常会用 bisect_left(arr, x) - 1。 * 如果返回的是 len(arr)，那么 len(arr) - 1 正好指向数组的**最后一个元素**。 * 这完全符合逻辑：既然所有数都比 \(x\) 小，那么最大的那个当然是最后一个。

总结¶

当 bisect 返回的索引等于列表长度时，它在向你发出一个明确的信号：“你要找的这个数太大了，它应该排在全队的最后。”

Sys¶

import sys

input = sys.stdin.read().split()
it = iter(input)

n = int(next(it))
matrix = [[int(next(it)) for _ in range(n)] for _ in range(n)]
//读入矩阵样例

在算法竞赛中，Python 的 input() 函数因为包含了很多处理逻辑（比如去除换行符、抛出异常等），在面对大规模数据（如 \(10^5\) 级别）时效率极低，经常导致 TLE (Time Limit Exceeded)。

使用 sys 模块进行输入输出是 Python 竞赛选手的必备技能。以下是几种最常用的写法及适用场景：

写法一：全量读取迭代法（最推荐，速度最快）¶

这种写法一次性将输入读入内存，然后按空格或换行切分。适用于绝大多数题目，尤其是那种“数字全挤在一起”或者“坐标跨行”的情况。

import sys

def solve():
    # 核心：一次性读取所有内容，切分成单词列表，转为迭代器
    input_data = sys.stdin.read().split()
    it = iter(input_data)

    # 使用 next(it) 逐个获取数据
    t = int(next(it))  # 读取测试用例数
    for _ in range(t):
        n = int(next(it))  # 读取 n
        m = int(next(it))  # 读取 m
        # 读取一个长度为 n 的数组
        arr = [int(next(it)) for _ in range(n)]

        # 处理逻辑...

if __name__ == "__main__":
    solve()

* 优点：速度极致。自动过滤掉多余的空行、空格。 * 缺点：如果输入文件非常巨大（例如几百 MB），可能会占用过多内存。但在常规竞赛（256MB/512MB）中完全没问题。

写法二：重定义 `input`（最无痛，适合平替）¶

如果你不想改变原来的 input() 写法逻辑，只需在代码开头加一行。

import sys

# 将系统的 readline 函数赋值给 input
# 注意：readline 会保留行末的换行符 \n，所以通常配合 .split() 使用
input = sys.stdin.readline

# 之后你可以像以前一样用，但速度提升几倍
n = int(input())
a, b = map(int, input().split())

* 注意：readline() 读到的是字符串且带换行符。如果是读字符串题目，记得用 input().strip() 去掉换行符。

写法三：逐行处理（适合矩阵或大批量行数据）¶

当题目是按行给出数据（比如 \(N\) 行 \(M\) 列的矩阵）时，直接迭代 sys.stdin。

import sys

# 直接遍历 stdin，它是按行生成的迭代器
for line in sys.stdin:
    if not line.strip(): # 处理可能的空行
        continue
    row = list(map(int, line.split()))
    # 处理这一行...

写法四：快速输出¶

当输出量也很大时（比如打印 \(10^5\) 个数），频繁调用 print() 也会慢。

import sys

# 方式 1：使用 sys.stdout.write (只能接字符串)
sys.stdout.write(str(ans) + '\n')

# 方式 2：批量收集结果，最后一次性打印 (最快)
results = []
for res in all_answers:
    results.append(str(res))
sys.stdout.write('\n'.join(results) + '\n')

进阶：针对递归题目的“保命”设置¶

Python 默认递归深度很浅（通常只有 1000），做 DFS（深度优先搜索）时必挂。配合 sys 使用：

import sys

# 设置递归深度上限，通常设为 10^5 或 10^6
sys.setrecursionlimit(200000)

总结建议：¶

首选写法一：sys.stdin.read().split() 配合 iter。它最稳，不用担心空行、多余空格或跨行数据的问题。
如果是交互题：绝对不能用 read()，必须用 sys.stdin.readline() 且每次输出后要 sys.stdout.flush()。
字符串题目：用 sys.stdin.readline().strip() 确保拿到的字符串不包含末尾的 \n。

一句话口诀：大批量数字用 read().split()，按行读字符串用 readline().strip()。

Iter¶

在 Python 中，迭代器（Iterator） 是一个非常核心的概念。简单来说，它就像一个“只进不退”的传送带，每次你向它要一个东西，它就吐出一个，直到吐完为止。

以下是迭代器的详细使用方法，分为基础操作、进阶技巧以及在竞赛中的妙用。

1. 基本概念：如何产生一个迭代器？¶

大部分我们熟悉的容器（列表、元组、字符串、字典）都是**可迭代对象（Iterable），但它们不是**迭代器。你需要用 iter() 函数来转化它们。

arr = [10, 20, 30]
it = iter(arr)  # 此时 it 就是一个迭代器

2. 获取数据：`next()` 函数¶

这是操作迭代器的唯一手动方式。

写法 A：直接取值

print(next(it))  # 输出 10
print(next(it))  # 输出 20

写法 B：带默认值的取值（推荐） 如果迭代器空了，直接 next(it) 会报错 StopIteration。为了安全，可以给个默认值：
```
val = next(it, "没了") 
```

3. 核心特性：只能前进，不能回头¶

迭代器有两个最重要的特点： 1. 惰性计算（Lazy Evaluation）：它不会一次性把所有数据准备好，而是你问它要，它才计算。这在处理超大数据集时非常省内存。 2. 一次性消耗：一旦某个元素被取走，它就从迭代器中消失了。你不能让迭代器“回到开头”。

arr = [1, 2, 3]
it = iter(arr)
for x in it:
    print(x) # 打印 1, 2, 3

# 再次运行这个循环：
for x in it:
    print(x) # 什么都不会打印！因为 it 已经干了。

4. 竞赛中的高级技巧¶

(1) 跨行读取与数据嵌套¶

正如之前讨论的，在处理“先读一个 \(T\)，再读 \(N\) 个数”这种结构时，迭代器非常高效：

it = iter(sys.stdin.read().split())

T = int(next(it))
for _ in range(T):
    N = int(next(it))
    # 连续取出 N 个元素构成列表
    arr = [int(next(it)) for _ in range(N)]

(2) 使用 `zip` 进行“成对”处理¶

如果你想两两一组处理数据，可以用迭代器配合 zip：

it = iter([1, 2, 3, 4, 5, 6])
# zip 每次从 it 中取两个，因为 it 是同一个，所以取走 1 之后，下次取就是 2
pairs = zip(it, it)
print(list(pairs)) # 输出 [(1, 2), (3, 4), (5, 6)]

(3) `map` 和 `enumerate` 本身就是迭代器¶

在 Python 3 中，map、filter、enumerate 返回的都是迭代器。这也是为什么你不能直接打印它们，而需要用 list() 转换的原因。

m = map(int, ["1", "2"]) # m 是迭代器
print(next(m)) # 输出整数 1

5. `itertools` 模块：迭代器的“武器库”¶

Python 内置的 itertools 模块提供了很多极其强大的迭代器工具，竞赛必备：

itertools.accumulate(arr)：生成前缀和迭代器。
itertools.permutations(arr)：生成全排列。
itertools.combinations(arr, r)：生成组合。
itertools.chain(arr1, arr2)：把两个列表像接火车一样接起来，不产生新列表，节省内存。
itertools.groupby()：将相邻的重复元素分组（类似去重）。

总结：为什么要用迭代器？¶

省内存：不需要一次性开辟巨大的空间存所有数据。
高性能：在循环处理中，迭代器的底层优化通常比手动索引更快。
代码简洁：配合 next()，可以非常优雅地处理复杂的输入格式。

竞赛口诀：数据大了用 sys 读，读完转成 iter 走，next 取值最稳妥，itertools 是好帮手。