Created
February 24, 2017 08:29
-
-
Save yDeepak1889/3ae6a8325532448b3493de5492df8ba9 to your computer and use it in GitHub Desktop.
Find Minimum between l ans r ( 0<=l <=r <=n-1) using sparse Table
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <bits/stdc++.h> | |
using namespace std; | |
#define ll long long | |
#define pint pair<int, int> | |
#define pll pair<ll, ll> | |
#define mk(a, b) make_pair(a, b) | |
#define pr(n) printf("%d\n", n) | |
#define sc(n) scanf ("%d", &n) | |
#define scll(n) scanf ("%lld", &n) | |
#define prll(n) printf("%lld\n", n) | |
#define MOD 1000000007ll | |
int n, q; | |
int arr[100000]; | |
const int k = 16; | |
int table[100000][k+1]; | |
void buildTable() { | |
int i; | |
for (i = 0; i < n; i++) { | |
table[i][0] = arr[i]; | |
} | |
int j; | |
for (j = 1; j <= k; j++) { | |
for (i = 0; i <= n-(1<<j); i++) { | |
table[i][j] = min(table[i][j-1], table[i+(1<<(j-1))][j-1]); | |
} | |
} | |
return ; | |
} | |
int query(int l, int r) { | |
int i; | |
int ans = MOD; | |
for (i = k; i >= 0; i--) { | |
if (l+(i<<k)-1 <= r) { | |
ans = min(ans, table[l][i]); | |
l = l + (1<<k); | |
} | |
} | |
return ans; | |
} | |
int main (void) { | |
sc(n); | |
int i; | |
for (i = 0; i < n; i++) { | |
sc(arr[i]); | |
} | |
buildTable(); | |
sc(q); | |
int l, r; | |
while (q--) { | |
sc(l), sc(r); | |
pr(query(l, r)); | |
} | |
return 0; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment