[Codechef] TAQTREE - Queries On Tree

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : TAQTREE - Queries On Tree
Source            : Codechef
Category          : Graph Theory, Tree
Algorithm         : Easiest HLD Over Subtree and Paths 
Verdict           : Accepted

#include "bits/stdc++.h"
 
using namespace std;
 
static const int maxn = 2e5 + 5;
static const int logn = 19;
 
struct Edge
{
      int v, w, id;
      Edge(int v = 0, int w = 0, int id = 0) : v(v), w(w), id(id) {}
};
 
vector <Edge> graph[maxn];
vector <int> Tree[maxn];
int subtreeSize[maxn], Id[maxn];
int depth[maxn], father[maxn][logn];
int nxt[maxn], in[maxn], out[maxn], tym, nodeCost[maxn];
 
void makeTree(int u = 1, int p = -1)
{
      for (Edge e : graph[u])
      {
            int v = e.v;
            int w = e.w;
            int id = e.id;
            if (v == p) continue;
            Tree[u].push_back(v);
            nodeCost[v] = w;
            Id[id] = v;
            makeTree(v, u);
      }
}
 
void dfsSize(int u = 1)
{
      for (int i = 1; i < logn; i++) father[u][i] = father[ father[u][i-1] ][i-1];
      for (int v : Tree[u])
      {
            dfsSize(v);
            subtreeSize[u] += subtreeSize[v];
            if (subtreeSize[v] > subtreeSize[ Tree[u][0] ]) swap(v, Tree[u][0]);
      }
}
 
void hld(int u = 1)
{
      in[u] = ++tym;
      for (int v : Tree[u])
      {
            nxt[v] = v == Tree[u][0] ? nxt[u] : v;
            hld(v);
      }
      out[u] = tym;
}
 
void dfs(int u = 1)
{
      for (int i = 1; i < logn; i++) father[u][i] = father[ father[u][i-1] ][i-1];
      for (int v : Tree[u])
      {
            depth[v] = depth[u] + 1;
            father[v][0] = u;
            dfs(v);
      }
}
 
int findLCA(int u, int v)
{
      if (depth[u] < depth[v]) swap(u, v);
      for (int i = logn - 1; i >= 0; i--)
      {
            if (depth[ father[u][i] ] >= depth[v]) u = father[u][i];
      }
      if (u == v) return u;
      for (int i = logn - 1; i >= 0; i--)
      {
            if (father[u][i] != father[v][i])
            {
                  u = father[u][i];
                  v = father[v][i];
            }
      }
      return father[u][0];
}
 
int segTree[maxn * 4];
int arr[maxn], N;
 
void update(int node, int a, int b, int pos, int val)
{
      if (a > pos or b < pos) return;
      if (a >= pos and b <= pos)
      {
            segTree[node] = val;
            return;
      }
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = a + b >> 1;
      update(lft, a, mid, pos, val);
      update(rgt, mid + 1, b, pos, val);
      segTree[node] = segTree[lft] + segTree[rgt];
}
 
int query(int node, int a, int b, int i, int j)
{
      if (a > j or b < i) return 0;
      if (a >= i and b <= j) return segTree[node];
      int lft = node << 1;
      int rgt = lft | 1;
      int mid = a + b >> 1;
      int p = query(lft, a, mid, i, j);
      int q = query(rgt, mid + 1, b, i, j);
      return p + q;
}
 
int queryUp(int u, int v)
{
      // u = niche, v = lca
      int sum = 0;
      int L = in[v];
      while (true)
      {
            int l = in[ nxt[u] ];
            int r = in[u];
            if (l <= L)
            {
                  l = max(l, L);
                  sum += query(1, 1, N, l, r);
                  break;
            }
            sum += query(1, 1, N, l, r);
            u = father[ nxt[u] ][0];
      }
      return sum;
}
 
int queryhld(int u, int v)
{
      int lca = findLCA(u, v);
      int lft = queryUp(u, lca);
      int rgt = queryUp(v, lca);
      int middle = queryUp(lca, lca);
      return queryUp(u, lca) + queryUp(v, lca) - 2 * queryUp(lca, lca);
}
 
void updatehld(int u, int val)
{
      nodeCost[u] = val;
      update(1, 1, N, in[u], val);
}
 
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 tnode;
      cin >> tnode;
      for (int e = 1; e < tnode; e++)
      {
            int u, v, w;
            cin >> u >> v >> w;
            graph[u].emplace_back(v, w, e);
            graph[v].emplace_back(u, w, e);
      }
      makeTree();
      dfsSize();
      nxt[1] = 1;
      hld();
      depth[1] = 1;
      dfs();
      N = tnode;
 
      for (int i = 1; i <= tnode; i++)
      {
//            cerr << i << ' ' << nodeCost[i] << ' ' << Id[i] << endl;
            updatehld(i, nodeCost[i]);
      }
 
      int q;
      cin >> q;
      while (q--)
      {
            int type;
            cin >> type;
            if (type == 1)
            {
                  int id, val;
                  cin >> id >> val;
                  updatehld(Id[id], val);
            }
            else
            {
                  int u, v;
                  cin >> u >> v;
                  cout << queryhld(u, v) << endl;
            }
      }
}
 

[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();  
}