[综合题]20（RMQ 区间最值问题）给定序列 a0, … , an-1，和 m 次询问，每次询问给定 l, r，求max {al, … , ar} 。为了解决该问题，有一个算法叫 the Method of

当前位置：首页 > 题库 > NOIP CSP J/S信奥赛 > 提高组

题目信息

题目类型: 提高级
题目年份: 2021

题目题型: 综合题
关键词: RMQ区间最值问题

题目题干

20（RMQ 区间最值问题）给定序列 a₀, … , a_n-1，和 m 次询问，每次询问给定 l, r，求max {a_l, … , a_r} 。

为了解决该问题，有一个算法叫 the Method of Four Russians，其时间复杂度为0(n + m)，步骤如下：

• 建立 Cartesian（笛卡尔）树，将问题转化为树上的 LCA（最近公共祖先）问题。

• 对于 LCA 问题，可以考虑其 Euler 序（即按照 DFS 过程，经过所有点，环游回根的序列），即求 Euler 序列上两点间一个新的 RMQ 问题。

• 注意新的问题为 ±1 RMQ，即相邻两点的深度差一定为 1。

下面解决这个 ±1 RMQ 问题，“序列”指 Euler 序列：

• 设 t 为 Euler 序列长度。取 b = $20（RMQ 区间最值问题）给定序列 a0, … , an-1，和 m 次询问，每次询问给定 l, r，求max {al, … , ar} 。为了解决该问题，有一个算法叫 the Method of Four Russians，其时间复杂度为0(n + m)，步骤如下： • 建立 Cartesian（笛卡尔）树，将问题转化为树上的 LCA（最近公共祖先）问题。 • 对于 LCA 问题，可以考虑其 Euler 序（即按照 DFS 过程，经过所有点，环游回根的序列），即求 Euler 序列上两点间一个新的 RMQ 问题。 • 注意新的问题为 ±1 RMQ，即相邻两点的深度差一定为 1。下面解决这个 ±1 RMQ 问题，“序列”指 Euler 序列： • 设 t 为 Euler 序列长度。取 b =将序列每 b 个分为一大块，使用 ST 表（倍增表）处理大块间的 RMQ 问题，复杂度 • （重点）对于一个块内的 RMQ 问题，也需要O(1) 的算法。由于差分数组 2b-1 种，可以预处理出所有情况下的最值位置，预处理复杂度 O(b2b)，不超过 O(n)。 • 最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ 问题。试补全程序。 #include <iostream> #include <cmath> using namespace std; const int MAXN = 100000, MAXT = MAXN << 1; const int MAXL = 18, MAXB = 9, MAXC = MAXT / MAXB; struct node { int val; int dep, dfn, end; node *son[2]; // son[0], son[1] 分别表示左右儿子 } T[MAXN]; int n, t, b, c, Log2[MAXC + 1]; int Pos[(1 << (MAXB - 1)) + 5], Dif[MAXC + 1]; node *root, *A[MAXT], *Min[MAXL][MAXC]; void build() { // 建立 Cartesian 树 static node *S[MAXN + 1]; int top = 0; for (int i = 0; i < n; i++) { node *p = &T[i]; while (top && S[top]->val < p->val) ①; if (top) ②; S[++top] = p; } root = S[1]; } void DFS(node *p) { // 构建 Euler 序列 A[p->dfn = t++] = p; for (int i = 0; i < 2; i++) if (p->son[i]) { p->son[i]->dep = p->dep + 1; DFS(p->son[i]); A[t++] = p; } p->end = t - 1; } node *min(node *x, node *y) { return ③ ? x : y; } void ST_init() { b = (int)(ceil(log2(t) / 2)); c = t / b; Log2[1] = 0; for (int i = 2; i <= c; i++) Log2[i] = Log2[i >> 1] + 1; for (int i = 0; i < c; i++) { Min[0][i] = A[i * b]; for (int j = 1; j < b; j++) Min[0][i] = min(Min[0][i], A[i * b + j]); } for (int i = 1, l = 2; l <= c; i++, l <<= 1) for (int j = 0; j + l <= c; j++) Min[i][j] = min(Min[i - 1][j], Min[i - 1][j + (l >> 1)]); } void small_init() { // 块内预处理 for (int i = 0; i <= c; i++) for (int j = 1; j < b && i * b + j < t; j++) if (④) Dif[i] |= 1 << (j - 1); for (int S = 0; S < (1 << (b - 1)); S++) { int mx = 0, v = 0; for (int i = 1; i < b; i++) { ⑤; if (v < mx) { mx = v; Pos[S] = i; } } } } node *ST_query(int l, int r) { int g = Log2[r - l + 1]; return min(Min[g][l], Min[g][r - (1 << g) + 1]); } node *small_query(int l, int r) { // 块内查询 int p = l / b; int S = ⑥; return A[l + Pos[S]]; } node *query(int l, int r) { if (l > r) return query(r, l); int pl = l / b, pr = r / b; if (pl == pr) { return small_query(l, r); } else { node *s = min(small_query(l, pl * b + b - 1), small_query(pr * b, r)); if (pl + 1 <= pr - 1) s = min(s, ST_query(pl + 1, pr - 1)); return s; } } int main() { int m; cin >> n >> m; for (int i = 0; i < n; i++) cin >> T[i].val; build(); DFS(root); ST_init(); small_init(); while (m--) { int l, r; cin >> l >> r; cout << query(T[l].dfn, T[r].dfn)->val << endl; } return 0; } 单选 ①处应填（） A.p->son[0] = S[top--] B.p->son[1] = S[top--] C.S[top--]->son[0] = p D.S[top--]->son[1] = p 第2题单选 ②处应填（） A.p->son[0] = S[top] B.p->son[1] = S[top] C.S[top]->son[0] = p D.S[top]->son[1] = p 第3题单选 ③处应填（） A.x->dep < y->dep B.x < y C.x->dep > y->dep D.x->val < y->val 第4题单选 ④处应填（） A.A[i * b + j - 1] == A[i * b + j]->son[0] B.A[i * b + j]->val < A[i * b + j - 1]->val C.A[i * b + j] == A[i * b + j - 1]->son[1] D.A[i * b + j]->dep < A[i * b + j - 1]->dep 第5题单选 ⑤处应填（） A.v += (S >> i & 1) ? -1 : 1 B.v += (S >> i & 1) ? 1 : -1 C.v += (S >> (i - 1) & 1) ? 1 : -1 D.v += (S >> (i - 1) & 1) ? -1 : 1 第6题单选 ⑥处应填（） A.(Dif[p] >> (r - p * b)) & ((1 << (r - l)) - 1) B.Dif[p] C.(Dif[p] >> (l - p * b)) & ((1 << (r - l)) - 1) D.(Dif[p] >> ((p + 1) * b - r)) & ((1 << (r - l + 1)) - 1)$ 将序列每 b 个分为一大块，使用 ST 表（倍增表）处理大块间的 RMQ 问题，复杂度

