快速输入输出（快读快写）

代码模板

竞赛风格的高效整数快速读入与快速输出实现，结构精简，易于书写和记忆。

  • 基础技巧
  • 快读快写
  • 输入输出优化
  • 代码模板

一句话算法

快读“跳空白、判负号、十倍累加”，快写“先判负、除十递、取模转字符”。

问题模型

在算法竞赛中，输入输出（I/O）往往是程序效率的隐形瓶颈。当输入输出的数据规模达到 105∼10710^5 \sim 10^7 级别时，耗时往往不在于算法本身的计算，而在于将外部文本流解析为内存数值的过程。

为什么标准 I/O 较慢

以 C++ 为例，常见 I/O 方式的开销主要集中在以下三个层面：

  1. 流同步机制：std::cin 与 std::cout 默认与 C 语言标准 I/O（scanf/printf）共享缓冲区以保证兼容性，这种同步机制会增加额外的虚函数调用与状态维护开销。
  2. 输入输出流绑定：默认情况下 std::cin 绑定到 std::cout，每次执行读取操作前都会隐式调用 std::cout.flush()，在大规模交互读写时导致频繁刷新。
  3. 格式化与本地化解析：scanf 和 printf 需要在运行时解析格式化字符串（如 %d、%lld），根据本地化规则处理字符编码，并进行动态类型检查，这些对于纯十进制整数读写来说是多余开销。

目标

使用最精简的底层字符输入输出函数（getchar 和 putchar），绕过所有格式化解析与缓冲同步，提供一套类型自适应、无外部状态依赖、可在 1 分钟内手工默写的快速 I/O 模板。

核心直觉

一个十进制整数在文本流中以字符序列的形式呈现，例如字符串 "-4028"。

1. 读入直觉：秦九韶算法（高位到低位）

字符从左往右依次到达。忽略正负号后，数值构建过程与多项式求值完全一致：

4028=((4×10+0)×10+2)×10+8 4028 = ((4 \times 10 + 0) \times 10 + 2) \times 10 + 8

因此，读入只需要做两件事：

  1. 不断读取字符，直到遇到第一个数字字符；在此过程中如果遇到负号 '-'，就记录符号标志 f=−1f = -1。
  2. 一旦进入数字区间，每读取一位字符 chch，就让已有结果乘以 1010 并加上 (ch−’0’)(ch - \text{'0'})，直到遇到下一个非数字字符（空格、换行或文件末尾）。

2. 输出直觉：递归调用栈（低位到高位转高位到低位）

对整数 xx 取模 x mod 10x \bmod 10 能剥离出最低位，除以 1010 可以移去最低位。但是字符输出流要求必须先输出高位、后输出低位。

常规方法需要开辟一个数组作为临时栈，将剥离出的各位压栈，再倒序弹出输出。然而，函数本身的调用栈就是最天然的后进先出（LIFO）结构：

  • 先递归处理高位：write(x / 10)
  • 递归返回时输出当前最低位：putchar(x % 10 + '0')

当递归到 x⩽9x \leqslant 9 时，满足基准条件直接输出最高位，然后层层返回依次输出后续低位。这种结构无需定义外部数组，无需维护指针，甚至能自动处理 x=0x = 0 的情况，代码仅有三行，心智负担几乎为零。

算法步骤

快读步骤 (read)

  1. 初始化累加变量 x=0x = 0，符号因子 f=1f = 1。
  2. 读取首个字符 ch=getchar()ch = \text{getchar}()。
  3. 循环判断：若 ch<’0’ch < \text{'0'} 或 ch>’9’ch > \text{'9'}，判断是否为负号；若是负号则设 f=−1f = -1；继续读取下一个字符。
  4. 循环判断：若 ch⩾’0’ch \geqslant \text{'0'} 且 ch⩽’9’ch \leqslant \text{'9'}，更新 x=x×10+(ch−’0’)x = x \times 10 + (ch - \text{'0'})，继续读取下一个字符。
  5. 将结果赋为 x×fx \times f 并完成赋值。

快写步骤 (write)

  1. 若 x<0x < 0，输出字符 '-'，并将 xx 置为其相反数 −x-x。
  2. 若 x>9x > 9，说明存在更高位，递归调用自身：write(x / 10)。
  3. 输出当前个位对应的 ASCII 字符：putchar(x % 10 + '0')。

算法证明

1. 读入正确性

