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 个数字这段区间里的最大值。怎么填这个小本本如果长度是 1k0那就是数字本身st[0][i] a[i]。如果长度是 2k1就是左边 1 个和右边 1 个比大小st[1][i] max(st[0][i], st[0][i1])。如果长度是 4k2就是把左半边 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就是 8k3。这时候神奇的事情发生了我们用两个长度为 8 的区间直接把[X, Y]给盖住第一个区间从X开始往右数 8 个即[X, X7]。第二个区间从Y往左数 8 个即[Y-7, Y]。因为2^k 8肯定大于区间长度的一半5所以这两个区间一定有重叠并且完美覆盖了整个[X, Y]。反正我们只是求最大值重叠了也不怕最大值不会因为重复计算而变大所以直接取max(区间1最大值, 区间2最大值)就是正确答案4.代码如下#includebits/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 表示长度指数1j 就是 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 别用 endlendl 会刷新缓冲区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−2d≤b−2题目已保证。暴力法为什么不行最直接的想法是枚举所有可能的大矩阵位置最多 10^6 个再枚举内部所有可能的篝火位置最多也是10^6 个相乘就爆炸了。所以必须预处理把“每个大矩阵内部的最小篝火和”提前算出来查询时直接减。整体思路三步走快速求任意矩形和用二维前缀和能在 O(1)时间内算出任意子矩阵的和。计算所有 c×d 小矩阵的和把每个可能的篝火位置左上角对应的和存下来得到一个二维数组val。滑动窗口求每个大矩形内部的最小篝火和大矩形内部能放篝火的左上角范围是一个固定大小的矩形区域高 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); vectorvectorint F(N 1, vectorint(M 1)); for (int i 1; i N; i) for (int j 1; j M; j) scanf(%d, F[i][j]); // 二维前缀和 vectorvectorint S(N 1, vectorint(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; vectorvectorint val(valRows 1, vectorint(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; // 结果列数 vectorvectorint rowMin(valRows 1, vectorint(rowMinCols 1)); for (int i 1; i valRows; i) { dequeint 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; // 列数不变 vectorvectorint minVal(minValRows 1, vectorint(minValCols 1)); for (int j 1; j rowMinCols; j) { dequeint 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[I1][J1] int minFire minVal[I 1][J 1]; ans max(ans, bigSum - minFire); } } printf(%d\n, ans); return 0; }9369: 区间最值位置题目简述给你一个长度为 n 的数组有 m次询问每次问区间 [x,y] 里的最大值和最小值分别出现在哪个下标如果有多个相同的输出最靠左的那个即下标最小的。n≤105m≤106查询量很大。如果用线段树每次查询要 O(logn)总共 10^6×17≈1.7×10^7次操作勉强能过但 ST 表可以做到 O(1) 查询更稳。核心思路ST 表存“位置”而不是值平时我们用 ST 表存的是区间的最大值/最小值但这题需要输出位置而且如果有多个相同最值要取最小的下标。所以我们让 ST 表里存的是下标比较的时候先比较值值相等时再比较下标保留较小的那个。1. 预处理定义两个 ST 表maxPos[k][i]表示从位置 i开始长度为 2k的区间中最大值所在的最小下标。minPos[k][i]类似表示最小值所在的最小下标。初始化k0k0maxPos[0][i] minPos[0][i] i因为长度为 1就是自己。递推k≥1对于长度 2k它由两个长度为2k−1 的区间合并左区间[i, i2^{k-1}-1]和右区间[i2^{k-1}, i2^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, x2^k-1]和[y-2^k1, y]。对于最大值取p1 maxPos[k][x]p2 maxPos[k][y - 2^k 1]比较a[p1]和a[p2]相同取下标小的。最小值同理。3. 复杂度预处理O(nlogn)n10^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: 天才的记忆思路准备一个“倍增表”定义st[k][i]从位置i开始连续2^k个数字中的最大值。初始化当k0时长度是 1最大值就是它自己st[0][i] a[i]。递推打表长度2^k的最大值 左半边长度2^{k-1}的最大值 和 右半边长度2^{k-1}的最大值 中较大的那个。公式st[k][i] max(st[k-1][i], st[k-1][i 2^{k-1}])。查询怎么查给定区间[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]重叠不影响最大值。关于 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−k1 行。比如样例n5, k3数组[1,2,3,4,5]窗口 [1,2,3] → 最大 3最小 1窗口 [2,3,4] → 最大 4最小 2窗口 [3,4,5] → 最大 5最小 3ST 表怎么做我们需要两个表maxSt[j][i]从i开始长度 2j 的区间最大值minSt[j][i]同理最小值预处理时长度 1 就是自己。递推时区间最大值 max(左半最大值, 右半最大值)最小值同理。查询区间 [l,r]取k floor(log2(r-l1))最大值 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最大值队列递减队列队列里存的是下标对应值从队首到队尾严格递减队首最大。新元素a[i]来时从队尾弹出所有值 ≤ a[i]的元素因为它们比a[i]小而且a[i]更新它们永远不可能再成为最大。然后把i入队。队首就是当前窗口的最大值。最小值队列递增队列队列里存下标值从队首到队尾严格递增队首最小。新元素来时从队尾弹出所有值 ≥ a[i]的元素。然后把i入队。队首就是当前窗口的最小值。关键点还要检查队首是否过期即它的下标已经不在当前窗口[i-k1, i]内如果是则弹出。代码如下#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, k; cin n k; vectorint a(n); for (int i 0; i n; i) cin a[i]; dequeint 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严格小于那么从 L1 到 i之间所有元素都 ≥ A[i]。右侧找到第一个小于 A[i] 的位置 R严格小于那么从 i 到 R−1 之间所有元素都 ≥ A[i]。那么以 A[i] 为最小值的最大区间就是 [L1,R−1]因为如果向左右扩展只要遇到 ≥A[i] 的元素最小值仍为 A[i]区间和会更大所以扩展得越远越好。该区间的舒适度 A[i]×(区间和)用前缀和 O(1) 计算区间和。我们枚举每个 i计算以它作为最小值的最大区间的舒适度取最大值即可。如何快速求左右第一个小于的位置利用单调栈维护单调递增栈左侧从左到右扫描维护栈内下标对应的值递增。当遇到 A[i] 时弹出栈顶所有 ≥ A[i] 的元素因为它们不可能成为后面元素的左边界最后栈顶就是左边第一个 A[i] 的位置若栈空则为 0。右侧从右到左扫描类似方法得到右边第一个 A[i] 的位置若栈空则为 n1。这样每个元素进出栈一次总复杂度 O(N)。代码如下#includebits/stdc.h using namespace std; const int N1e6; #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); cinn; // 读入数组并计算前缀和b[i]表示前i项和 for(int i1;in;i){ cina[i]; b[i]a[i]b[i-1]; } // 计算左侧第一个小于 a[i] 的位置 for(int i1;in;i){ int pi-1; // 从左边相邻位置开始 while(a[p] a[i]){ // 如果左边元素 当前值则继续往左跳 p l[p]; // 跳到该位置对应的更左边第一个小于它的位置 } l[i]p; // 最终 p 就是左边第一个小于 a[i] 的位置 } // 计算右侧第一个小于 a[i] 的位置 for(int in;i1;i--){ int pi1; // 从右边相邻位置开始 while(a[p] a[i]){ p r[p]; // 跳到该位置对应的更右边第一个小于它的位置 } r[i]p; // 最终 p 就是右边第一个小于 a[i] 的位置 } ll ans0; for(int i1;in;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); } coutans; return 0; }
