Showing posts with label Persistent Trie. Show all posts
Showing posts with label Persistent Trie. Show all posts

Saturday, March 25, 2023

[Hackerearth] Prefix queries


Algorithm: Persistent Trie

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
const int maxn = 3e5 + 5;
const int maxbit = 62;
const int MAXNODES = 2e7;
 
// https://www.hackerearth.com/practice/data-structures/advanced-data-structures/trie-keyword-tree/practice-problems/algorithm/prefix-queries-3-2c111491/
struct Node {
    int st, lchild, rchild;
    Node(int st = 0, int lchild = 0, int rchild = 0)
        : st(st), lchild(lchild), rchild(rchild) {}
};
 
int NODES;
Node Tree[MAXNODES];
int version[maxn];
 
int update(int root, int pos, int val, int add) {
    int newNode = ++NODES;
    Tree[newNode] = Tree[root];
    if (pos < 0) {
        Tree[newNode].st += add;
        return newNode;
    }
    bool bit = val >> pos & 1LL;
    if (bit == 0) {
        Tree[newNode].lchild = update(Tree[newNode].lchild, pos - 1, val, add);
    } else {
        Tree[newNode].rchild = update(Tree[newNode].rchild, pos - 1, val, add);
    }
    Tree[newNode].st = Tree[ Tree[newNode].lchild ].st + Tree[ Tree[newNode].rchild ].st;
    return newNode;
}
 
int getMaxPrefix(int root, int pos, int val) {
    if (pos < 0) {
        return 0;
    }
    bool bit = val >> pos & 1LL;
    if (bit == 0 and Tree[ Tree[root].lchild ].st > 0) {
        return 1 + getMaxPrefix(Tree[root].lchild, pos - 1, val);
    } else if (bit == 1 and Tree[ Tree[root].rchild ].st > 0) {
        return 1 + getMaxPrefix(Tree[root].rchild, pos - 1, val);
    }
    return 0;
}
 
int n;
int q;
vector<int> arr;
vector<vector<int>> graph;
vector<vector<pair<int, int>>> queries;
vector<vector<int>> level;
vector<int> par;
vector<int> ans;
 
void dfs(int u = 1, int p = 0, int lvl = 0) {
    version[1] = update(version[1], maxbit - 1, arr[u], 1);
    for (auto it : queries[u]) {
        ans[it.second] = getMaxPrefix(version[1], maxbit - 1, it.first);
    }
    for (int v : graph[u]) {
        if (v == p) {
            continue;
        }
        dfs(v, u);
    }
    version[1] = update(version[1], maxbit - 1, arr[u], -1);
}
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
    }
 
    int tc;
    cin >> tc;
    while (tc--) {
        cin >> n;
        arr.clear(); arr.resize(n + 1);
        NODES = 0;
        for (int i = 1; i <= n; i++) {
            cin >> arr[i];
        }
        graph.clear(); 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);
        }
        cin >> q;
        queries.clear(); queries.resize(n + 1);
        for (int i = 0; i < q; i++) {
            int v, x;
            cin >> v >> x;
            queries[x].push_back({v, i});
        }
        ans.resize(q);
        dfs();
        for (int x : ans) {
            cout << x << ' ';
        }
        cout << endl;
 
        for (int i = 0; i <= NODES; i++) {
            Tree[i] = Node();
        }
    }
} 

  

Thursday, January 30, 2020