设输入的一串数字字符为 ck,ck−1,…,c0c_k, c_{k-1}, \dots, c_0，其中 ci∈{0,1,…,9}c_i \in \{0, 1, \dots, 9\}。

在循环开始前，x0=0x_0 = 0。第 mm 次循环更新规则为：

xm=xm−1⋅10+ck−m+1 x_m = x_{m-1} \cdot 10 + c_{k-m+1}

经数学归纳可知：

xk=∑i=0kci⋅10i x_k = \sum_{i=0}^k c_i \cdot 10^i

乘上符号因子 ff 后，结果严格等于文本流所表示的十进制整数。

2. 递归输出正确性与终止性

终止性：每次递归调用入参为 ⌊x/10⌋\lfloor x / 10 \rfloor。对于任意整数 x⩾10x \geqslant 10，显然有 ⌊x/10⌋<x\lfloor x / 10 \rfloor < x。状态单调严格递减，至多经过 ⌊log⁡10x⌋\lfloor \log_{10} x \rfloor 次调用必达到基准状态 x∈[0,9]x \in [0, 9]，递归必在有限步内终止。

输出顺序：

  • 对于 x∈[0,9]x \in [0, 9]，直接执行 putchar(x + '0')，正确输出。
  • 对于 x⩾10x \geqslant 10，由归纳假设，write(x / 10) 率先正确输出除个位外的所有前缀高位。待该子任务全部输出完毕后，程序执行下一行 putchar(x % 10 + '0')，精准拼接上最后一位。因此输出顺序与十进制表示完全一致。

栈深度安全性：对于 64 位有符号整型 long long，最大值约为 9.22×10189.22 \times 10^{18}，十进制位数不超过 1919。最大递归深度至多为 1919 层，函数调用开销微乎其微，绝不会导致栈溢出。

复杂度分析

  • 时间复杂度：
    • 单个数值读入与输出的时间复杂度均为 O(log⁡10∣x∣)O(\log_{10} |x|)，即与该数值的十进制位数呈线性关系。对于固定位宽的整型（int、long long），可以视为常数时间 O(1)O(1)。
    • 读取或输出 NN 个整数的总耗时为 O(N⋅L)O(N \cdot L)，其中 LL 为平均十进制位数，达到理论最优的字符流处理下界。
  • 空间复杂度：
    • 读入操作仅使用固定辅助变量，额外空间复杂度为 O(1)O(1)。
    • 递归输出的系统调用栈深度为 O(log⁡10∣x∣)⩽19O(\log_{10} |x|) \leqslant 19，额外空间复杂度为 O(log⁡10∣x∣)O(\log_{10} |x|)，属于微小常量级开销。

代码模板

下面的模板提供了竞赛中开箱即用的极简快速输入输出封装。

C++

C++ 版本使用模板函数实现泛型支持，同时利用 C++11 可变参数模板折叠展开，支持一条语句连续读取多个变量（如 read(n, m, k)）。

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

        #include <cstdio>
#include <cctype>

/**
 * 竞赛极简快速输入输出模板 (Fast I/O)
 *
 * 核心特点：
 * 1. 结构对称：read() 先滤非数字、再算十进制；write() 先判负、再递归除 10 输出。
 * 2. 极度精简：无需开外层栈数组与维护指针，代码行数极少，可在 1 分钟内手工默写。
 * 3. 泛型适配：支持 int、long long、__int128 等所有整型类型，支持单行多变量读入。
 */

// 快速读入：支持所有有符号与无符号整型
template <typename T>
inline void read(T &x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    // 过滤空白字符并识别负号
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    // 秦九韶算法累加各位数值
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    x *= f;
}

// 可变参数快速读入：一条语句读取多个变量，如 read(n, m, k)
template <typename T, typename... Args>
inline void read(T &x, Args &...args) {
    read(x);
    read(args...);
}

// 快速输出：利用递归栈自动倒序输出各位数字
template <typename T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

// 快捷带后缀字符输出（如空格、换行符）
template <typename T>
inline void write(T x, char end) {
    write(x);
    putchar(end);
}

// 快捷带换行输出
template <typename T>
inline void writeln(T x) {
    write(x);
    putchar('\n');
}
Python

Python 在处理大规模输入输出时，使用 sys.stdin.read().split() 将文本全量载入内存拆分为 Token，辅以 sys.stdout.write 消除逐项输出开销。

