企业官网建设流程全解析

6570: 数列区间最大值

1. 先别急着写代码，想想暴力法为啥不行？

题目说最多有100万个询问（M ≤ 10^6），如果每次询问我们都从 X 到 Y 跑一个循环找最大值，最坏情况下每次循环10万次（N ≤ 10^5），总共就是10^6 × 10^5 = 1000亿次运算，电脑肯定跑冒烟了（超时）。

所以我们得提前把答案准备好，等询问来的时候，直接“秒回”。这就用到了经典的ST 表（倍增表）。

2. 核心思路：打表 + 拼凑（倍增思想）

我们可以提前把所有长度是 2 的幂次（比如 1, 2, 4, 8, 16...）的区间最大值全部算出来存好。

• 定义我们的“小本本”：令st[k][i]表示从位置 i 开始，往右数 2^k 个数字，这段区间里的最大值。

• 怎么填这个小本本？

  • 如果长度是 1（k=0），那就是数字本身：st[0][i] = a[i]。

  • 如果长度是 2（k=1），就是左边 1 个和右边 1 个比大小：st[1][i] = max(st[0][i], st[0][i+1])。

  • 如果长度是 4（k=2），就是把左半边 2 个的最大值，和右半边 2 个的最大值，再比一下大小。

  • 总结成公式：st[k][i] = max( st[k-1][i] , st[k-1][i + 2^(k-1)] )。
    说白了就是：“左边一半的最大值” 和 “右边一半的最大值” 取个大的。

3. 来了询问怎么查？（重点！）

假设问你[X, Y]的最大值，这个区间的长度len = Y - X + 1。

我们找一个最大的k，使得2^k <= len（也就是长度不超过区间长度的最大的 2 的幂次）。

比如区间长度是 10，那最大的2^k就是 8（k=3）。

这时候神奇的事情发生了：
我们用两个长度为 8 的区间，直接把[X, Y]给盖住！

• 第一个区间：从X开始，往右数 8 个，即[X, X+7]。

• 第二个区间：从Y往左数 8 个，即[Y-7, Y]。

因为2^k = 8肯定大于区间长度的一半（5），所以这两个区间一定有重叠，并且完美覆盖了整个[X, Y]。
反正我们只是求最大值，重叠了也不怕，最大值不会因为重复计算而变大，所以直接取max(区间1最大值, 区间2最大值)就是正确答案

4.代码如下：

#include<bits/stdc++.h> using namespace std; #define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0) typedef long long ll; const int MAXN = 100005; const int LOG = 20; // 因为 2^17 = 131072 > 1e5，所以 20 绝对够用，多开一点防越界 int st[LOG][MAXN]; // st[k][i]：从 i 开始长度为 2^k 的区间最大值 int lg2[MAXN]; // 提前存好 log2(数字) 的值，查的时候直接用，省时间 void solve() { int N, M; cin >> N >> M; // 读入原始数组，存放到 st[0][i] 里（长度为1的区间最大值就是它自己） for (int i = 1; i <= N; i++) { cin >> st[0][i]; } // 1. 预处理 log2 值（比如 lg2[8] = 3, lg2[10] = 3） // 递推公式：当前数的 log = 它一半的 log + 1 lg2[1] = 0; for (int i = 2; i <= N; i++) { lg2[i] = lg2[i / 2] + 1; } // 2. 预处理 ST 表（倍增打表） // j 表示长度指数，1<<j 就是 2 的 j 次方 for (int j = 1; (1 << j) <= N; j++) { // i 是起点，注意右边界不能超出 N for (int i = 1; i + (1 << j) - 1 <= N; i++) { // 左半部分最大值 和 右半部分最大值 取较大者 st[j][i] = max(st[j-1][i], st[j-1][i + (1 << (j-1))]); } } // 3. 处理 M 个询问 while (M--) { int X, Y; cin >> X >> Y; int len = Y - X + 1; // 区间长度 int k = lg2[len]; // 能覆盖这个长度的最大的 2 的幂次 // 两个区间重叠覆盖，直接取最大值 int ans = max(st[k][X], st[k][Y - (1 << k) + 1]); cout << ans << '\n'; // 用 '\n' 别用 endl，endl 会刷新缓冲区，1e6次会慢死 } } int main(){ IOS; // 加速 cin/cout 用的，一定要写上 int t = 1; while(t--) { solve(); } return 0; }

