区间查询,果断想到线段树,看了一下题解有很多用的st表,但感觉st表模板太难记了,线段树相对好记很多,还是线段树更香一点。
树状数组也可以求最值但得改模板。
参考代码:
#include using namespace std; const int N = 100010; int w[N]; int n, m; struct node { int l, r; int minv; }tr[N * 4]; //向上更新 void pushup(int u) { tr[u].minv = min(tr[u << 1].minv, tr[u << 1 | 1].minv); } //初始化 void bulid(int u, int l, int r) { if (l == r) tr[u]= { l,r,w[r] }; else { tr[u] = { l,r }; int mid = l + r >> 1; bulid(u << 1, l, mid); bulid(u << 1 | 1, mid + 1, r); pushup(u); } } //区间查询 int query(int u, int l, int r) { if (tr[u].l >= l && tr[u].r > 1; if (l <= mid) res = min(res, query(u << 1, l, r)); if (r > mid)res = min(res, query(u << 1 | 1, l, r)); return res; } //将x位置的数修改为v,此题没有用到单点修改,这个函数可以不写 void modify(int u, int x, int v) { if (tr[u].l == tr[u].r) tr[u].minv = v; else { int mid = tr[u].l + tr[u].r >> 1; if (x <= mid)modify(u << 1, x, v); else modify(u << 1 | 1, x, v); pushup(u); } } int main() { //大输入记得开取消同步流或者用cstdio不然必超时 ios::sync_with_stdio(false); cin.tie(0); cin >> m >> n; for (int i = 1; i > w[i]; bulid(1, 1, m); while (n--) { int l, r; cin >> l >> r; cout << query(1, l, r) << '\n'; } return 0; }
0.0分
3 人评分
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:642 |
多输入输出练习2 (C语言代码)浏览:1656 |
简单的a+b (C语言代码)浏览:442 |
A+B for Input-Output Practice (III) (C语言代码)浏览:423 |
C语言程序设计教程(第三版)课后习题7.4 (C语言代码)浏览:510 |
多组数据新方法浏览:355 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:628 |
1218题求大神帮忙看看怎么不能过浏览:697 |
C语言程序设计教程(第三版)课后习题9.4 (C语言代码)浏览:484 |
母牛的故事 (C语言代码)浏览:503 |