python 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

        import sys

"""
Python 竞赛极简快速输入输出 (Fast I/O)

核心特点：
1. sys.stdin.read().split() 一次性将全部输入读入内存并按空白切分，避免循环调用 input()。
2. sys.stdout.write 替代自带多重格式化与参数检查的 print()。
"""

# 一次性读取全部输入并按空格/换行拆分为 Token 列表
def load_all_tokens():
    return sys.stdin.read().split()

# 基于单行的高速输入（适用于内存严格或交互题场景）
readline = sys.stdin.readline

# 高速单值输出并追加指定分隔符（默认换行）
def write(val, end="\n"):
    sys.stdout.write(str(val) + end)

代码实现

以下提供一份完整的测试程序。程序首先读取整数 nn，随后读取 nn 个可能包含负数的整数，计算并输出其前缀和序列。

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
56
57
58
59
60
61
62

        #include <cstdio>

// ==================== 快读快写模板 ====================

template <typename T>
inline void read(T &x) {
    x = 0;
    T f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = x * 10 + (ch - '0');
        ch = getchar();
    }
    x *= f;
}

template <typename T, typename... Args>
inline void read(T &x, Args &...args) {
    read(x);
    read(args...);
}

template <typename T>
inline void write(T x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}

template <typename T>
inline void write(T x, char end) {
    write(x);
    putchar(end);
}

template <typename T>
inline void writeln(T x) {
    write(x);
    putchar('\n');
}

// ==================== 业务逻辑 ====================

int main() {
    int n;
    read(n);
    long long sum = 0;
    for (int i = 0; i < n; ++i) {
        long long val;
        read(val);
        sum += val;
        write(sum, i == n - 1 ? '\n' : ' ');
    }
    return 0;
}
Python
python 
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

        import sys

def main():
    tokens = sys.stdin.read().split()
    if not tokens:
        return
    n = int(tokens[0])
    cur_sum = 0
    res = []
    for i in range(1, n + 1):
        cur_sum += int(tokens[i])
        res.append(str(cur_sum))
    sys.stdout.write(" ".join(res) + "\n")

if __name__ == "__main__":
    main()

测试用例

用例一：一般混合情况（正负数与多空格）

输入：

5
10   -2
3 0 -5

输出：

10 8 11 11 6

过程分析：

  1. 读入 n=5n = 5。
  2. 依次读取各个数值，中间的连续空格与换行被前导循环自动过滤。
  3. 负数正确捕获符号因子，0 正确保留。
  4. 前缀和依次为 1010、10+(−2)=810 + (-2) = 8、8+3=118 + 3 = 11、11+0=1111 + 0 = 11、11+(−5)=611 + (-5) = 6。

用例二：单元素为 0

输入：

1
0

输出：

0

过程分析：

  • 读入阶段：ch = '0' 直接进入数字读取循环，x=0x = 0，0×1=00 \times 1 = 0。
  • 输出阶段：x=0x = 0，不满足 x<0x < 0 与 x>9x > 9，直接输出 0 + '0' = '0'。完美处理了边界零值。

应用分类详解

快速 I/O 的应用本质是：根据题目给定的数据规模与时间限制，选择性价比最高、心智负担适宜的输入输出优化方案。

数据吞吐量选择阶梯:
  N <= 10^4              -> 默认 std::cin / std::cout 或 scanf / printf
  10^4 < N <= 10^5       -> 关闭流同步: ios::sync_with_stdio(0); cin.tie(0);
  10^5 < N <= 10^6       -> 竞赛极简快读快写 (getchar / putchar)
  N > 10^6 (极端卡常题)   -> 块缓冲快读快写 (fread / fwrite)

一、基础阶梯：标准流解绑

典型模式： 数据量 N⩽105N \leqslant 10^5，题目时限较为充裕（如 1.0s），题面没有极度严苛的卡常标记。
识别信号： 常规图论、动态规划、字符串题目。
核心建模： 在 main() 函数开头直接解绑流同步与关联，继续书写熟悉的 cin >> x 与 cout << x << '\n'。

cpp 
        
1
2

        std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);

二、竞赛首选：字符级极简快读快写（本模板）