7097: Trip

题目解读

简化题意：
给你一个 N×M 的矩阵（每个格子有个“舒服度”），要选出一个大小为 a×b 的子矩阵作为晚会场地，再在这个大矩阵内部（不能贴边）选一个大小为 c×d的子矩阵放篝火。
最终的总舒服度 =大矩阵所有格子之和–篝火所在格子之和。
求这个总舒服度的最大值。

注意：篝火必须完全在大矩阵内部，也就是说篝火的四条边都要和大矩阵的边界至少相隔 1 格，所以一定有：
c≤a−2，d≤b−2（题目已保证）。

暴力法为什么不行？

最直接的想法是：枚举所有可能的大矩阵位置（最多 10^6 个），再枚举内部所有可能的篝火位置（最多也是10^6 个），相乘就爆炸了。
所以必须预处理，把“每个大矩阵内部的最小篝火和”提前算出来，查询时直接减。

整体思路（三步走）

1. 快速求任意矩形和
   用二维前缀和，能在 O(1)时间内算出任意子矩阵的和。

2. 计算所有 c×d 小矩阵的和
   把每个可能的篝火位置（左上角）对应的和存下来，得到一个二维数组val。

3. 滑动窗口求每个大矩形内部的最小篝火和
   大矩形内部能放篝火的左上角范围是一个固定大小的矩形区域（高 a−c−1，宽 b−d−1）。
   我们要在这个区域内找val的最小值。
   这可以用二维滑动窗口最小值来完成，先水平滑窗，再垂直滑窗。

最后枚举所有大矩形，用“大矩形和 – 内部最小篝火和”更新答案。

代码如下：

#include <bits/stdc++.h> using namespace std; int main() { int M, N, b, a, d, c; // 输入顺序：M, N, b, a, d, c // 注意：a行b列是大矩形，c行d列是篝火 scanf("%d%d%d%d%d%d", &M, &N, &b, &a, &d, &c); vector<vector<int>> F(N + 1, vector<int>(M + 1)); for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) scanf("%d", &F[i][j]); // 二维前缀和 vector<vector<int>> S(N + 1, vector<int>(M + 1, 0)); for (int i = 1; i <= N; i++) for (int j = 1; j <= M; j++) S[i][j] = S[i - 1][j] + S[i][j - 1] - S[i - 1][j - 1] + F[i][j]; auto getSum = [&](int x1, int y1, int x2, int y2) { return S[x2][y2] - S[x1 - 1][y2] - S[x2][y1 - 1] + S[x1 - 1][y1 - 1]; }; // 1. 计算所有 c×d 子矩阵的和 val int valRows = N - c + 1; int valCols = M - d + 1; vector<vector<int>> val(valRows + 1, vector<int>(valCols + 1)); for (int i = 1; i <= valRows; i++) for (int j = 1; j <= valCols; j++) val[i][j] = getSum(i, j, i + c - 1, j + d - 1); // 2. 水平滑动窗口最小值（窗口宽度 W = b - d - 1） int W = b - d - 1; int rowMinCols = valCols - W + 1; // 结果列数 vector<vector<int>> rowMin(valRows + 1, vector<int>(rowMinCols + 1)); for (int i = 1; i <= valRows; i++) { deque<int> dq; for (int j = 1; j <= valCols; j++) { // 维护单调递增队列 while (!dq.empty() && val[i][dq.back()] >= val[i][j]) dq.pop_back(); dq.push_back(j); // 移除不在窗口内的队首 if (dq.front() < j - W + 1) dq.pop_front(); // 当窗口长度达到 W 时，记录最小值 if (j >= W) { int start = j - W + 1; rowMin[i][start] = val[i][dq.front()]; } } } // 3. 垂直滑动窗口最小值（窗口高度 H = a - c - 1） int H = a - c - 1; int minValRows = valRows - H + 1; // 结果行数 int minValCols = rowMinCols; // 列数不变 vector<vector<int>> minVal(minValRows + 1, vector<int>(minValCols + 1)); for (int j = 1; j <= rowMinCols; j++) { deque<int> dq; for (int i = 1; i <= valRows; i++) { while (!dq.empty() && rowMin[dq.back()][j] >= rowMin[i][j]) dq.pop_back(); dq.push_back(i); if (dq.front() < i - H + 1) dq.pop_front(); if (i >= H) { int start = i - H + 1; minVal[start][j] = rowMin[dq.front()][j]; } } } // 4. 枚举所有大矩形，求最大值 int ans = INT_MIN; int maxI = N - a + 1; // 大矩形左上角行范围 int maxJ = M - b + 1; // 大矩形左上角列范围 for (int I = 1; I <= maxI; I++) { for (int J = 1; J <= maxJ; J++) { int bigSum = getSum(I, J, I + a - 1, J + b - 1); // 内部最小篝火和正好存储在 minVal[I+1][J+1] int minFire = minVal[I + 1][J + 1]; ans = max(ans, bigSum - minFire); } } printf("%d\n", ans); return 0; }

