static_range_minimum_queries_1647.cpp (1080B)
1 #include <iostream> 2 #include <limits> 3 #include <vector> 4 5 int minrange(std::vector<int>& a, int x, int y, int i, int p, int l, int r) { 6 if (x == l && y == r) 7 return a[2*p-2-i]; 8 9 if (x >= y) 10 return std::numeric_limits<int>::max(); 11 12 int lr = (l+r)/2; 13 return std::min( 14 minrange(a, std::max(x, l), std::min(y, lr), 2*i+2, p, l, lr), 15 minrange(a, std::max(x, lr), std::min(y, r), 2*i+1, p, lr, r) 16 ); 17 } 18 19 void compute_mins(std::vector<int>& a, int j, int n) { 20 for (int i = 0; i < n; i += 2) 21 a[j+n+i/2] = std::min(a[j+i], a[j+i+1]); 22 } 23 24 int main() { 25 int n, q, x, y, p; 26 std::cin >> n >> q; 27 28 // For simplicity, extend n to a power of 2 29 for (p = 1; p < n; p <<= 1) ; 30 31 std::vector<int> a(2*p-1, 0); 32 for (int i = 0; i < n; i++) 33 std::cin >> a[i]; 34 35 // a[p], a[p+1] ... a[p+p/2-1] are min of pairs 36 // a[p+p/2], a[p+p/2+1], ... a[p+p/2+p/4] are min of quads 37 // etc... 38 for (int i = 1, j = 0; i < p; i <<= 1) { 39 compute_mins(a, j, p/i); 40 j += p/i; 41 } 42 43 for (int i = 0; i < q; i++) { 44 std::cin >> x >> y; 45 std::cout << minrange(a, x-1, y, 0, p, 0, p) << "\n"; 46 } 47 }