[Codechef] SEGPROD - Product on the segment by modulo

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : SEGPROD - Product on the segment by modulo
Source            : Codechef
Category          : Data Structure
Algorithm         : Disjoint Sparse Table 
Verdict           : Accepted

#include <bits/stdc++.h>  
  
using namespace std;  
  
#define ll                long long  
  
static const int maxn = 3e6 + 50;  
static const int Max = 2e7 + 5;  
static const int logn = 20;  
  
ll arr[maxn], dst[maxn][logn];  
ll p;  
ll queries[Max];  
  
ll mul(ll a, ll b)  
{  
      return (a * b) % p;  
}  
  
void buildDST(int h, int l, int r)  
{  
      if (h < 0) return;  
      int mid = (l + r) >> 1;  
      ll product = 1;  
      for (int i = mid - 1; i >= l; i--)  // Suffix calculation  
      {  
            dst[i][h] = mul(product, arr[i]);  
            product = mul(product, arr[i]);  
      }  
      product = 1;  
      for (int i = mid; i < r; i++) // Prefix calculation  
      {  
            dst[i][h] = mul(product, arr[i]);  
            product = mul(product, arr[i]);  
      }  
      buildDST(h-1, l, mid);  
      buildDST(h-1, mid, r);  
}  
  
ll query(int l, int r)  
{  
      if (l == r) return arr[l]; // Base Case  
      int h = 31 - __builtin_clz(l ^ r);  
      return mul(dst[l][h], dst[r][h]);  
}  
  
void solve()  
{  
      int n, q;  
      cin >> n >> p >> q;  
      for (int i = 0; i < n; i++)  
      {  
            cin >> arr[i];  
            arr[i] %= p;  
      }  
      int h = 1;  
      while ((1 << h) < n) ++h;  
      buildDST(h-1, 0, (1 << h));  
      int totalQuery = q / 64 + 2;  
      for (int i = 0; i < totalQuery; i++) cin >> queries[i];  
      ll l = 0, r = 0;  
      ll last = 0;  
      for (int i = 0; i < q; i++)  
      {  
            if (i % 64 == 0)  
            {  
                  l = (queries[i / 64] + last) % n;  
                  r = (queries[i / 64 + 1] + last) % n;  
            }  
            else  
            {  
                  l = (l + last) % n;  
                  r = (r + last) % n;  
            }  
            if (l > r) swap(l, r);  
            ll ans = query(l, r);  
            last = (ans + 1) % p;  
      }  
      cout << last << '\n';  
}  
  
int main()  
{  
      ios_base::sync_with_stdio(false);  
      cin.tie(nullptr);  
      cout.tie(nullptr);  
  
      #ifndef ONLINE_JUDGE  
            freopen("in.txt", "r", stdin);  
      #endif // ONLINE_JUDGE  
  
      int tc;  
      cin >> tc;  
      for (int tcase = 1; tcase <= tc; tcase++) solve();  
}