題目描述
老管家是一個(gè)聰明能干的人。他為財(cái)主工作了整整10年，財(cái)主為了讓自已賬目更加清楚。要求管家每天記k次賬，由于管家聰明能干，因而管家總是讓財(cái)主十分滿意。但是由于一些人的挑撥，財(cái)主還是對(duì)管家產(chǎn)生了懷疑。于是他決定用一種特別的方法來判斷管家的忠誠，他把每次的賬目按1，2，3…編號(hào)，然后不定時(shí)的問管家問題，問題是這樣的：在a到b號(hào)賬中最少的一筆是多少？為了讓管家沒時(shí)間作假他總是一次問多個(gè)問題。
輸入格式
輸入中第一行有兩個(gè)數(shù)m,n表示有m(m<=100000)筆賬,n表示有n個(gè)問題，n<=100000。
第二行為m個(gè)數(shù),分別是賬目的錢數(shù)
后面n行分別是n個(gè)問題,每行有2個(gè)數(shù)字說明開始結(jié)束的賬目編號(hào)。
輸出格式
輸出文件中為每個(gè)問題的答案。具體查看樣例。
輸入輸出樣例
輸入 #1
10 3 1 2 3 4 5 6 7 8 9 10 2 7 3 9 1 10
輸出 #1
2 3 1
題解
這是一道線段樹的模板題目。我參考的線段樹模板來自：https://baijiahao.baidu.com/s?id=1605870136961096251&wfr=spider&for=pc。原來的模板是線段區(qū)間求和，現(xiàn)在改為區(qū)間求最小值。
1 #include <iostream> 2 #include <stdio.h> 3 #include <math.h> 4 #include <algorithm> 5 #include <string.h> 6 #define ll long long 7 8 const int MAXN = 1000001; 9 10 using namespace std; 11 12 ll n, m, a[MAXN], ans[MAXN<<2], tag[MAXN<<2]; 13 14 ll ls(ll x) 15 { 16 return x<<1; 17 } 18 19 ll rs(ll x) 20 { 21 return x<<1|1; 22 } 23 24 void push_up(ll p) 25 { 26 ans[p] = min(ans[ls(p)], ans[rs(p)]); 27 } 28 29 void build(ll p, ll l, ll r) 30 { 31 tag[p] = 0; 32 if(l == r) 33 { 34 ans[p] = a[l]; 35 return; 36 } 37 ll mid = (l + r) >> 1; 38 build(ls(p), l, mid); 39 build(rs(p), mid + 1, r); 40 push_up(p); 41 } 42 43 void f(ll p, ll l, ll r, ll k) 44 { 45 tag[p] = tag[p] + k; 46 ans[p] = ans[p] + k * (r - l + 1); 47 } 48 49 void push_down(ll p, ll l, ll r) 50 { 51 ll mid = (l + r)>>1; 52 f(ls(p), l, mid, tag[p]); 53 f(rs(p), mid + 1, r, tag[p]); 54 tag[p] = 0; 55 } 56 57 ll query(ll q_x, ll q_y, ll l, ll r, ll p) 58 { 59 ll res = 922337203685477580; 60 if(q_x <= l && r <= q_y) 61 { 62 return ans[p]; 63 } 64 ll mid = (l + r)>>1; 65 push_down(p, l, r); 66 if(q_x <= mid) 67 { 68 res = min(res, query(q_x, q_y, l, mid, ls(p))); 69 } 70 if(q_y > mid) 71 { 72 res = min(res, query(q_x, q_y, mid + 1, r, rs(p))); 73 } 74 return res; 75 } 76 77 int main() 78 { 79 ll e, f; 80 scanf("%lld%lld", &n, &m); 81 for(ll i = 1; i <= n; i++) 82 { 83 scanf("%lld", &a[i]); 84 } 85 build(1, 1, n); 86 for(ll i = 1; i <= m; i++) 87 { 88 scanf("%lld%lld", &e, &f); 89 printf("%lld ", query(e, f, 1, n, 1)); 90 } 91 return 0; 92 }
浙公網(wǎng)安備 33010602011771號(hào)