1. 项目概述从一道竞赛题看C序列处理的精髓最近在整理厦门小学生C竞赛的历年真题2022年的这道“序列问题”让我眼前一亮。题目编号B4153标签是“普及”这意味着它已经超出了基础语法的范畴开始真正考验选手对数据结构和算法的理解与应用能力。很多刚接触竞赛的孩子一看到“序列”两个字可能就懵了脑子里会冒出“序列化”、“子序列”等各种概念。但竞赛题里的“序列”通常就是指一个按顺序排列的数据集合比如一个整数数组[1, 5, 3, 4, 2]。这道题的核心就是考察你如何高效地操作和处理这样一个序列去解决一个特定的问题。我之所以觉得这道题值得深挖是因为它像一把钥匙能打开C算法学习中好几扇重要的大门。它不像单纯求最大值、最小值那么简单往往需要你综合运用循环、条件判断甚至可能涉及到排序、查找等基础算法思想。对于目标是“普及”级别相当于NOIP普及组提高难度的选手来说这类题目是绝佳的练兵场。它训练的不是死记硬背代码而是分析问题、设计解决方案的计算思维。接下来我们就一起拆解这道题看看如何从题目描述出发一步步推导出高效、正确的C代码并在这个过程中把相关的核心知识点都捋清楚。2. 核心需求解析与问题建模首先我们必须明确在没有原题具体描述的情况下我们需要基于“序列问题”这个标题和“普及”的难度标签构建一个合理且具有代表性的问题模型。这本身就是一项重要的能力——通过有限信息推断核心考点。根据常见的竞赛题型“序列问题”通常围绕以下几个核心需求展开查询询问序列中某个位置的值、某个值的出现次数、某个区间内的统计信息如和、最大值、最小值。修改对序列中某个位置的值进行更新或者对某个区间内的所有值进行统一操作如增加一个固定值。变换根据特定规则重新排列或计算序列例如寻找最长上升子序列、计算逆序对数量、执行某种排序操作。判定判断序列是否满足某种性质例如是否为回文序列、是否有序等。对于“普及”难度题目不太可能涉及需要高级数据结构如线段树、树状数组才能高效解决的复杂区间操作。更可能的是它考察对基础算法的巧妙组合和优化。一个非常典型且符合该难度的模型是给定一个整数序列进行一系列操作最终输出序列的某种状态或计算结果。操作可能混合了上述的查询和修改。这里我们构建一个具体的问题实例用于后续讲解有一个长度为 N 的整数序列 A。初始时序列给定。接下来有 M 次操作操作分为两种类型1 x y将序列中第 x 个元素的值修改为 y。2 L R查询序列中从第 L 个到第 R 个元素包含两端这个子序列中不同数字的个数。 最终需要输出所有类型2操作查询结果的和。这个问题模型涵盖了序列的单点修改和区间查询查询的内容不同数字个数有一定技巧性非常适合“普及”级别。它要求选手不仅会写循环还要思考如何避免低效算法导致超时。2.1 从暴力法到优化思路面对这个问题最直观的暴力思路是存储用一个数组a[N1]存储序列。修改类型1直接a[x] y时间复杂度 O(1)。查询类型2遍历a[L]到a[R]用一个集合如bool标记数组或set来统计出现过的数字最后返回集合大小。时间复杂度 O(R-L1)在最坏情况下每次查询都查整个序列为 O(N)。如果 N 和 M 都很大比如达到 10^5 级别那么 M 次查询的總時間複雜度可能高達 O(M*N)這必然會超時。這就引出了我們的第一個優化思考能否將查詢的複雜度降低對於統計區間內不同數字個數一個常見的優化技巧是使用“離線處理”配合“樹狀數組”或“莫隊算法”。但考慮到“普及”的定位更可能期望的解法是對暴力法進行“剪枝”或利用“預處理”。然而仔細分析後會發現單純預處理很難應對單點修改。這時我們需要重新審視題目可能的數據範圍。如果 N 和 M 較小比如 ≤ 2000那麼 O(M*N) 的暴力法或許是可接受的。但“普及”通常會卡掉純暴力引導選手尋找更優解。另一條思路是注意到“不同數字個數”這個查詢。如果我們能快速知道某個值在序列中出現的情況或許能簡化計算。但這仍然困難。因此一個更合理的推測是原題B4153的查詢操作可能比“統計不同數字”更簡單例如查詢區間和、區間最大值等這樣就可以使用“前綴和”或“ST表”在 O(1) 或 O(log N) 內回答查詢並且能較好地與單點修改結合雖然前綴和面對修改需要 O(N) 更新但若修改操作很少亦可接受。為了兼顧教學意義和覆蓋核心考點我們將問題模型調整為一個更經典且更具教學意義的版本它同樣符合“序列問題”的範疇有一個長度為 N 的整數序列 A。初始時序列給定。接下來有 M 次操作操作分為兩種類型1 x y將序列中第 x 個元素的值修改為 y。2 L R查詢序列中從第 L 個到第 R 個元素這個子序列的最大值。 對於每個類型2操作輸出查詢結果。這個問題清晰地引入了“區間最值查詢”這個經典問題。我們將基於這個模型展開後續的詳細解析。這要求選手掌握以下核心知識點數組的基本操作、循環與條件判斷、函數的封裝以及更重要的——對時間複雜度的分析和對基礎數據結構的應用。3. 核心算法與數據結構選型確定了問題模型單點修改、區間最值查詢後我們需要選擇合適的數據結構和算法來實現它。不同的選擇對應著不同的時間複雜度和編碼難度這也是競賽題目的核心考察點。3.1 方案一暴力查詢法這是最直接的方法。存儲使用數組int a[N1];。修改a[x] y;查詢遍歷區間[L, R]用一個變量max_val記錄最大值並返回。int query_max(int L, int R, int a[]) { int max_val a[L]; // 初始化為區間第一個元素 for (int i L 1; i R; i) { if (a[i] max_val) { max_val a[i]; } } return max_val; }時間複雜度分析單點修改O(1)區間查詢O(K)其中 K R-L1 為區間長度。總體設有 M 次操作其中 Q 次是查詢操作。在最壞情況下每次查詢都遍歷整個序列K N總時間複雜度為 O(Q * N)。適用場景與局限當 N 和 Q 都較小例如 ≤ 5000時該方法簡單有效代碼不易出錯。但一旦數據規模增大例如 N10^5, Q10^5那麼 O(10^10) 的操作數遠遠超出了普通計算機一秒內能處理的範圍約 10^8 次運算必然導致“時間超限”。這就迫使我們尋找更高效的算法。3.2 方案二分塊算法分塊是一種“優雅的暴力”它將序列分成若干個大小為sqrt(N)的塊。預處理計算出每個塊內的最大值存儲在數組block_max[]中。修改更新a[x]後同時更新a[x]所在塊的block_max需要重新掃描該塊。查詢若查詢區間[L, R]完全覆蓋若干個整塊則直接讀取這些塊的block_max。對於區間兩端可能不完整的“碎片”部分暴力掃描元素。時間複雜度分析預處理O(N)單點修改O(sqrt(N))因為需要重新計算一個塊的最大值。區間查詢O(sqrt(N))最多需要處理約 2*sqrt(N) 個元素兩端的碎片和 sqrt(N) 個整塊信息。總體O(M * sqrt(N))。當 N10^5 時sqrt(N)≈316M10^5 時總運算量約為 3e7在時間限制內通常是安全的。優缺點優點思想直觀比純暴力快得多。它平衡了修改和查詢的成本。在“普及”難度中實現分塊是一個不錯的挑戰能很好地鍛煉代碼組織能力。缺點效率不如線段樹或樹狀數組但對於本問題的模型足夠用。編碼複雜度中等。3.3 方案三線段樹線段樹是處理區間問題的“瑞士軍刀”它可以在 O(log N) 的時間內完成單點修改和區間查詢。核心思想將整個序列構建一棵二叉樹每個樹節點代表序列的一個區間並存儲該區間的統計信息這裡是最大值。根節點代表整個區間[1, N]其左右子節點分別代表左右半區間以此類推直到葉子節點代表單個元素。修改從根節點向下遞歸找到對應的葉子節點更新其值然後在回溯的過程中更新所有祖先節點的最大值。查詢給定區間[L, R]從根節點開始遞歸。如果當前節點代表的區間完全被[L, R]包含則直接返回該節點存儲的最大值如果完全不重疊則返回一個不影響結果的極小值如果部分重疊則分別查詢左右子樹並返回兩者結果的較大值。時間複雜度預處理建樹 O(N)單次修改和查詢均為 O(log N)。總體複雜度 O(M log N)效率極高。優缺點優點時間效率最高是解決此類問題的標準答案。缺點編碼複雜度最高遞歸思想需要時間理解調試相對困難。對於“普及”的小學生選手而言是一個很高的挑戰但並非不可能。很多優秀的小學生選手確實能掌握線段樹。注意在實際競賽中如果時間充裕且對線段樹有把握直接使用線段樹是最穩妥的。如果時間緊張或對線段樹不熟練分塊算法是一個可靠的備選方案。暴力法則僅在確認數據範圍很小時使用。考慮到教學的循序漸進和“普及”選手的普遍水平我們將以分塊算法作為本篇解析的重點實現方案。它既有足夠的優化效果其思想又比線段樹更容易理解和實現。我們會詳細闡述分塊的每一個步驟。4. 分塊算法詳細實現與代碼解析我們將按照“初始化分塊 - 實現修改操作 - 實現查詢操作”的順序一步步構建代碼。4.1 數據結構定義與初始化首先我們需要定義幾個全局數組和變量a[]存儲原始序列下標從1開始。block_max[]存儲每個塊內的最大值。belong[]記錄每個元素屬於哪一個塊。block_size每個塊的大小通常取sqrt(N)。block_num塊的總數。初始化過程建構包括計算塊大小和塊數量。確定每個元素所屬的塊。計算每個塊的最大值。#include iostream #include cmath #include algorithm #include climits using namespace std; const int MAXN 100010; // 根據題目可能的最大N設定 int a[MAXN]; // 原始序列 int block_max[MAXN]; // 每個塊的最大值 int belong[MAXN]; // 元素所屬的塊編號 int block_size, block_num; void build(int n) { block_size sqrt(n); // 塊大小取根號N block_num n / block_size; if (n % block_size ! 0) { block_num; // 最後一個塊可能不滿 } // 初始化每個塊的最大值為無窮小 for (int i 1; i block_num; i) { block_max[i] INT_MIN; } // 確定歸屬並計算塊最大值 for (int i 1; i n; i) { belong[i] (i - 1) / block_size 1; // 計算所屬塊編號 // 更新所屬塊的最大值 block_max[belong[i]] max(block_max[belong[i]], a[i]); } }實操心得belong[i] (i - 1) / block_size 1這個公式是分塊算法的核心之一務必理解。它將下標從1開始的元素均勻地映射到從1開始的塊編號上。INT_MIN來自climits頭文件代表整數的最小值用於初始化最大值。4.2 單點修改操作實現修改第x個元素的值為y。更新原始數組a[x] y。找到x所在的塊id belong[x]。由於該塊的最大值可能發生了變化需要重新掃描整個塊來計算新的最大值。這是分塊算法中修改操作的主要開銷所在。void update(int x, int y) { // 1. 更新原始數組 a[x] y; // 2. 找到所屬塊 int id belong[x]; // 3. 重新計算該塊的最大值 int start (id - 1) * block_size 1; // 該塊第一個元素的下標 int end min(id * block_size, (int)MAXN); // 該塊最後一個元素的下標注意邊界 // 重新初始化塊最大值 block_max[id] INT_MIN; for (int i start; i end i MAXN; i) { // 注意循環終止條件 // 這裡需要訪問a[i]所以要確保i在有效範圍內 // 實際上我們應該傳入序列總長度n這裡為簡化先這樣寫 block_max[id] max(block_max[id], a[i]); } }注意上面的update函數有一個問題它循環的終點end是通過id * block_size計算的可能超過序列的實際長度n也超過了數組a的定義範圍MAXN。在實際代碼中我們需要將序列長度n作為參數傳入或者作為全局變量。修正如下int n; // 序列實際長度應在main函數中讀入並設為全局變量 void update(int x, int y) { a[x] y; int id belong[x]; int start (id - 1) * block_size 1; int end min(id * block_size, n); // 修正結束下標不超過n block_max[id] INT_MIN; for (int i start; i end; i) { block_max[id] max(block_max[id], a[i]); } }4.3 區間查詢操作實現查詢區間[L, R]的最大值。這是分塊算法的精華所在需要處理三種情況L和R在同一個塊內直接暴力掃描區間[L, R]。L和R在不同塊內處理左端不完整的塊暴力掃描[L, 該塊結尾]。處理中間完整的若干個塊直接讀取這些塊的block_max值進行比較。處理右端不完整的塊暴力掃描[該塊開頭, R]。int query(int L, int R) { int ans INT_MIN; // 初始化答案為無窮小 int id_L belong[L], id_R belong[R]; // 情況1在同一塊內 if (id_L id_R) { for (int i L; i R; i) { ans max(ans, a[i]); } return ans; } // 情況2不在同一塊內 // 處理左端碎片 for (int i L; i id_L * block_size; i) { ans max(ans, a[i]); } // 處理中間完整塊 for (int i id_L 1; i id_R; i) { ans max(ans, block_max[i]); } // 處理右端碎片 for (int i (id_R - 1) * block_size 1; i R; i) { ans max(ans, a[i]); } return ans; }4.4 主程序邏輯與完整代碼框架現在我們將所有部分組合起來形成完整的程序框架。假設輸入格式為第一行兩個整數 N, M。第二行 N 個整數表示初始序列。接下來 M 行每行三個整數op, x, y。若op1則執行修改操作update(x, y)若op2則執行查詢操作query(x, y)並輸出結果。#include iostream #include cmath #include algorithm #include climits using namespace std; const int MAXN 100010; int a[MAXN]; int block_max[MAXN]; int belong[MAXN]; int block_size, block_num; int n, m; // 序列長度和操作次數 void build() { block_size sqrt(n); block_num n / block_size; if (n % block_size ! 0) block_num; for (int i 1; i block_num; i) block_max[i] INT_MIN; for (int i 1; i n; i) { belong[i] (i - 1) / block_size 1; block_max[belong[i]] max(block_max[belong[i]], a[i]); } } void update(int x, int y) { a[x] y; int id belong[x]; int start (id - 1) * block_size 1; int end min(id * block_size, n); block_max[id] INT_MIN; for (int i start; i end; i) { block_max[id] max(block_max[id], a[i]); } } int query(int L, int R) { int ans INT_MIN; int id_L belong[L], id_R belong[R]; if (id_L id_R) { for (int i L; i R; i) ans max(ans, a[i]); return ans; } for (int i L; i id_L * block_size; i) ans max(ans, a[i]); for (int i id_L 1; i id_R; i) ans max(ans, block_max[i]); for (int i (id_R - 1) * block_size 1; i R; i) ans max(ans, a[i]); return ans; } int main() { ios::sync_with_stdio(false); // 關閉同步加速cin/cout cin.tie(0); cin n m; for (int i 1; i n; i) { cin a[i]; } build(); // 初始化分塊結構 while (m--) { int op, x, y; cin op x y; if (op 1) { update(x, y); } else if (op 2) { cout query(x, y) endl; } } return 0; }5. 時間複雜度分析與對比驗證我們已經實現了基於分塊的算法。現在來具體算一算為什麼它比暴力法快。假設序列長度 N 100,000操作次數 M 100,000。暴力法每次查詢最壞 O(N) 100,000。如果一半操作是查詢總時間複雜度約為 50,000 * 100,000 5e9 次運算。這在1秒的時間限制內通常評測機約為1e8次運算/秒是絕對無法完成的。分塊法塊大小block_size sqrt(100000) ≈ 316。單點修改update需要重新計算一個塊的最大值循環約316次複雜度 O(√N)。區間查詢query最壞情況下區間橫跨多個塊。兩端的“碎片”部分總長度不超過2 * block_size ≈ 632中間完整塊的數量約為N / block_size ≈ 316個但我們只是讀取其預先計算好的block_max值這部分是 O(塊數) ≈ O(√N)。所以查詢的複雜度也是 O(√N)。總操作複雜度O(M * √N) ≈ 100,000 * 316 ≈ 3.16e7 次運算。這個量級在1秒內是很有希望通過的。為了更直觀我們可以構建一個小規模的測試數據來驗證代碼的正確性並通過計時來感受效率差異雖然對於小數據差異不明顯。測試數據示例5 5 1 5 3 4 2 2 1 5 1 3 10 2 1 5 1 5 1 2 3 4程序運行過程初始序列[1, 5, 3, 4, 2]。查詢[1,5]最大值輸出5。修改a[3] 10序列變為[1, 5, 10, 4, 2]。查詢[1,5]最大值輸出10。修改a[5] 1序列變為[1, 5, 10, 4, 1]。查詢[3,4]最大值輸出10。通過這個簡單測試可以驗證我們的分塊算法邏輯是正確的。6. 常見問題與調試技巧在實現分塊算法的過程中初學者很容易遇到一些問題。這裡我總結了幾個常見的“坑”和調試技巧。6.1 數組下標越界這是分塊算法中最常見的錯誤尤其是在計算塊的起止下標和循環終止條件時。belong數組計算錯誤公式(i-1)/block_size 1是標準寫法確保下標從1開始。如果從0開始存儲公式應為i/block_size但需要處理整除邊界更麻煩。建議序列下標統一從1開始。update函數中循環終點錯誤如前所述end id * block_size可能超過n必須用min(id * block_size, n)來限制。query函數中碎片處理的循環條件錯誤左端碎片循環終點是id_L * block_size但這個值可能超過n。不過由於L和R本身是合法的輸入1 ≤ L ≤ R ≤ n且L一定在id_L塊內所以id_L * block_size可能大於n嗎會如果最後一個塊不滿id_L恰好是最後一個塊時id_L * block_size就大於n。因此更嚴謹的左端碎片循環應寫成for (int i L; i min(id_L * block_size, n); i)。但在我們的query函數中由於R是合法的且id_L id_R時我們才處理左端碎片此時id_L塊一定不是最後一個塊因為後面還有id_R塊所以id_L * block_size不會超過n。這是一個需要仔細推敲的邊界。安全起見在碎片循環中也加上min限制是更好的習慣。調試技巧當程序出現“段錯誤”或讀取到詭異值時首先檢查所有數組訪問的下標是否在聲明的範圍內1到n或1到block_num。可以在關鍵代碼處添加cout輸出下標值或者使用調試器觀察。6.2 最大值初始化問題在build和update函數中我們需要將block_max[id]初始化為一個極小值然後用max函數更新。這個極小值必須小於序列中任何可能的值。如果序列值範圍是-10^9到10^9使用INT_MIN約為 -2e9是安全的。如果題目沒有說明或者值域可能小於INT_MIN則需要根據題目條件自己設定一個足夠小的值例如-1e18。絕對不要初始化為0如果序列全是負數結果就會出錯。6.3 分塊大小選擇的影響我們通常取block_size sqrt(n)。這是一個經驗值能在修改和查詢之間取得較好的平衡。如果block_size過小比如設為1那麼塊的數量就等於n。此時查詢中間完整塊時需要遍歷block_max數組的很多項退化為近似 O(N) 的複雜度。如果block_size過大比如設為n那麼整個序列就是一個塊。每次修改都需要重新計算整個序列的最大值也退化為 O(N)。sqrt(n)是一個理論上的最優平衡點。在實際競賽中有時微調塊大小例如sqrt(n) 1或sqrt(n) * 2可能會因為常數因子而獲得稍好的性能但sqrt(n)在絕大多數情況下都是可靠且高效的選擇。6.4 查詢操作中同一塊內的優化在我們的query函數中對於L和R在同一塊的情況我們使用了暴力掃描。這在區間長度接近塊大小時是合理的。但如果這種查詢很多且區間通常很短這樣做沒有問題。如果同一塊內的查詢區間很長暴力掃描也是 O(塊大小) ≈ O(√N)與分塊的設計目標一致。7. 從分塊到線段樹思維的躍遷雖然分塊算法已經能解決這道題但作為一名有追求的選手了解更強大的工具——線段樹是必要的。線段樹將查詢和修改的時間複雜度都降到了 O(log N)對於 N 和 M 達到 10^6 級別的題目也能遊刃有餘。線段樹的實現比分塊複雜但其核心思想優美任何一個區間都可以被拆分成線段樹上不超過 O(log N) 個節點的並集。實現線段樹通常有遞歸和迭代兩種方式遞歸方式更直觀。下面給出解決本問題單點修改區間求最大值的遞歸版線段樹核心代碼框架作為對比和延伸學習#include iostream #include algorithm #include climits using namespace std; const int MAXN 100010; int a[MAXN]; int tree[4 * MAXN]; // 線段樹數組大小通常開4倍原數組 // 建樹節點rt代表區間[l, r] void build(int rt, int l, int r) { if (l r) { tree[rt] a[l]; return; } int mid (l r) / 2; build(rt * 2, l, mid); // 遞歸構建左子樹 build(rt * 2 1, mid 1, r); // 遞歸構建右子樹 tree[rt] max(tree[rt * 2], tree[rt * 2 1]); // 更新當前節點最大值 } // 將位置pos的值更新為val void update(int rt, int l, int r, int pos, int val) { if (l r) { tree[rt] val; return; } int mid (l r) / 2; if (pos mid) { update(rt * 2, l, mid, pos, val); } else { update(rt * 2 1, mid 1, r, pos, val); } tree[rt] max(tree[rt * 2], tree[rt * 2 1]); // 回溯更新 } // 查詢區間[L, R]的最大值 int query(int rt, int l, int r, int L, int R) { if (L l r R) { return tree[rt]; // 當前區間完全包含在查詢區間內 } int mid (l r) / 2; int ans INT_MIN; if (L mid) { ans max(ans, query(rt * 2, l, mid, L, R)); } if (R mid) { ans max(ans, query(rt * 2 1, mid 1, r, L, R)); } return ans; } int main() { int n, m; cin n m; for (int i 1; i n; i) cin a[i]; build(1, 1, n); // 從根節點編號1開始建樹對應區間[1, n] while (m--) { int op, x, y; cin op x y; if (op 1) { update(1, 1, n, x, y); a[x] y; // 別忘了更新原數組雖然線段樹查詢不直接用它 } else { cout query(1, 1, n, x, y) endl; } } return 0; }線段樹要點tree數組大小要開足夠一般為4 * MAXN。遞歸函數的參數通常包含當前節點編號rt當前節點代表的區間[l, r]以及操作目標更新位置pos或查詢區間[L, R]。build和update在遞歸返回時都需要用子節點的信息更新父節點tree[rt] max(...)。query函數中如果當前區間[l, r]完全包含於查詢區間[L, R]則直接返回該節點值否則根據查詢區間與中點mid的關係遞歸查詢左右子樹。從分塊到線段樹是算法能力的一次重要提升。建議先徹底理解並能獨立實現分塊算法再挑戰線段樹。當你能夠熟練運用線段樹時你會發現很多複雜的區間問題都變得清晰起來。8. 總結與擴展思考回顧我們對“B4153 序列問題”的整個拆解過程我們從一個抽象的標題出發構建了一個具體的“單點修改、區間求最大值”的問題模型。我們詳細分析了暴力法、分塊法和線段樹三種解決方案並重點實現了適合“普及”難度的分塊算法。我們不僅給出了代碼還深入分析了時間複雜度、邊界條件和常見錯誤。這道題的價值在於它是一個範例教會我們面對序列問題時的基本思考路徑理解操作明確題目對序列有哪些操作查詢、修改。分析數據範圍這是選擇算法的關鍵。數據範圍決定了暴力法是否可行。選擇數據結構根據操作類型和數據範圍選擇合適的數據結構數組、分塊、線段樹、樹狀數組等。實現與優化編寫代碼並注意邊界條件和效率優化。測試與調試用樣例和邊界數據測試程序。這道題還可以有很多變種例如區間求和只需將代碼中的max改為sumblock_max改為block_sum。查詢時中間完整塊直接加block_sum兩端碎片暴力加元素值。區間內某個數的出現次數這就回到了我們最初構想的“不同數字個數”的簡化版。如果數字範圍不大可以為每個塊維護一個計數數組。修改時更新兩個塊的計數查詢時合併計數數組。這就比單純求最值複雜一些。混合操作同時存在區間加法和區間查詢。這就需要在分塊中引入“懶標記”的概念或者在線段樹中實現“懶惰傳播”。我個人在帶學生訓練時發現很多孩子卡在“序列問題”上不是因為不會寫循環而是缺乏這種“問題建模”和“算法選型”的意識。他們習慣於看到題目就想著套用某個固定的代碼模板而忽視了對題目本質的分析。這道題正好是一個絕佳的練習讓孩子們明白編程解決問題首先是想清楚怎麼做然後才是用代碼實現。分塊算法就是這個“想清楚”過程中的一座很好的橋樑它既有一定的技巧性又不至於像線段樹那樣讓初學者望而生畏。把這道題吃透再遇到其他序列處理的題目思路就會開闊很多。