原文

https://www.beiweidoge.top/132.html

P1：求最大值1

題目描述

題目描述
小明給了你n個數字，你需要依次輸出：

• 1到n的最大值，
• 1到n/2的最大值，n/2+1到n的最大值，
• 1到n/4的最大值，n/4+1到n/2的最大值，……
  ……
  確保n是2的冪次。
  輸入
• 第一行一個整數n（n < 2e5），
• 第二行n個整數ai。
  輸出
  一共輸出2^n-1個答案。
  樣例輸入

16  
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16  

樣例輸出

16 8 16 4 8 12 16 2 4 6 8 10 12 14 16  

輸出說明
輸出的順序是：

1. 第1層：整個區間的最大值（1-16 → 16），
2. 第2層：左半區間的最大值（1-8 → 8）和右半區間的最大值（9-16 → 16），
3. 第3層：將第2層的兩個區間再分別分成兩半，得到4個區間的最大值（1-4→4, 5-8→8, 9-12→12, 13-16→16），
4. 第4層：繼續二分，直到區間長度為1（此時輸出原數列本身）。
   輸出的順序是按層次遍歷（BFS）的順序。

解題思路

1. 問題分析：
   • 題目要求我們按照層次遍歷（BFS）的順序輸出一個完全二叉樹的節點值，其中每個節點的值表示對應區間的最大值。
   • 輸入保證 n 是 2 的冪次，因此可以完美地構建一棵完全二叉樹，每個非葉子節點的區間都是其左右子節點區間的并集。
2. 數據結構選擇：
   • 使用線段樹（Segment Tree）來高效地存儲和查詢區間最大值。
   • 線段樹的每個節點存儲對應區間的最大值，構建過程是遞歸的（DFS），但輸出順序需要按層次遍歷（BFS）。
3. 構建線段樹：
   • 遞歸地構建線段樹：
     • 葉子節點直接存儲數組元素的值。
     • 非葉子節點的值為其左右子節點值的最大值。
   • 遞歸函數 dfs(t, w, x)：
     • t 和 w 表示當前區間的左右端點。
     • x 表示當前節點在線段樹數組中的索引。
4. 層次遍歷輸出：
   • 線段樹的存儲方式是數組形式，其中索引為 i 的節點的左孩子是 2*i，右孩子是 2*i+1。
   • 直接遍歷線段樹數組的前 n-1 個節點（因為線段樹的總節點數為 2n-1，但題目只需要輸出前 n 層的節點值）。
5. 時間復雜度：
   • 構建線段樹的時間復雜度為 O(n)。
   • 輸出結果的時間復雜度為 O(n)。
   • 總時間復雜度為 O(n)，滿足題目約束（n < 2e5）。
6. 關鍵點：
   • 線段樹的構建和查詢是解決區間問題的經典方法。
   • 層次遍歷的順序直接對應線段樹數組的存儲順序（按索引從小到大）。

標準程序

#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int i,n,a[N],f[N*4];
void dfs(int t,int w,int x){int mid;if(t==w){f[x]=a[t];return;}mid=(t+w)/2;dfs(t,mid,x*2);dfs(mid+1,w,x*2+1);f[x]=max(f[x*2],f[x*2+1]);
}
int main(){cin>>n;for(i=1;i<=n;i++) cin>>a[i];dfs(1,n,1);for(i=1;i<n;i++) cout<<f[i]<<" ";
}

P2：求最大值2

題目描述

題目描述
小明給了你n個數字，接下來他會提出m個詢問。每個詢問會給出一個區間范圍，你需要回答這個區間內的最大值是多少。
輸入格式：

• 第一行兩個整數n和m（1 ≤ n, m ≤ 1e5）
• 第二行n個整數，表示初始的n個數字
• 接下來m行，每行三個整數x,y,z：
  • 當x=0時，表示詢問區間[y,z]內的最大值
  • 當x=1時，表示將第y個數字修改為z（本題中x只會是0）
    輸出格式：
• 對于每個x=0的詢問，輸出一行表示區間[y,z]的最大值
  樣例輸入：

5 6
1 2 3 4 5
0 1 5
0 1 5
0 2 4
0 3 1
0 4 4
0 5 1

樣例輸出：

5
5
4
3
4
5

數據范圍：

• 所有數字都在int范圍內
• 保證y和z在有效范圍內（1 ≤ y ≤ z ≤ n）

解題思路

1. 問題分析：
   • 題目要求高效處理多個區間最大值查詢（Range Maximum Query, RMQ）。
   • 直接暴力遍歷每次查詢區間的時間復雜度是O(n)，對于m次查詢總復雜度O(mn)會超時（n,m≤1e5）。
2. 數據結構選擇：
   • 使用線段樹（Segment Tree）來預處理數據，支持高效的區間查詢。
   • 線段樹可以在O(n)時間預處理，O(logn)時間回答每個查詢。
