শুক্রবার, ১৮ মে, ২০১৮

Range Minimum Query using Sparse Table

#include<bits/stdc++.h>
using namespace std;
#define Max 10000005
int ST[24][Max];
int A[Max];
void Compute_ST(int N)
{
    for (int i=0; i<N; i++)
        ST[0][i] = i;
    for (int k = 1; (1 << k)<N; k++)
    {
        for (int i=0; i+(1<<k)<=N; i++)
        {
            int x = ST[k-1][i];
            int y = ST[k-1][i+(1<<k-1)];
            ST[k][i]=A[x]<=A[y]?x:y;
        }
    }
}

int RMQ(int i, int j)
{
    int k = log2(j-i);
    int x = ST[k][i];
    int y = ST[k][j-(1<<k)+1];
    return A[x] <= A[y] ? x : y;
}

int main()
{
    int N;
    cin>>N;
    for(int i=0; i<N; i++)
    {
        cin>>A[i];
    }
    Compute_ST(N);
    int Q;
    cin>>Q;
    while(Q--)
    {
        int x,y;
        cin>>x>>y;
        cout<<A[RMQ(x,y)]<<endl;
    }
    return 0;
}

কোন মন্তব্য নেই:

একটি মন্তব্য পোস্ট করুন

Factorization with prime Sieve

vector <int> prime; char sieve[1000009]; int N=1000009; void primeSieve ( ) { sieve[0] = sieve[1] = 1; prime.push_back(2); ...