[toph.co] Smallest Subarray

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Smallest Subarray
Source            : toph.co
Category          : String, Data Structure
Algorithm         : Suffix Array, Sparse Table
Verdict           : Accepted

#include <bits/stdc++.h>
 
using namespace std;
 
static const int maxn = 65536;
static const int logn = 22;
 
struct entry
{
      int nr[3];
      int p;
} L[maxn];
 
int P[logn][maxn];
int A[maxn];
int N, Q;
int stp, cnt;
 
int ST[logn][maxn];
int arr[maxn];
 
inline int cmp(struct entry a, struct entry b)
{
      if (a.nr[0] == b.nr[0])
      {
            if (a.nr[1] < b.nr[1]) return 1;
            else return 0;
      }
      else
      {
            if (a.nr[0] < b.nr[0]) return 1;
            else return 0;
      }
}
 
inline void suffix_array()
{
      for (int i = 0; i < N; i++) P[0][i] = A[i];
      for (stp = 1, cnt = 1; cnt < N; stp++, cnt *= 2)
      {
            for (int i = 0; i < N; i++)
            {
                  L[i].nr[0] = P[stp-1][i];
                  L[i].nr[1] = (i + cnt) < N ? P[stp-1][i+cnt] : -1;
                  L[i].p = i;
            }
            sort(L, L+N, cmp);
            for (int i = 0; i < N; i++)
            {
                  if (i > 0 && L[i].nr[0] == L[i-1].nr[0] && L[i].nr[1] == L[i-1].nr[1])
                        P[stp][L[i].p] = P[stp][L[i-1].p];
                  else
                        P[stp][L[i].p] = i;
            }
      }
      for (int i = 0; i < N; i++) arr[L[i].p] = i;
}
 
inline void compute_sparse_table()
{
      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-1)) < N; i++)
            {
                  int x = ST[k-1][i];
                  int y = ST[k-1][i + (1 << (k-1))];
                  ST[k][i] = arr[x] <= arr[y] ? x : y;
            }
      }
}
 
inline int RMQ(int i, int j)
{
      int k = log2(j - i + 1);
      int x = ST[k][i];
      int y = ST[k][j + 1 - (1 << k)];
      return arr[x] <= arr[y] ? x : y;
}
 
int main()
{
//      freopen("in.txt", "r", stdin);
 
      int tc;
      scanf("%d", &tc);
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            scanf("%d %d", &N, &Q);
            for (int i = 0; i < N; i++) scanf("%d", &A[i]);
            suffix_array();
            compute_sparse_table();
            printf("Case %d:\n", tcase);
            while (Q--)
            {
                  int a, b;
                  scanf("%d %d", &a, &b);
                  a--;
                  b--;
                  int pos = RMQ(a, b) + 1;
                  printf("%d\n", pos);
            }
      }
}