3. 線段樹構建：
   • 遞歸構建線段樹，每個節點存儲對應區間的最大值。
   • 葉子節點直接存儲數組元素值。
   • 非葉子節點的值為其左右子節點值的最大值。
4. 查詢處理：
   • 對于查詢區間[y,z]，從根節點開始遞歸查詢：
     • 如果當前節點區間完全包含在查詢區間內，直接返回該節點存儲的最大值。
     • 如果與查詢區間無交集，返回極小值。
     • 否則遞歸查詢左右子樹，取兩者的最大值。
5. 邊界處理：
   • 當y>z時交換y和z（保證區間有效）。
   • 使用快速輸入輸出優化（ios::sync_with_stdio(false)）來加速大量數據的處理。
6. 時間復雜度：
   • 預處理：O(n)
   • 單次查詢：O(logn)
   • 總體復雜度：O(n + mlogn)，完全滿足題目要求。
7. 空間復雜度：
   • 線段樹需要4n的空間，對于n≤1e5完全足夠。
8. 優化點：
   • 使用結構體存儲線段樹節點信息，代碼更清晰。
   • 遞歸實現簡潔易懂，適合競賽編程。
   • 輸入輸出優化對大規模數據很關鍵。

標準程序

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int i,n,m,x,y,z,a[N];
struct no{int t,w,x;}f[N*4];
void dfs(int t,int w,int x){int mid;f[x].t=t;f[x].w=w;if(t==w){f[x].x=a[t];return;}mid=(t+w)/2;dfs(t,mid,x*2);dfs(mid+1,w,x*2+1);f[x].x=max(f[x*2].x,f[x*2+1].x);
}
int check(int t,int w,int x){if(t<=f[x].t&&f[x].w<=w) return f[x].x;else if(f[x].w<t||w<f[x].t) return -2e9;else return max(check(t,w,x*2),check(t,w,x*2+1));
}
int main(){ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin>>n>>m;for(i=1;i<=n;i++) cin>>a[i];dfs(1,n,1);for(i=1;i<=m;i++){cin>>x>>y>>z;if(y>z) swap(y,z);cout<<check(y,z,1)<<"\n";}
}

P3：求最大值3

題目描述

題目描述
小明給了你n個數字，接下來他會提出m個操作。每個操作可能是查詢區間最大值，也可能是修改某個數字的值。
輸入格式：

• 第一行兩個整數n和m（1 ≤ n, m ≤ 1e5）
• 第二行n個整數ai，表示初始的n個數字
• 接下來m行，每行三個整數x,y,z：
  • 當x=0時，表示查詢區間[y,z]內的最大值
  • 當x=1時，表示將第y個數字修改為z
    輸出格式：
• 對于每個x=0的查詢操作，輸出一行表示區間[y,z]的最大值
  樣例輸入：

5 6
1 2 3 4 5
0 1 5
1 3 6
0 1 5
0 2 4
1 3 1
0 3 1

樣例輸出：

5
6
6
2

數據范圍：

• 所有數字都在int范圍內
• 保證y和z在有效范圍內（1 ≤ y ≤ z ≤ n）
• 修改操作保證y在有效范圍內（1 ≤ y ≤ n）

解題思路

解題思路

1. 問題分析：
   • 題目需要同時支持兩種操作：區間最大值查詢和單點修改
   • 直接暴力解法每次查詢O(n)，修改O(1)，總復雜度O(mn)會超時
   • 需要選擇支持高效查詢和修改的數據結構
2. 數據結構選擇：
   • 線段樹：支持O(logn)時間復雜度的區間查詢和單點修改
   • 相比RMQ更適合動態數據場景
   • 每個節點存儲對應區間的最大值
3. 線段樹實現：
   • 構建：遞歸構建線段樹，葉子節點存儲數組元素值，非葉子節點存儲子節點最大值
   • 查詢：遞歸查詢區間[y,z]，合并左右子樹結果
   • 修改：遞歸找到對應葉子節點，更新后回溯更新父節點最大值
4. 關鍵優化：
   • 使用結構體存儲節點信息（區間范圍、最大值）
   • 輸入輸出優化處理大數據量
   • 處理無效區間（y>z時交換）
5. 時間復雜度：
   • 預處理：O(n)
   • 查詢：O(logn)
   • 修改：O(logn)
   • 總體：O(n + mlogn)，完全滿足1e5數據規模
6. 空間復雜度：
   • 線段樹需要4n空間，對于n≤1e5足夠
7. 注意事項：
   • 修改操作需要從根節點遞歸更新到葉子節點
   • 查詢時要正確處理區間包含關系
   • 使用快速IO優化對大規模數據很關鍵

標準程序

