[Codechef] DIVMAC - Dividing Machine

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : DIVMAC - Dividing Machine
Source            : Codechef
Category          : Number Theory, Data Structure
Algorithm         : Sieve - Smallest Prime Factor, Segment Tree
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll           long long int   
#define endl         '\n'  
  
static const int maxn = 2e6 + 5;  
  
bool isprime[maxn];  
vector <int> prime;  
int sp[maxn];  
  
void sieve()  
{  
    for (int i = 2; i < maxn; i++) isprime[i] = true;  
    sp[2] = 2;  
    for (int i = 4; i < maxn; i += 2) isprime[i] = false, sp[i] = 2;  
    for (long long i = 3; i < maxn; i += 2)  
    {  
        if (isprime[i])  
        {  
            sp[i] = i;  
            for (long long j = i; i * j < maxn; j += 2)  
            {  
                if (isprime[i * j])  
                {  
                    isprime[i * j] = false;  
                    sp[i * j] = i;  
                }  
            }  
        }  
    }  
    prime.push_back(2);  
    for (int i = 3; i < maxn; i += 2) if (isprime[i]) prime.push_back(i);  
}  
  
struct SegmentTree  
{  
    int num;  
    int lpf;  
    SegmentTree(int num = 0, int lpf = 0) : num(num), lpf(lpf) {}  
      
    void assignLeaf(int x, int y)  
    {  
        num = x;  
        lpf = y;  
    }  
    void marge(const SegmentTree &lchild, const SegmentTree &rchild)  
    {  
        num = max(lchild.num, rchild.num);  
        lpf = max(lchild.lpf, rchild.lpf);  
    }  
} Tree[maxn * 4];  
  
int arr[maxn];  
  
void build(int node, int a, int b)  
{  
    if (a == b) return void(Tree[node].assignLeaf(arr[a], sp[ arr[a] ]));  
    int lchild = node * 2;  
    int rchild = lchild + 1;  
    int mid = (a + b) / 2;  
    build(lchild, a, mid);  
    build(rchild, mid + 1, b);  
    Tree[node].marge(Tree[lchild], Tree[rchild]);  
}  
  
void update(int node, int a, int b, int i, int j)  
{  
    if (a > j or b < i) return;  
    if (a == b)   
    {  
        int num = Tree[node].num / sp[ Tree[node].num ];  
        int lpf = max(1, sp[num]);  
        Tree[node].assignLeaf(num, lpf);  
        return;  
    }  
    int lchild = node * 2;  
    int rchild = lchild + 1;  
    int mid = (a + b) / 2;  
    if (Tree[lchild].num >= 2) update(lchild, a, mid, i, j);  
    if (Tree[rchild].num >= 2) update(rchild, mid + 1, b, i, j);  
    Tree[node].marge(Tree[lchild], Tree[rchild]);  
}  
  
int query(int node, int a, int b, int i, int j)  
{  
    if (a > j or b < i) return 1;  
    if (a >= i and b <= j) return Tree[node].lpf;  
    int lchild = node * 2;  
    int rchild = lchild + 1;  
    int mid = (a + b) / 2;  
    int p = query(lchild, a, mid, i, j);  
    int q = query(rchild, mid + 1, b, i, j);  
    return max(p, q);   
}  
  
signed main()  
{  
    ios_base::sync_with_stdio(false);  
    cin.tie(nullptr);  
    cout.tie(nullptr);  
      
    sieve();  
      
    int tc;  
    cin >> tc;  
    while (tc--)  
    {  
        int n, m;  
        cin >> n >> m;  
        for (int i = 1; i <= n; i++) cin >> arr[i];  
        build(1, 1, n);  
        while (m--)  
        {  
            int type, l, r;  
            cin >> type >> l >> r;  
            if (type == 0) update(1, 1, n, l, r);  
            else cout << query(1, 1, n, l, r) << ' ';  
            for (int i = 1; i <= n; i++) cerr << query(1, 1, n, i, i) << ", ";  
            cerr << endl;  
        }  
        cout << endl;  
    }  
}  

[Toph] Jontrona of Liakot

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : Jontrona of Liakot
Source            : Toph.co
Category          : Data Structure, Graph Theory, Tree
Algorithm         : Persistent Trie
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll           long long int  
#define endl         '\n'  
  
