原文

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);}
}