#include <bits/stdc++.h>
using namespace std;
const int N=100010;
int i,n,m,x,y,z,a[N];
struct no{int t,w,x;}f[N*4];
void dfs(int t,int w,int x){int mid;f[x].t=t;f[x].w=w;if(t==w){f[x].x=a[t];return;}mid=(t+w)/2;dfs(t,mid,x*2);dfs(mid+1,w,x*2+1);f[x].x=max(f[x*2].x,f[x*2+1].x);
}
int check(int t,int w,int x){if(t<=f[x].t&&f[x].w<=w) return f[x].x;else if(f[x].w<t||w<f[x].t) return -2e9;else return max(check(t,w,x*2),check(t,w,x*2+1));
}
void change(int x,int y,int z){if(f[x].t==f[x].w){f[x].x=z;return;}if(y<=f[x*2].w) change(x*2,y,z);else change(x*2+1,y,z);f[x].x=max(f[x*2].x,f[x*2+1].x);
}
int main(){ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin>>n>>m;for(i=1;i<=n;i++) cin>>a[i];dfs(1,n,1);for(i=1;i<=m;i++){cin>>x>>y>>z;if(x==0){if(y>z) swap(y,z);cout<<check(y,z,1)<<"\n";}else change(1,y,z);}
}

P4：單點修改區間求和

題目描述

題目描述
給定一個初始全部為零的數列，需要支持兩種操作：修改某個元素的值，或查詢區間的連續和。
輸入格式：

• 第一行兩個正整數n和m（n ≤ 100000，m ≤ 100000）
• 接下來m行，每行三個正整數k,a,b：
  • 當k=0時，表示將第a個位置的數字增加b
  • 當k=1時，表示查詢區間[a,b]內所有數的和（不保證a≤b）
• 保證所有數據在long long范圍內
  輸出格式：
• 對于每個k=1的查詢操作，輸出一行表示區間和
  樣例輸入：

10 20
0 1 10
1 1 4
0 6 6
1 4 10
1 8 9
1 4 9
0 10 2
1 1 8
0 2 10
1 3 9
0 7 8
0 3 10
0 1 1
1 3 8
1 6 9
0 5 5
1 1 8
0 4 2
1 2 8
0 1 1

樣例輸出：

10
6
0
6
16
6
24
14
50
41

數據范圍：

• 1 ≤ n ≤ 1e5
• 1 ≤ m ≤ 1e5
• 修改操作：1 ≤ a ≤ n，b為long long范圍內的正整數
• 查詢操作：1 ≤ a,b ≤ n（a可能大于b）

解題思路

1. 問題分析：
   • 需要實現兩種操作：單點修改（增加某個位置的值）和區間求和查詢
   • 直接暴力解法每次查詢需要O(n)時間，無法處理1e5量級的數據
   • 需要選擇支持高效單點修改和區間查詢的數據結構
2. 數據結構選擇：
   • 線段樹：支持O(logn)時間復雜度的單點修改和區間查詢
   • 相比樹狀數組更直觀易懂，適合競賽使用
   • 每個節點存儲對應區間的和
3. 線段樹實現：
   • 初始化：遞歸構建線段樹，所有節點初始值為0
   • 單點修改：遞歸找到對應葉子節點，增加指定值后回溯更新父節點和
   • 區間查詢：遞歸查詢區間[y,z]，合并左右子樹結果
   • 無效區間處理：當y>z時交換y和z
4. 關鍵優化：
   • 使用結構體存儲節點信息（區間范圍、區間和）
   • 輸入輸出優化處理大數據量
   • 使用long long類型防止數據溢出
5. 時間復雜度：
   • 預處理：O(n)
   • 單次修改：O(logn)
   • 單次查詢：O(logn)
   • 總體：O(n + mlogn)，完全滿足1e5數據規模
6. 空間復雜度：
   • 線段樹需要4n空間，對于n≤1e5足夠
7. 注意事項：
   • 需要處理a>b的查詢情況
   • 修改是增加操作而非直接賦值
   • 所有操作都可能涉及大數，必須使用long long類型

標準程序

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=100010;
int i,n,m,x,y,z,a[N];
struct no{int t,w,x;}f[N*4];
void dfs(int t,int w,int x){int mid;f[x].t=t;f[x].w=w;if(t==w){f[x].x=0;return;}mid=(t+w)/2;dfs(t,mid,x*2);dfs(mid+1,w,x*2+1);f[x].x=f[x*2].x+f[x*2+1].x;
}
int check(int t,int w,int x){if(t<=f[x].t&&f[x].w<=w) return f[x].x;else if(f[x].w<t||w<f[x].t) return 0;else return check(t,w,x*2)+check(t,w,x*2+1);
}
void change(int x,int y,int z){if(f[x].t==f[x].w){f[x].x+=z;return;}if(y<=f[x*2].w) change(x*2,y,z);else change(x*2+1,y,z);f[x].x=f[x*2].x+f[x*2+1].x;
}
signed main(){ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin>>n>>m;dfs(1,n,1);for(i=1;i<=m;i++){cin>>x>>y>>z;if(x==0) change(1,y,z);else{if(y>z) swap(y,z);cout<<check(y,z,1)<<"\n";}}
}

