简单有效的优化手段。
Login to join training plan
【复制自洛谷】
荀子曰：不积跬步，无以至千里；不积小流，无以成江海。这句话揭示了世间万物整体和部 分之间的关系——庞大的整体由若干个体组成；单个个体虽小，但经过一点一滴的累积，也能聚 成一个庞大的整体。学习工作贵在不断积累，不断充实、丰富、完善自己，所有的努力都会有回报。
在算法竞赛中，利用整体和部分的性质可以达成很多目的，例如利用前缀和可以在常数时间 复杂度中查询区间和，利用差分在常数时间复杂度对序列进行区间操作，或者利用离散化去除无用数据区间，通过放缩保留有用的数据。这些操作使得我们不必每次都要重复处理个体的数据，而是直接对整体进行处理，从而降低时间复杂度，提升运算效率。这一章将会学习前缀和、差分和离散化的思想，并使用这些思想完成一些简单的任务。
Section 1. 前缀和
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P8218 【深进1.例1】求区间和 | 107 | 52 | 4 |
| A1472 子矩阵的元素之和 | 78 | 38 | 4 |
| P2004 领地选择 | 117 | 17 | 8 |
| P2280 [HNOI2003] 激光炸弹 | 194 | 16 | 9 |
| P5745 【深基附B例】区间最大和 | 45 | 7 | 8 |
Section 2. 差分
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| P2367 语文成绩 | 150 | 43 | 6 |
| P3406 海底高铁 | 70 | 18 | 7 |
| P4552 [Poetize6] IncDec Sequence | 59 | 11 | 8 |
| P2879 [USACO07JAN] Tallest Cow S | 27 | 8 | 7 |
Section 3. 离散化
Open
| Problem | Tried | AC | Difficulty |
|---|---|---|---|
| B3694 数列离散化 | 25 | 12 | 5 |
| A1486 区间和 | 12 | 2 | 10 |
| P1496 火烧赤壁 | 28 | 9 | 7 |