9369: 区间最值位置

题目简述

给你一个长度为 n 的数组，有 m次询问，每次问区间 [x,y] 里的最大值和最小值分别出现在哪个下标（如果有多个相同的，输出最靠左的那个，即下标最小的）。

• n≤105，m≤106，查询量很大。

• 如果用线段树，每次查询要 O(log⁡n)，总共 10^6×17≈1.7×10^7次操作，勉强能过，但 ST 表可以做到 O(1) 查询，更稳。

核心思路：ST 表存“位置”而不是值

平时我们用 ST 表存的是区间的最大值/最小值，但这题需要输出位置，而且如果有多个相同最值要取最小的下标。
所以我们让 ST 表里存的是下标，比较的时候先比较值，值相等时再比较下标，保留较小的那个。

1. 预处理

定义两个 ST 表：

• maxPos[k][i]：表示从位置 i开始，长度为 2k的区间中，最大值所在的最小下标。

• minPos[k][i]：类似，表示最小值所在的最小下标。

初始化（k=0k=0）：
maxPos[0][i] = minPos[0][i] = i（因为长度为 1，就是自己）。

递推（k≥1）：
对于长度 2k，它由两个长度为2k−1 的区间合并：左区间[i, i+2^{k-1}-1]和

右区间[i+2^{k-1}, i+2^k-1]。

我们有两个候选下标：p1 = maxPos[k-1][i]，p2 = maxPos[k-1][i + 2^{k-1}]。
比较a[p1]和a[p2]：

• 如果值不同，取值较大的那个下标。

• 如果值相同，取下标较小的那个（因为题目要求最小的位置）。

最小值同理。

2. 查询

给定区间 [x,y]，长度len = y - x + 1。
取k = floor(log2(len))，则区间可以由两个长度为 2k 的子区间完全覆盖：
[x, x+2^k-1]和[y-2^k+1, y]。

对于最大值：取p1 = maxPos[k][x]，p2 = maxPos[k][y - 2^k + 1]，比较a[p1]和a[p2]，相同取下标小的。
最小值同理。

3. 复杂度

• 预处理：O(nlog⁡n)，n=10^5时大约 1.7×10^6次操作，很快。

• 每次查询：O(1)，总共 10^6次。

4. 注意点

• 数组下标从 1 开始，方便处理。

• 预计算log2数组，或者直接用__lg函数（GCC 内置）。