$20（RMQ 区间最值问题）给定序列 a0, … , an-1，和 m 次询问，每次询问给定 l, r，求max {al, … , ar} 。为了解决该问题，有一个算法叫 the Method of Four Russians，其时间复杂度为0(n + m)，步骤如下： • 建立 Cartesian（笛卡尔）树，将问题转化为树上的 LCA（最近公共祖先）问题。 • 对于 LCA 问题，可以考虑其 Euler 序（即按照 DFS 过程，经过所有点，环游回根的序列），即求 Euler 序列上两点间一个新的 RMQ 问题。 • 注意新的问题为 ±1 RMQ，即相邻两点的深度差一定为 1。下面解决这个 ±1 RMQ 问题，“序列”指 Euler 序列： • 设 t 为 Euler 序列长度。取 b =将序列每 b 个分为一大块，使用 ST 表（倍增表）处理大块间的 RMQ 问题，复杂度 • （重点）对于一个块内的 RMQ 问题，也需要O(1) 的算法。由于差分数组 2b-1 种，可以预处理出所有情况下的最值位置，预处理复杂度 O(b2b)，不超过 O(n)。 • 最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ 问题。试补全程序。 #include <iostream> #include <cmath> using namespace std; const int MAXN = 100000, MAXT = MAXN << 1; const int MAXL = 18, MAXB = 9, MAXC = MAXT / MAXB; struct node { int val; int dep, dfn, end; node *son[2]; // son[0], son[1] 分别表示左右儿子 } T[MAXN]; int n, t, b, c, Log2[MAXC + 1]; int Pos[(1 << (MAXB - 1)) + 5], Dif[MAXC + 1]; node *root, *A[MAXT], *Min[MAXL][MAXC]; void build() { // 建立 Cartesian 树 static node *S[MAXN + 1]; int top = 0; for (int i = 0; i < n; i++) { node *p = &T[i]; while (top && S[top]->val < p->val) ①; if (top) ②; S[++top] = p; } root = S[1]; } void DFS(node *p) { // 构建 Euler 序列 A[p->dfn = t++] = p; for (int i = 0; i < 2; i++) if (p->son[i]) { p->son[i]->dep = p->dep + 1; DFS(p->son[i]); A[t++] = p; } p->end = t - 1; } node *min(node *x, node *y) { return ③ ? x : y; } void ST_init() { b = (int)(ceil(log2(t) / 2)); c = t / b; Log2[1] = 0; for (int i = 2; i <= c; i++) Log2[i] = Log2[i >> 1] + 1; for (int i = 0; i < c; i++) { Min[0][i] = A[i * b]; for (int j = 1; j < b; j++) Min[0][i] = min(Min[0][i], A[i * b + j]); } for (int i = 1, l = 2; l <= c; i++, l <<= 1) for (int j = 0; j + l <= c; j++) Min[i][j] = min(Min[i - 1][j], Min[i - 1][j + (l >> 1)]); } void small_init() { // 块内预处理 for (int i = 0; i <= c; i++) for (int j = 1; j < b && i * b + j < t; j++) if (④) Dif[i] |= 1 << (j - 1); for (int S = 0; S < (1 << (b - 1)); S++) { int mx = 0, v = 0; for (int i = 1; i < b; i++) { ⑤; if (v < mx) { mx = v; Pos[S] = i; } } } } node *ST_query(int l, int r) { int g = Log2[r - l + 1]; return min(Min[g][l], Min[g][r - (1 << g) + 1]); } node *small_query(int l, int r) { // 块内查询 int p = l / b; int S = ⑥; return A[l + Pos[S]]; } node *query(int l, int r) { if (l > r) return query(r, l); int pl = l / b, pr = r / b; if (pl == pr) { return small_query(l, r); } else { node *s = min(small_query(l, pl * b + b - 1), small_query(pr * b, r)); if (pl + 1 <= pr - 1) s = min(s, ST_query(pl + 1, pr - 1)); return s; } } int main() { int m; cin >> n >> m; for (int i = 0; i < n; i++) cin >> T[i].val; build(); DFS(root); ST_init(); small_init(); while (m--) { int l, r; cin >> l >> r; cout << query(T[l].dfn, T[r].dfn)->val << endl; } return 0; } 单选 ①处应填（） A.p->son[0] = S[top--] B.p->son[1] = S[top--] C.S[top--]->son[0] = p D.S[top--]->son[1] = p 第2题单选 ②处应填（） A.p->son[0] = S[top] B.p->son[1] = S[top] C.S[top]->son[0] = p D.S[top]->son[1] = p 第3题单选 ③处应填（） A.x->dep < y->dep B.x < y C.x->dep > y->dep D.x->val < y->val 第4题单选 ④处应填（） A.A[i * b + j - 1] == A[i * b + j]->son[0] B.A[i * b + j]->val < A[i * b + j - 1]->val C.A[i * b + j] == A[i * b + j - 1]->son[1] D.A[i * b + j]->dep < A[i * b + j - 1]->dep 第5题单选 ⑤处应填（） A.v += (S >> i & 1) ? -1 : 1 B.v += (S >> i & 1) ? 1 : -1 C.v += (S >> (i - 1) & 1) ? 1 : -1 D.v += (S >> (i - 1) & 1) ? -1 : 1 第6题单选 ⑥处应填（） A.(Dif[p] >> (r - p * b)) & ((1 << (r - l)) - 1) B.Dif[p] C.(Dif[p] >> (l - p * b)) & ((1 << (r - l)) - 1) D.(Dif[p] >> ((p + 1) * b - r)) & ((1 << (r - l + 1)) - 1)$

