题目链接:http://www.lightoj.com/volume_showproblem.php?problem=1082 真心不解释,如果加一个U操作简直可以跟前几天发的某一道题配对儿了。。
![](/Images/OutliningIndicators/ContractedBlock.gif) view code 1 #include <iostream> 2 #include <cstdio> 3 #include <cstdlib> 4 #include <cstring> 5 #include <cmath> 6 #include <algorithm> 7 using namespace std; 8 #define lson l, m, rt << 1 9 #define rson m + 1, r, rt << 1 | 1 10 const int maxn = 100010; 11 int MIN[maxn << 2]; 12 void PushUp(int rt) 13 { 14 MIN[rt] = min(MIN[rt << 1], MIN[rt << 1 | 1]); 15 } 16 void build(int l, int r, int rt) 17 { 18 if (l == r) 19 { 20 scanf("%d", &MIN[rt]); 21 return; 22 } 23 int m = (l + r) >> 1; 24 build(lson); 25 build(rson); 26 PushUp(rt); 27 } 28 int query(int ll, int rr, int l, int r, int rt) 29 { 30 if (ll <= l && rr >= r) return MIN[rt]; 31 int m = (l + r) >> 1; 32 int ret = maxn; 33 if (ll <= m) ret = min(ret, query(ll, rr, lson)); 34 if (rr > m) ret = min(ret, query(ll, rr, rson)); 35 return ret; 36 } 37 int main() 38 { 39 int t; 40 scanf("%d", &t); 41 for (int i = 1; i <= t; i++) 42 { 43 printf("Case %d:\n", i); 44 int n, m; scanf("%d%d", &n, &m); 45 build(1, n, 1); 46 while (m--) 47 { 48 int x, y; 49 scanf("%d%d", &x, &y); 50 int ans = query(x, y, 1, n, 1); 51 printf("%d\n", ans); 52 } 53 } 54 return 0; 55
|