• 输入输出用scanf/printf或快速cin/cout，因为 mm 很大，endl千万不要用，用'\n'。

代码如下:

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; const int LOG = 18; // 因为 2^17 = 131072 > 1e5，所以 18 够用 int n, m; int a[MAXN]; int maxPos[LOG][MAXN]; int minPos[LOG][MAXN]; int lg2[MAXN]; // 比较两个下标，返回较优的那个（值大/值小，相同时返回下标小的） int betterMax(int p, int q) { if (a[p] != a[q]) return a[p] > a[q] ? p : q; return p < q ? p : q; } int betterMin(int p, int q) { if (a[p] != a[q]) return a[p] < a[q] ? p : q; return p < q ? p : q; } void build() { // 预处理 log2 lg2[1] = 0; for (int i = 2; i <= n; i++) lg2[i] = lg2[i / 2] + 1; // 初始化长度为 1 的区间 for (int i = 1; i <= n; i++) { maxPos[0][i] = i; minPos[0][i] = i; } // 递推 for (int k = 1; (1 << k) <= n; k++) { for (int i = 1; i + (1 << k) - 1 <= n; i++) { int p1 = maxPos[k - 1][i]; int p2 = maxPos[k - 1][i + (1 << (k - 1))]; maxPos[k][i] = betterMax(p1, p2); int q1 = minPos[k - 1][i]; int q2 = minPos[k - 1][i + (1 << (k - 1))]; minPos[k][i] = betterMin(q1, q2); } } } int queryMax(int l, int r) { int len = r - l + 1; int k = lg2[len]; int p1 = maxPos[k][l]; int p2 = maxPos[k][r - (1 << k) + 1]; return betterMax(p1, p2); } int queryMin(int l, int r) { int len = r - l + 1; int k = lg2[len]; int p1 = minPos[k][l]; int p2 = minPos[k][r - (1 << k) + 1]; return betterMin(p1, p2); } int main() { scanf("%d%d", &n, &m); for (int i = 1; i <= n; i++) scanf("%d", &a[i]); build(); while (m--) { int x, y; scanf("%d%d", &x, &y); int maxIdx = queryMax(x, y); int minIdx = queryMin(x, y); printf("%d %d\n", maxIdx, minIdx); } return 0; }

6573: 天才的记忆

思路

1. 准备一个“倍增表”
   定义st[k][i]：从位置i开始，连续2^k个数字中的最大值。

2. 初始化
   当k=0时，长度是 1，最大值就是它自己：st[0][i] = a[i]。

3. 递推打表
   长度2^k的最大值 = 左半边长度2^{k-1}的最大值 和 右半边长度2^{k-1}的最大值 中较大的那个。
   公式：st[k][i] = max(st[k-1][i], st[k-1][i + 2^{k-1}])。

4. 查询怎么查？
   给定区间[A, B]，长度len = B - A + 1。
   找一个最大的k，使得2^k <= len（这个k可以用log2(len)快速得到）。
   那么区间最大值 =max( st[k][A], st[k][B - 2^k + 1] )。
   为什么？因为两个长度为2^k的子区间有重叠，但正好覆盖整个[A, B]，重叠不影响最大值。

5. 关于 log2
   我们可以提前把所有1~N的 log2 值算出来存到数组里，这样查询时直接取，不用每次都调用log函数（更稳）。

代码如下：

#include <bits/stdc++.h> using namespace std; const int MAXN = 200005; const int LOG = 19; // 因为 2^18 = 262144 > 2e5，取 19 绝对够 int st[LOG][MAXN]; // st[k][i] 表示从 i 开始长度为 2^k 的区间最大值 int lg2[MAXN]; // 预存 log2 值 int main() { int N; scanf("%d", &N); for (int i = 1; i <= N; i++) { scanf("%d", &st[0][i]); // 长度为 1 就是自己 } // 1. 预处理 log2 lg2[1] = 0; for (int i = 2; i <= N; i++) { lg2[i] = lg2[i / 2] + 1; } // 2. 构建 ST 表 for (int k = 1; (1 << k) <= N; k++) { for (int i = 1; i + (1 << k) - 1 <= N; i++) { st[k][i] = max(st[k - 1][i], st[k - 1][i + (1 << (k - 1))]); } } // 3. 处理询问 int M; scanf("%d", &M); while (M--) { int A, B; scanf("%d%d", &A, &B); int len = B - A + 1; int k = lg2[len]; int ans = max(st[k][A], st[k][B - (1 << k) + 1]); printf("%d\n", ans); } return 0; }

