区间查询,果断想到线段树,看了一下题解有很多用的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 人评分
整人!!浏览:839 |
DNA (C++代码)浏览:650 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:324 |
点我有惊喜!你懂得!浏览:1403 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:674 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:585 |
【计算两点间的距离】 (C语言代码)浏览:884 |
Pascal三角 (C语言代码)浏览:1188 |
输出正反三角形 (C语言代码)格式错误!!!浏览:1141 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:600 |