Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <bits/stdc++.h>
- #define NMAX 100005
- using namespace std;
- ifstream f ("rmq.in");
- ofstream g ("rmq.out");
- int n , m , x , y;
- int a[NMAX][20];
- void Compute()
- {
- for(int j = 1 ; (1 << j) <= n ; j++)
- for(int i = 1 ; i + (1 << j) - 1 <= n ; i++)
- if(a[i][j - 1] < a[i + (1 << (j - 1))][j - 1])
- a[i][j] = a[i][j - 1];
- else a[i][j] = a[i + (1 << (j - 1))][j - 1];
- }
- void Query(int c , int b)
- {
- int k = log2(b - c + 1);
- if(a[c][k] < a[b - (1 << k) + 1][k])
- g << a[c][k] << '\n';
- else g << a[b - (1 << k) + 1][k] << '\n';
- }
- int main()
- {
- f >> n >> m;
- for(int i = 1 ; i <= n ; i++)
- f >> a[i][0];
- Compute();
- for(int i = 1 ; i <= m ; i++)
- {
- f >> x >> y;
- Query(x , y);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement