Pagini recente » Cod sursa (job #2684532) | Cod sursa (job #1645574) | Cod sursa (job #2184747) | Cod sursa (job #2414183) | Cod sursa (job #772479)
Cod sursa(job #772479)
#include<fstream>
using namespace std;
ifstream fin("rmq.in"); ofstream fout("rmq.out");
int n, m, rmq[100001][18], a[100001], Log[100001];
void preprocess_RMQ(){
int i, j, lng, half;
//process intervals of length 1
for (i = 0; i < n; i++) rmq[i][0] = i;
//process bigger intervals
for (j = 1, lng = 2; lng < n; lng = 1 << ++j)
for (i = 0, half = lng / 2; i + lng <= n; i++)
rmq[i][j] = a[rmq[i][j - 1]] > a[rmq[i + half][j - 1]] ? rmq[i + half][j - 1] : rmq[i][j] = rmq[i][j - 1];
}
int Minim(int x, int y){
int l_min = a[rmq[x][Log[y - x]]];
int r_min = a[rmq[y - (1 << Log[y - x]) + 1][Log[y - x]]];
return l_min < r_min ? l_min : r_min;
}
int main(){
int i, j, x, y, p;
fin >> n >> m;
for (i = 0; i < n; i++) fin >> a[i];
for (i = 0, p = 1; p <= n; p = 1 << ++i)
for (j = p; j < p * 2 && j <= n; j++)
Log[j] = i;
preprocess_RMQ();
for (i = 0; i < m; i++)
fin >> x >> y, fout << Minim(x - 1, y - 1) << "\n";
}