• （重点）对于一个块内的 RMQ 问题，也需要O(1) 的算法。由于差分数组 2^b-1

种，可以预处理出所有情况下的最值位置，预处理复杂度 O(b2^b)，不超过 O(n)。

• 最终，对于一个查询，可以转化为中间整的大块的 RMQ 问题，以及两端块内的 RMQ 问题。

试补全程序。

#include <iostream>

#include <cmath>

using namespace std;

const int MAXN = 100000, MAXT = MAXN << 1;

const int MAXL = 18, MAXB = 9, MAXC = MAXT / MAXB;

struct node {

int val;

int dep, dfn, end;

node *son[2]; // son[0], son[1] 分别表示左右儿子

} T[MAXN];

int n, t, b, c, Log2[MAXC + 1];

int Pos[(1 << (MAXB - 1)) + 5], Dif[MAXC + 1];

node *root, *A[MAXT], *Min[MAXL][MAXC];

void build() { // 建立 Cartesian 树

static node *S[MAXN + 1];

int top = 0;

for (int i = 0; i < n; i++) {

node *p = &T[i];

while (top && S[top]->val < p->val)

①;

if (top)

②;

S[++top] = p;

}

root = S[1];

}

void DFS(node *p) { // 构建 Euler 序列

A[p->dfn = t++] = p;

for (int i = 0; i < 2; i++)

if (p->son[i]) {

p->son[i]->dep = p->dep + 1;

DFS(p->son[i]);

A[t++] = p;

}

p->end = t - 1;

}