典型模式： 输入规模 N∈[105,2×106]N \in [10^5, 2 \times 10^6]，或者涉及频繁询问（如树状数组、线段树、ST 表、莫队算法等）。
识别信号：

  1. 题目包含大规模数组输入，如数论筛法打表查询、树上多组点对查询。
  2. 纯整数读入量极大，提交时偶发接近时限的超时（TLE）。
    核心建模： 默写 15 行内的 read 和 3 行递归 write，使用一条语句批量读入，将 I/O 耗时压减至原先的 1/3∼1/51/3 \sim 1/5。
应用场景 典型特征 优势
ST 稀疏表高频查询 10510^5 规模数组，10610^6 次区间极值询问 避免每一次查询输出被格式化拖垮
树状数组 / 线段树 高频修改与查询指令混合输入 连续读入数字不卡常
图论建图输入 M⩾106M \geqslant 10^6 条边读入 大幅缩短建图前置耗时

三、极限阶梯：块缓冲 I/O（fread / fwrite）

典型模式： 极端数据量 N⩾5×106N \geqslant 5 \times 10^6 甚至达到几千万字节（几百 MB）的特殊卡常题或大厂压测赛题。
识别信号： 题面特别注明“本题输入量巨大，请使用极速读入”，时限卡在 0.2s ~ 0.5s 极限边缘。
核心建模： 开辟 1∼4 MB1 \sim 4\text{ MB} 的大数组，通过系统调用 fread 一次性整块加载，指针内部滑动自增。因为该方案代码繁冗、调试时容易吞字符且不易默写，仅在常规快读无法通过时作为秘密武器使用。

经典例题

1. 洛谷 P1001 A+B Problem

  • 链接：Luogu P1001
  • 题目简述：输入两个整数 AA 和 BB（可能为负数），输出它们的和。
  • 练习重点：
    • 检验快读对负数的处理是否正确（验证符号标记因子 ff）。
    • 检验快写对负数结果是否正确输出负号。
    • 是测试新写模板最轻便的沙盒题目。

2. 洛谷 P3865 【模板】ST 表

  • 链接：Luogu P3865
  • 题目简述：给定 N⩽105N \leqslant 10^5 个数的序列，进行 M⩽2×106M \leqslant 2 \times 10^6 次静态区间最大值查询。
  • 重点分析：
    • 本题是经典的“计算只需 O(1)O(1)，瓶颈全在 I/O”的典型案例。
    • M=2×106M = 2 \times 10^6 次询问意味着输出量高达两百万行。直接使用 std::cout << ans << std::endl 会严重超时；即使关闭同步，流输出开销依然显著。
    • 使用本章的递归快写 write(ans); putchar('\n'); 能轻松跑进题目时间限制的一半以内。

3. 洛谷 P1908 逆序对

  • 链接：Luogu P1908
  • 题目简述：给定长度为 N⩽5×105N \leqslant 5 \times 10^5 的数组，求序列中逆序对的总数。
  • 重点分析：
    • 逆序对总数最大可达到 N(N−1)2≈1.25×1011\frac{N(N-1)}{2} \approx 1.25 \times 10^{11}，必须使用 long long 保存结果。
    • 本题能直接检验快读泛型模板 read(n) 以及递归快写 write(ans) 对 long long 类型的天然无缝支持。

避坑指南与技巧

严禁混用标准流与 C 字符接口

如果在程序开头执行了 std::ios::sync_with_stdio(false)，绝对不能在后续代码中将 std::cin / std::cout 与 getchar / putchar / scanf / printf 混合使用。关闭同步后，C++ 流与 C 缓冲池完全脱钩，混用会导致输入乱序、字符遗失或不可预知的未定义行为。

别忘了输出分隔符

本模板的 write(x) 函数只负责打印数字本身，不会自动附加空格或换行符。需要多数字同行或换行展示时，请使用 write(x, ' ')、write(x, '\n') 或 writeln(x)。

极端边界：最小值取相反数

对于有符号整型，负数绝对值比正数多 1（例如 32 位有符号整型的范围为 [−231,231−1][-2^{31}, 2^{31}-1]）。在极端情况下，如果输入恰好是最小值（如 INT_MIN），执行 x = -x 会发生有符号整型溢出。在普通算法竞赛中极少有数据正好卡在这一单点；若遇此极端测试点，只需将变量类型扩展为 long long 或改用无符号类型接收即可。

参考

  • 本文算法基于经典的秦九韶算法与十进制字符流状态机模型。
  • 更多通用竞赛代码骨架与调试工具，请参阅本书工具与附录章节。