6571: 最敏捷的机器人

题意简述

给你一个长度为 n 的数组，还有一个窗口大小 k。
需要你输出所有连续 k 个数的窗口中的最大值和最小值。
窗口从左向右滑动，一共要输出 n−k+1 行。

比如样例n=5, k=3，数组[1,2,3,4,5]：

• 窗口 [1,2,3] → 最大 3，最小 1

• 窗口 [2,3,4] → 最大 4，最小 2

• 窗口 [3,4,5] → 最大 5，最小 3

ST 表怎么做？

我们需要两个表：

• maxSt[j][i]：从i开始，长度 2j 的区间最大值

• minSt[j][i]：同理，最小值

预处理时，长度 1 就是自己。
递推时，区间最大值 =max(左半最大值, 右半最大值)，最小值同理。

查询区间 [l,r]：
取k = floor(log2(r-l+1))，
最大值 =max(maxSt[k][l], maxSt[k][r - 2^k + 1])
最小值类似。

代码如下：

#include <bits/stdc++.h> using namespace std; const int MAXN = 100005; const int LOG = 18; // 2^17 = 131072 > 1e5 int a[MAXN]; int maxSt[LOG][MAXN]; int minSt[LOG][MAXN]; int lg2[MAXN]; int main() { int n, k; scanf("%d%d", &n, &k); for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); maxSt[0][i] = minSt[0][i] = a[i]; } // 预处理 log2 lg2[1] = 0; for (int i = 2; i <= n; i++) { lg2[i] = lg2[i / 2] + 1; } // 构建 ST 表 for (int j = 1; (1 << j) <= n; j++) { for (int i = 1; i + (1 << j) - 1 <= n; i++) { maxSt[j][i] = max(maxSt[j-1][i], maxSt[j-1][i + (1 << (j-1))]); minSt[j][i] = min(minSt[j-1][i], minSt[j-1][i + (1 << (j-1))]); } } // 查询每个窗口 for (int i = 1; i <= n - k + 1; i++) { int l = i, r = i + k - 1; int len = r - l + 1; int j = lg2[len]; int mx = max(maxSt[j][l], maxSt[j][r - (1 << j) + 1]); int mn = min(minSt[j][l], minSt[j][r - (1 << j) + 1]); printf("%d %d\n", mx, mn); } return 0; }

不过这题的最优解法是单调队列

单调队列思想（核心）

我们用两个双端队列（deque）：

1. 最大值队列（递减队列）

   • 队列里存的是下标，对应值从队首到队尾严格递减（队首最大）。

   • 新元素a[i]来时，从队尾弹出所有值 ≤ a[i]的元素（因为它们比a[i]小，而且a[i]更新，它们永远不可能再成为最大）。

   • 然后把i入队。

   • 队首就是当前窗口的最大值。

2. 最小值队列（递增队列）

   • 队列里存下标，值从队首到队尾严格递增（队首最小）。

   • 新元素来时，从队尾弹出所有值 ≥ a[i]的元素。

   • 然后把i入队。

   • 队首就是当前窗口的最小值。

关键点：还要检查队首是否过期（即它的下标已经不在当前窗口[i-k+1, i]内），如果是则弹出。

代码如下：