node *min(node *x, node *y) {

return ③ ? x : y;

}

void ST_init() {

b = (int)(ceil(log2(t) / 2));

c = t / b;

Log2[1] = 0;

for (int i = 2; i <= c; i++)

Log2[i] = Log2[i >> 1] + 1;

for (int i = 0; i < c; i++) {

Min[0][i] = A[i * b];

for (int j = 1; j < b; j++)

Min[0][i] = min(Min[0][i], A[i * b + j]);

}

for (int i = 1, l = 2; l <= c; i++, l <<= 1)

for (int j = 0; j + l <= c; j++)

Min[i][j] = min(Min[i - 1][j], Min[i - 1][j + (l >> 1)]);

}

void small_init() { // 块内预处理

for (int i = 0; i <= c; i++)

for (int j = 1; j < b && i * b + j < t; j++)

if (④)

Dif[i] |= 1 << (j - 1);

for (int S = 0; S < (1 << (b - 1)); S++) {

int mx = 0, v = 0;

for (int i = 1; i < b; i++) {

⑤;

if (v < mx) {

mx = v;

Pos[S] = i;

}

node *ST_query(int l, int r) {

int g = Log2[r - l + 1];

return min(Min[g][l], Min[g][r - (1 << g) + 1]);

}

node *small_query(int l, int r) { // 块内查询

int p = l / b;

int S = ⑥;

return A[l + Pos[S]];

}

node *query(int l, int r) {

if (l > r)

return query(r, l);

int pl = l / b, pr = r / b;

if (pl == pr) {

return small_query(l, r);

} else {

node *s = min(small_query(l, pl * b + b - 1),

small_query(pr * b, r));

if (pl + 1 <= pr - 1)

s = min(s, ST_query(pl + 1, pr - 1));

return s;

}

int main() {

int m;

cin >> n >> m;

for (int i = 0; i < n; i++)

cin >> T[i].val;

build();

DFS(root);

ST_init();

small_init();

while (m--) {

int l, r;

cin >> l >> r;

cout << query(T[l].dfn, T[r].dfn)->val << endl;

}

return 0;

}

单选

①处应填（）

A.p->son[0] = S[top--]

B.p->son[1] = S[top--]

C.S[top--]->son[0] = p

D.S[top--]->son[1] = p

第2题单选

②处应填（）

A.p->son[0] = S[top]

B.p->son[1] = S[top]

C.S[top]->son[0] = p

D.S[top]->son[1] = p

第3题单选

③处应填（）

A.x->dep < y->dep

B.x < y

C.x->dep > y->dep

D.x->val < y->val

第4题单选

④处应填（）

A.A[i * b + j - 1] == A[i * b + j]->son[0]

B.A[i * b + j]->val < A[i * b + j - 1]->val

C.A[i * b + j] == A[i * b + j - 1]->son[1]

D.A[i * b + j]->dep < A[i * b + j - 1]->dep

第5题单选

⑤处应填（）

A.v += (S >> i & 1) ? -1 : 1

B.v += (S >> i & 1) ? 1 : -1

C.v += (S >> (i - 1) & 1) ? 1 : -1

D.v += (S >> (i - 1) & 1) ? -1 : 1

第6题单选

⑥处应填（）

A.(Dif[p] >> (r - p * b)) & ((1 << (r - l)) - 1)

B.Dif[p]

C.(Dif[p] >> (l - p * b)) & ((1 << (r - l)) - 1)

D.(Dif[p] >> ((p + 1) * b - r)) & ((1 << (r - l + 1)) - 1)

答案解析

提示声明

免责声明：本站资源均来自网络或者用户投稿，仅供用于学习和交流：如有侵权联系删除!
温馨提示：本文属于积分文章，需要充值获得积分或升级VIP会员，也可在会员中心投稿获取。

20（RMQ 区间最值问题）给定序列 a0, … , an-1，和 m 次询问，每次询问给定 l, r，求max {al, … , ar} 。为了解决该问题，有一个算法叫 the Method of

目录

题目信息

题目题干

答案解析

相关题目

提示声明

猜你喜欢

©2016-2021 100150.com

帮助中心

20（RMQ 区间最值问题）给定序列 a0, … , an-1，和 m 次询问，每次询问给定 l, r，求max {al, … , ar} 。 为了解决该问题，有一个算法叫 the Method of

目录

题目信息

题目题干

答案解析

相关题目

提示声明

猜你喜欢

©2016-2021 100150.com

帮助中心

20（RMQ 区间最值问题）给定序列 a0, … , an-1，和 m 次询问，每次询问给定 l, r，求max {al, … , ar} 。为了解决该问题，有一个算法叫 the Method of