[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

  1. #include "bits/stdc++.h"  
  2.   
  3. using namespace std;  
  4.   
  5. #define ll           long long int  
  6. #define endl         '\n'  
  7.   
  8. static const int maxn = 2e5 + 5;  
  9. static const int maxp = 6e6 + 6;  
  10.   
  11. struct Node  
  12. {  
  13.       int st;  
  14.       int lchild;  
  15.       int rchild;  
  16.       Node(int st = 0, int lchild = 0, int rchild = 0)  
  17.             : st(st)  
  18.             , lchild(lchild)  
  19.             , rchild(rchild) {}  
  20. } Tree[maxp];  
  21.   
  22. int version[maxn];  
  23. int NODES;  
  24.   
  25. int update(int root, int pos, int val)  
  26. {  
  27.       int newNode = ++NODES;  
  28.       Tree[newNode] = Tree[root];  
  29.       if (pos < 0)  
  30.       {  
  31.             Tree[newNode].st += 1;  
  32.             return newNode;  
  33.       }  
  34.       int bit = (bool)(val & (1 << pos));  
  35.       if (bit == 0) Tree[newNode].lchild = update(Tree[newNode].lchild, pos - 1, val);  
  36.       else Tree[newNode].rchild = update(Tree[newNode].rchild, pos - 1, val);  
  37.       Tree[newNode].st = Tree[ Tree[newNode].lchild ].st + Tree[ Tree[newNode].rchild ].st;  
  38.       return newNode;  
  39. }  
  40.   
  41. int kth(int root1, int root2, int root3, int root4, int pos, int k, int xor_val)  
  42. {  
  43.       if (pos < 0) return 0;  
  44.       bool bit = (bool)(xor_val & (1 << pos));  
  45.       int bad = 0;  
  46.       if (bit == 0)  
  47.       {  
  48.             bad = Tree[ Tree[root4].lchild ].st - Tree[ Tree[root1].lchild ].st -  
  49.                   Tree[ Tree[root3].lchild ].st + Tree[ Tree[root2].lchild ].st;  
  50.             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);  
  51.             else return kth(Tree[root1].lchild, Tree[root2].lchild, Tree[root3].lchild, Tree[root4].lchild, pos - 1, k, xor_val);  
  52.       }  
  53.       else  
  54.       {  
  55.             bad = Tree[ Tree[root4].rchild ].st - Tree[ Tree[root1].rchild ].st -  
  56.                   Tree[ Tree[root3].rchild ].st + Tree[ Tree[root2].rchild ].st;  
  57.             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);  
  58.             else kth(Tree[root1].rchild, Tree[root2].rchild, Tree[root3].rchild, Tree[root4].rchild, pos - 1, k, xor_val);  
  59.       }  
  60. }  
  61.   
  62. vector < vector <int> > graph;  
  63. int in[maxn];  
  64. int out[maxn];  
  65. int which[maxn];  
  66. int dfsTime;  
  67.   
  68. void dfs(int u = 1, int p = -1)  
  69. {  
  70.       in[u] = ++dfsTime;  
  71.       which[dfsTime] = u;  
  72.       for (int v : graph[u])  
  73.       {  
  74.             if (v == p) continue;  
  75.             dfs(v, u);  
  76.       }  
  77.       out[u] = dfsTime;  
  78. }  
  79.   
  80. int arr[maxn];  
  81.   
  82. signed main()  
  83. {  
  84.       ios_base::sync_with_stdio(false);  
  85.       cin.tie(nullptr);  
  86.       cout.tie(nullptr);  
  87.   
  88.       #ifndef ONLINE_JUDGE  
  89.             freopen("in.txt", "r", stdin);  
  90.       #endif // ONLINE_JUDGE  
  91.   
  92.       int n, q;  
  93.       cin >> n >> q;  
  94.       for (int i = 1; i <= n; i++) cin >> arr[i];  
  95.       graph.resize(n + 1);  
  96.       for (int e = 1; e < n; e++)  
  97.       {  
  98.             int u, v;  
  99.             cin >> u >> v;  
  100.             graph[u].push_back(v);  
  101.             graph[v].push_back(u);  
  102.       }  
  103.       dfs();  
  104.       for (int i = 1; i <= n; i++) version[i] = update(version[i - 1], 30, arr[ which[i] ]);  
  105.       while (q--)  
  106.       {  
  107.             int u, v, z, k;  
  108.             cin >> u >> v >> z >> k;  
  109.             int root1 = version[ in[u] - 1 ];  
  110.             int root2 = version[ in[v] - 1 ];  
  111.             int root3 = version[ out[v] ];  
  112.             int root4 = version[ out[u] ];  
  113.             int sze = out[u] - in[u] + 1 - (out[v] - in[v] + 1);  
  114.             if (sze < k)  
  115.             {  
  116.                   cout << "-1" << endl;  
  117.             }  
  118.             else  
  119.             {  
  120.                   int ans = kth(root1, root2, root3, root4, 30, k, z);  
  121.                   cout << ans << endl;  
  122.             }  
  123.       }  
  124. }