#include <bits/stdc++.h> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin >> n >> k; vector<int> a(n); for (int i = 0; i < n; i++) cin >> a[i]; deque<int> maxq, minq; for (int i = 0; i < n; i++) { // 维护最大值队列（递减） while (!maxq.empty() && a[maxq.back()] <= a[i]) maxq.pop_back(); maxq.push_back(i); if (maxq.front() < i - k + 1) maxq.pop_front(); // 维护最小值队列（递增） while (!minq.empty() && a[minq.back()] >= a[i]) minq.pop_back(); minq.push_back(i); if (minq.front() < i - k + 1) minq.pop_front(); // 输出当前窗口结果 if (i >= k - 1) { cout << a[maxq.front()] << " " << a[minq.front()] << '\n'; } } return 0; }

7937: 良好的感觉

题目理解

给定一个长度为 N 的数组 A（感受值），对于任意区间 [i,j]，定义舒适度 =区间内最小值×区间和。
要求找出所有区间中舒适度的最大值。
例如样例中，选择区间 [3,5] = [6,4,5]，最小值为 4，和为 15，乘积 60 为最大。

算法思路（基于单调栈 + 前缀和）

核心观察

对于每个位置 ii，如果它作为区间最小值，那么能够“管辖”的左右边界是：

• 左侧：找到第一个小于 A[i] 的位置 L（严格小于），那么从 L+1 到 i之间所有元素都 ≥ A[i]。

• 右侧：找到第一个小于 A[i] 的位置 R（严格小于），那么从 i 到 R−1 之间所有元素都 ≥ A[i]。

那么，以 A[i] 为最小值的最大区间就是 [L+1,R−1]（因为如果向左右扩展，只要遇到 ≥A[i] 的元素，最小值仍为 A[i]，区间和会更大，所以扩展得越远越好）。
该区间的舒适度 =A[i]×(区间和)，用前缀和 O(1) 计算区间和。
我们枚举每个 i，计算以它作为最小值的最大区间的舒适度，取最大值即可。

如何快速求左右第一个小于的位置？

利用单调栈（维护单调递增栈）：

• 左侧：从左到右扫描，维护栈内下标对应的值递增。
  当遇到 A[i] 时，弹出栈顶所有 ≥ A[i] 的元素（因为它们不可能成为后面元素的左边界），最后栈顶就是左边第一个 < A[i] 的位置（若栈空则为 0）。

• 右侧：从右到左扫描，类似方法得到右边第一个 < A[i] 的位置（若栈空则为 n+1）。

这样每个元素进出栈一次，总复杂度 O(N)。

代码如下：

#include<bits/stdc++.h> using namespace std; const int N=1e6; #define ll long long ll cnt,n,m,t,x,y,k; ll a[100010], b[100010], l[100010], r[100010]; int main() { ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); cin>>n; // 读入数组，并计算前缀和（b[i]表示前i项和） for(int i=1;i<=n;i++){ cin>>a[i]; b[i]=a[i]+b[i-1]; } // 计算左侧第一个小于 a[i] 的位置 for(int i=1;i<=n;i++){ int p=i-1; // 从左边相邻位置开始 while(a[p] >= a[i]){ // 如果左边元素 >= 当前值，则继续往左跳 p = l[p]; // 跳到该位置对应的更左边第一个小于它的位置 } l[i]=p; // 最终 p 就是左边第一个小于 a[i] 的位置 } // 计算右侧第一个小于 a[i] 的位置 for(int i=n;i>=1;i--){ int p=i+1; // 从右边相邻位置开始 while(a[p] >= a[i]){ p = r[p]; // 跳到该位置对应的更右边第一个小于它的位置 } r[i]=p; // 最终 p 就是右边第一个小于 a[i] 的位置 } ll ans=0; for(int i=1;i<=n;i++){ // 区间 [l[i]+1, r[i]-1] 中最小值就是 a[i] // 区间和 = b[r[i]-1] - b[l[i]] ll sum = a[i] * (b[r[i]-1] - b[l[i]]); ans = max(ans, sum); } cout<<ans; return 0; }