static const int maxn = 2e5 + 5;  
static const int maxp = 6e6 + 6;  
  
struct Node  
{  
      int st;  
      int lchild;  
      int rchild;  
      Node(int st = 0, int lchild = 0, int rchild = 0)  
            : st(st)  
            , lchild(lchild)  
            , rchild(rchild) {}  
} Tree[maxp];  
  
int version[maxn];  
int NODES;  
  
int update(int root, int pos, int val)  
{  
      int newNode = ++NODES;  
      Tree[newNode] = Tree[root];  
      if (pos < 0)  
      {  
            Tree[newNode].st += 1;  
            return newNode;  
      }  
      int bit = (bool)(val & (1 << pos));  
      if (bit == 0) Tree[newNode].lchild = update(Tree[newNode].lchild, pos - 1, val);  
      else Tree[newNode].rchild = update(Tree[newNode].rchild, pos - 1, val);  
      Tree[newNode].st = Tree[ Tree[newNode].lchild ].st + Tree[ Tree[newNode].rchild ].st;  
      return newNode;  
}  
  
int kth(int root1, int root2, int root3, int root4, int pos, int k, int xor_val)  
{  
      if (pos < 0) return 0;  
      bool bit = (bool)(xor_val & (1 << pos));  
      int bad = 0;  
      if (bit == 0)  
      {  
            bad = Tree[ Tree[root4].lchild ].st - Tree[ Tree[root1].lchild ].st -  
                  Tree[ Tree[root3].lchild ].st + Tree[ Tree[root2].lchild ].st;  
            if (bad < k) return (1 << pos) + kth(Tree[root1].rchild, Tree[root2].rchild, Tree[root3].rchild, Tree[root4].rchild, pos - 1, k - bad, xor_val);  
            else return kth(Tree[root1].lchild, Tree[root2].lchild, Tree[root3].lchild, Tree[root4].lchild, pos - 1, k, xor_val);  
      }  
      else  
      {  
            bad = Tree[ Tree[root4].rchild ].st - Tree[ Tree[root1].rchild ].st -  
                  Tree[ Tree[root3].rchild ].st + Tree[ Tree[root2].rchild ].st;  
            if (bad < k) return (1 << pos) + kth(Tree[root1].lchild, Tree[root2].lchild, Tree[root3].lchild, Tree[root4].lchild, pos - 1, k - bad, xor_val);  
            else kth(Tree[root1].rchild, Tree[root2].rchild, Tree[root3].rchild, Tree[root4].rchild, pos - 1, k, xor_val);  
      }  
}  
  
vector < vector <int> > graph;  
int in[maxn];  
int out[maxn];  
int which[maxn];  
int dfsTime;  
  
void dfs(int u = 1, int p = -1)  
{  
      in[u] = ++dfsTime;  
      which[dfsTime] = u;  
      for (int v : graph[u])  
      {  
            if (v == p) continue;  
            dfs(v, u);  
      }  
      out[u] = dfsTime;  
}  
  
int arr[maxn];  
  
signed 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 n, q;  
      cin >> n >> q;  
      for (int i = 1; i <= n; i++) cin >> arr[i];  
      graph.resize(n + 1);  
      for (int e = 1; e < n; e++)  
      {  
            int u, v;  
            cin >> u >> v;  
            graph[u].push_back(v);  
            graph[v].push_back(u);  
      }  
      dfs();  
      for (int i = 1; i <= n; i++) version[i] = update(version[i - 1], 30, arr[ which[i] ]);  
      while (q--)  
      {  
            int u, v, z, k;  
            cin >> u >> v >> z >> k;  
            int root1 = version[ in[u] - 1 ];  
            int root2 = version[ in[v] - 1 ];  
            int root3 = version[ out[v] ];  
            int root4 = version[ out[u] ];  
            int sze = out[u] - in[u] + 1 - (out[v] - in[v] + 1);  
            if (sze < k)  
            {  
                  cout << "-1" << endl;  
            }  
            else  
            {  
                  int ans = kth(root1, root2, root3, root4, 30, k, z);  
                  cout << ans << endl;  
            }  
      }  
}