Square Root Decomposition Algorithm Code

#include<bits/stdc++.h>
using namespace std;
const int sz=100005;
const int inf=(1<<28);
template<typename t> t MIN3(t a,t b, t c)
{
    return min(a,min(b,c));
}
int block[400];
int arr[sz];
int getId(int indx,int blocksz)
{
    return indx/blocksz;
}
void init(int sz)
{
    for(int i=0; i<=sz; i++)
        block[i]=inf;
}
void update(int val,int indx,int blocksz)
{
    int id=getId(indx,blocksz);
    block[id]=min(block[id],val);
}
int query(int L,int R,int blocksz)
{
    int lid=getId(L,blocksz);
    int rid=getId(R,blocksz);
    if(lid==rid)
    {
        int ret=inf;
        for(int i=L; i<=R; i++)
            ret=min(ret,arr[i]);
        return ret;
    }
    int m1=inf,m2=inf,m3=inf;
    for(int i=L; i<(lid+1)*blocksz; i++)
        m1=min(m1,arr[i]);
    for(int i=lid+1; i<rid; i++)
        m2=min(m2,block[i]);
    for(int i=rid*blocksz; i<=R; i++)
        m3=min(m3,arr[i]);
    return MIN3(m1,m2,m3);
}
int main()
{
    int n,q;
    scanf("%d %d",&n,&q);
    int blocksz=sqrt(n);
    init(blocksz);
    for(int i=0; i<n; i++)
    {
        int x;
        scanf("%d",&x);
        arr[i]=x;
        update(x,i,blocksz);
    }
    while(q--)
    {
        int x,y;
        scanf("%d %d",&x,&y);
        printf("%d\n",query(x,y,blocksz));
    }
    return 0;
}