P5：最大數

題目描述

題目描述
給定一個初始為空的整數序列，支持兩種操作：向序列末尾添加元素，或查詢序列最后L個元素中的最大值。添加操作的值會受到之前查詢結果的影響。
輸入格式：

• 第一行兩個正整數m和p，表示操作次數和模數
• 接下來m行，每行一個操作：
  • A t：向序列末尾添加一個數，值為(t + a) % p，其中a是上一次查詢的結果（初始為0）
  • Q L：查詢序列最后L個元素中的最大值
• 保證第一個操作一定是添加操作
• 保證查詢操作中的L不超過當前序列長度
  輸出格式：
• 對于每個Q L操作，輸出一行表示最后L個元素的最大值
  樣例輸入：

10 100
A 97
Q 1
Q 1
A 17
Q 2
A 63
Q 1
Q 1
Q 3
A 99

樣例輸出：

97
97
97
60
60
97

數據范圍：

• 1 ≤ m ≤ 2×10^5
• 1 ≤ p ≤ 2×10^9
• 0 ≤ t < p
• 查詢操作保證1 ≤ L ≤ 當前序列長度
  操作說明：

1. 序列初始為空
2. 添加操作的值計算：(輸入值t + 上次查詢結果a) % p
3. 第一個操作保證是添加操作
4. 查詢操作保證L合法

解題思路

1. 問題分析：
   • 需要維護一個動態增長的序列，支持快速查詢最后L個元素的最大值
   • 添加操作的值計算涉及前一次查詢結果（帶模運算）
   • 操作次數高達2×10^5，需要高效算法
2. 數據結構選擇：
   • 線段樹：支持O(logn)時間復雜度的單點修改和區間最大值查詢
   • 動態維護序列長度，每次添加相當于單點修改
   • 查詢最后L個數相當于查詢區間[s-L+1, s]的最大值（s為當前序列長度）
3. 關鍵實現：
   • 初始化：預先建立足夠大的線段樹（根據最大可能長度）
   • 添加操作：
     1. 序列長度s加1
     2. 計算新值：(t + a) % p
     3. 在線段樹對應位置更新值
   • 查詢操作：
     1. 計算查詢區間[s-L+1, s]
     2. 在線段樹查詢區間最大值
     3. 記錄查詢結果a供下次添加操作使用
4. 優化處理：
   • 使用結構體存儲線段樹節點信息（區間范圍、最大值）
   • 輸入輸出優化處理大數據量
   • 使用long long類型防止數據溢出
5. 時間復雜度：
   • 預處理：O(n)（建立線段樹）
   • 單次添加：O(logn)
   • 單次查詢：O(logn)
   • 總體：O(mlogn)，完全滿足2×10^5數據規模
6. 空間復雜度：
   • 線段樹需要4n空間，對于n≤2×10^5足夠
7. 注意事項：
   • 初始a值為0
   • 第一個操作保證是添加操作
   • 查詢操作保證L不超過當前序列長度
   • 添加操作的值計算需要模p運算
8. 邊界情況：
   • 序列初始為空
   • 連續多次查詢
   • 添加和查詢操作交替進行
   • 大數運算防止溢出
     該解法通過線段樹高效維護動態序列，完美解決了大規模數據下的添加和查詢操作需求。

標準程序

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,m,i,t,s,a;
char ch;
struct no{int t,w,x;}f[1000010];
void dfs(int t,int w,int x){int mid;f[x].t=t;f[x].w=w;if(t==w){f[x].x=0;f[x].t=t;f[x].w=w;return;}mid=(t+w)/2;dfs(t,mid,x*2);dfs(mid+1,w,x*2+1);f[x].x=max(f[x*2].x,f[x*2+1].x);}
int check(int t,int w,int x){if(t<=f[x].t&&w>=f[x].w) return f[x].x;if(w<f[x*2+1].t) return check(t,w,x*2);if(t>f[x*2].w) return check(t,w,x*2+1);return max(check(t,w,x*2),check(t,w,x*2+1));
}
void change(int y,int k,int x){if(f[x].t==f[x].w){f[x].x=k;return;}if(y<f[x*2+1].t) change(y,k,x*2);else change(y,k,x*2+1);f[x].x=max(f[x*2].x,f[x*2+1].x);
}
signed main(){ios::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cin>>n>>m;dfs(1,n,1);for(i=1;i<=n;i++){cin>>ch>>t;if(ch=='Q') a=check(s-t+1,s,1),cout<<a<<"\n";else s++,change(s,(t+a)%m,1);}
}