题目链接
题目描述 老管家是一个聪明能干的人。他为财主工作了整整 $10$ 年,财主为了让自已账目更加清楚。要求管家每天记 $k$ 次账,由于管家聪明能干,因而管家总是让财主十分满意。但是由于一些人的挑拨,财主还是对管家产生了怀疑。于是他决定用一种特别的方法来判断管家的忠诚,他把每次的账目按 $1,2,3 \cdots$ 编号,然后不定时的问管家问题,问题是这样的:在 $a$ 到 $b$ 号账中最少的一笔是多少?为了让管家没时间作假他总是一次问多个问题。
输入格式 输入中第一行有两个数 $m,n$ 表示有 $m$($m \le 10^5$)笔账,$n$ 表示有 $n$ 个问题,$n \le 10^5$。
第二行为 $m$ 个数,分别是账目的钱数
后面 $n$ 行分别是 $n$ 个问题,每行有 $2$ 个数字说明开始结束的账目编号。
输出格式 输出文件中为每个问题的答案。
题解 当然可以用线段树来维护,但是这里选择树状数组会更加精炼
当然,树状数组也有其弊端,对于没有被包含的单个节点,就需要一个一个比较了……这会大大降低效率!
upd: ST 表(这个会快很多,重点在于没有修改)
代码
树状数组
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 #include <iostream> #include <algorithm> #include <cstring> using namespace std ;const int N = 1e5 + 5 ;int n, m;int t[N], a[N];int x, y;void add (int x, int k) { while (x <= n) { if (t[x] > k) t[x] = k; else return ; x += x & -x; } } int getmin (int x, int y) { int r = 2147483647 ; while (y >= x) { if (y - (y & -y) > x) { r = min(r, t[y]); y -= y & -y; } else { r = min(r, a[y]); --y; } } return r; } int main () { ios::sync_with_stdio(0 ); cin >> n >> m; memset (t, 127 , sizeof (t)); for (int i = 1 ; i <= n; i++) { cin >> a[i]; add(i, a[i]); } for (int i = 1 ; i <= m; i++) { cin >> x >> y; cout << getmin(x, y) << ' ' ; } return 0 ; }
线段树
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 #include <bits/stdc++.h> using namespace std ;#define ll long long const int N = 1e5 + 5 ;int n, m, op, x, y, k;ll a[N]; struct node { ll min_p, sum, tag; } T[N << 2 ]; inline ll min (ll a, ll b) { return a > b ? b : a; }inline int ls (ll p) { return p << 1 ; }inline int rs (ll p) { return p << 1 | 1 ; }inline void push_up (ll p) { T[p].sum = T[ls(p)].sum + T[rs(p)].sum; T[p].min_p = min(T[ls(p)].min_p, T[rs(p)].min_p); } void build (ll p, ll l, ll r) { T[p].tag = 0 ; T[p].min_p = 0x3f3f3f3f ; if (l == r) { T[p].min_p = T[p].sum = a[l]; return ; } ll mid = (l + r) >> 1 ; build(ls(p), l, mid); build(rs(p), mid + 1 , r); push_up(p); } inline void push_down (ll p, ll l, ll r) { ll mid = (l + r) >> 1 ; T[ls(p)].sum += T[p].tag * (r - l + 1 ); T[ls(p)].tag += T[p].tag; T[rs(p)].sum += T[p].tag * (r - l + 1 ); T[rs(p)].tag += T[p].tag; T[p].tag = 0 ; } ll query_min (ll q_x, ll q_y, ll l, ll r, ll p) { if (q_x <= l && r <= q_y) return T[p].min_p; ll mid = (l + r) >> 1 , resa = 0x3f3f3f3f , resb = 0x3f3f3f3f ; push_down(p, l, r); if (q_x <= mid) resa = query_min(q_x, q_y, l, mid, ls(p)); if (q_y > mid) resb = query_min(q_x, q_y, mid + 1 , r, rs(p)); return min(resa, resb); } int main () { ios::sync_with_stdio(false ); cin >> n >> m; for (int i = 1 ; i <= n; i++) cin >> a[i]; build(1 , 1 , n); for (int i = 1 ; i <= m; i++) { cin >> x >> y; cout << query_min(x, y, 1 , n, 1 ) << " " ; } return 0 ; }
ST 表
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 #include <bits/stdc++.h> using namespace std ;int lg2 (int n, int result = 0 ) { if (n & 0xffff0000 ) result += 16 , n >>= 16 ; if (n & 0x0000ff00 ) result += 8 , n >>= 8 ; if (n & 0x000000f0 ) result += 4 , n >>= 4 ; if (n & 0x0000000c ) result += 2 , n >>= 2 ; if (n & 0x00000002 ) result += 1 , n >>= 1 ; return result; } const int N = 1e6 + 5 ;int n, m, f[25 ][N], l, r;inline char getcha () { static char buf[100000 ], *p1 = buf, *p2 = buf; return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1 , 100000 , stdin ), p1 == p2) ? EOF : *p1++; } inline int read () { char ch = getcha(); int ret = 0 , f = 1 ; while (!isdigit (ch)) { if (ch == '-' ) f = -f; ch = getcha(); } while (isdigit (ch)) { ret = (ret << 1 ) + (ret << 3 ) + ch - '0' ; ch = getcha(); } return ret * f; } char pbuf[100000 ], *pp = pbuf;void push (const char c) { if (pp - pbuf == 100000 ) fwrite(pbuf, 1 , 100000 , stdout ), pp = pbuf; *pp++ = c; } void write (int x) { static int sta[35 ]; int top = 0 ; do { sta[top++] = x % 10 , x /= 10 ; } while (x); while (top) push(sta[--top] + '0' ); push(' ' ); } int main () { n = read(), m = read(); for (int i = 1 ; i <= n; i++) f[0 ][i] = read(); for (int j = 1 ; j <= 21 ; j++) for (int i = 1 ; i + (1 << j) - 1 <= n; i++) f[j][i] = min(f[j - 1 ][i], f[j - 1 ][i + (1 << (j - 1 ))]); for (int i = 1 ; i <= m; i++) { l = read(), r = read(); int s = lg2(r - l + 1 ); write(min(f[s][l], f[s][r - (1 << s) + 1 ])); } fwrite(pbuf, 1 , pp - pbuf, stdout ); pp = pbuf; return 0 ; }
注意
要初始化为最大值