[一本通学习笔记] RMQ专题
2024-08-31 13:50:50
傻傻地敲了好多遍ST表。
10119. 「一本通 4.2 例 1」数列区间最大值
#include <bits/stdc++.h>
using namespace std;
const int N = 1000005;
struct st {
int a[N][21];
void build(int *src, int n) {
for (int i = 1; i <= n; i++) a[i][0] = src[i];
for (int i = 1; i <= 20; i++)
for (int j = 1; j <= n - (1 << i) + 1; j++)
a[j][i] = max(a[j][i - 1], a[j + (1 << (i - 1))][i - 1]);
}
int query(int l, int r) {
int j = log2(r - l + 1);
return max(a[l][j], a[r - (1 << j) + 1][j]);
}
};
int n, m, a[N];
st s;
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i];
s.build(a, n);
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
cout << s.query(u, v) << endl;
}
}
10120. 「一本通 4.2 例 2」最敏捷的机器人
#include <bits/stdc++.h>
using namespace std;
struct Monoqueue {
deque<pair<int, int> > q;
void push(int val, int tim) {
while (q.size() && q.front().first >= val) q.pop_front();
q.push_front(make_pair(val, tim));
}
int get(int tim) {
while (q.size() && q.back().second < tim) q.pop_back();
return q.back().first;
}
};
Monoqueue a, b;
int n, k, t;
int main() {
ios::sync_with_stdio(false);
cin >> n >> k;
for (int i = 1; i < k; i++) {
cin >> t;
a.push(t, i + k - 1);
b.push(-t, i + k - 1);
}
for (int i = k; i <= n; i++) {
cin >> t;
a.push(t, i + k - 1);
b.push(-t, i + k - 1);
cout << -b.get(i) << " " << a.get(i) << endl;
}
}
10121. 「一本通 4.2 例 3」与众不同
#include <bits/stdc++.h>
using namespace std;
int n, m, a[3000005], L, R;
namespace Monoqueue {
int head = -1, tail = 0, q[2000005], buck[2000005], jmp[2000005];
void solve() {
for (int i = 1; i <= n; i++) {
q[++head] = a[i];
while (buck[a[i]]) buck[q[tail++]]--;
buck[a[i]]++;
jmp[i] = (head - tail + 1);
}
}
} // namespace Monoqueue
namespace ST {
int s[2000005][21];
void build(int n, int *src) {
for (int i = 1; i <= n; i++) s[i][0] = src[i];
for (int j = 1; j < 20; j++)
for (int i = 1; i <= n - (1 << j >> 1); i++) s[i][j] = max(s[i][j - 1], s[i + (1 << j >> 1)][j - 1]);
}
int query(int l, int r) {
int lg = log2(r - l + 1);
return max(s[l][lg], s[r - (1 << lg) + 1][lg]);
}
} // namespace ST
int main() {
ios::sync_with_stdio(false);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i], a[i] += 1000000;
Monoqueue::solve();
ST::build(n, Monoqueue::jmp);
for (int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
++l;
++r;
int L = 1, R = r - l + 2;
while (R > L) {
int M = (L + R) >> 1;
int x = ST::query(l + M - 1, r);
// cout<<L<<" "<<R<<" "<<M<<" "<<x<<endl;
if (x >= M)
L = M + 1;
else
R = M;
}
cout << L - 1 << endl;
}
}
10122. 「一本通 4.2 练习 1」天才的记忆
#include <bits/stdc++.h>
using namespace std;
int n, m, a[1000005][21];
void build() {
for (int i = 1; i <= 20; i++)
for (int j = 1; j <= n - (1 << i >> 1) + 1; j++)
a[j][i] = max(a[j][i - 1], a[j + (1 << i >> 1)][i - 1]);
}
int query(int l, int r) {
int lg = log2(r - l + 1);
return max(a[l][lg], a[r - (1 << lg) + 1][lg]);
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i][0];
build();
cin >> m;
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
cout << query(u, v) << endl;
}
}
10123. 「一本通 4.2 练习 2」Balanced Lineup
#include <bits/stdc++.h>
using namespace std;
int n, m, a[1000005][21], b[1000005][21], u, v;
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> a[i][0], b[i][0] = a[i][0];
for (int i = 1; i <= 20; i++)
for (int j = 1; j + (1 << i >> 1) - 1 <= n; j++)
a[j][i] = max(a[j][i - 1], a[j + (1 << i >> 1)][i - 1]),
b[j][i] = min(b[j][i - 1], b[j + (1 << i >> 1)][i - 1]);
for (int i = 1; i <= m; i++) {
cin >> u >> v;
int lg = log2(v - u + 1);
cout << max(a[u][lg], a[v - (1 << lg) + 1][lg]) - min(b[u][lg], b[v - (1 << lg) + 1][lg]) << endl;
}
}
最新文章
- kafka单节点测试
- Debugging WebLogic Server Applications Using Eclipse and the WebLogic-Plugin
- VirtualBox网络设置的问题
- selenium实战-自动退百度云共享群
- 9月15日，YTFCloud，创业圈的技术新宠
- Coremail邮件系统存储型XSS两个
- WebForm 发送邮箱
- android-exploitme（二）：安装apk熟悉测试环境
- twitter bootstrap 2.x 3.x区别
- C# using SendMessage, problem with WM_COPYDATA z
- Android -- 官方下拉刷新SwipeRefreshLayout
- 内功心法 -- java.util.ArrayList<E> (2)
- JS数组+JS循环题
- Coursera课程 Programming Languages, Part A 总结
- px,em,rem的区别与用法
- f-stack nginx多进程报错 primary worker process failed to initialize
- 简单的线程Thread使用
- docker应用-5（使用overlay 网络进行容器间跨物理主机通信）
- google sitemap
- 一个C#操作Excel类，功能比较全