1416D - Graph and Queries - CodeForces Solution

#include <bits/stdc++.h>

using namespace std; 

typedef long long ll; 
typedef pair<int,int> ii; 

#define f(i,a,b) for(int i = a; i < b; i++)
#define fa(i,a,b) for(int i = a; i >= b; i--)

const int N = 2e5 + 5, M = 3e5 + 5, R = 5e5 + 5; 


int n, m, que; 
int Time, reach_id, ID; 
int val[N], p[2*N], a[N]; 
int l[2*N], r[2*N]; // [l[i], r[i]] : nodes in array that node i convers in the reach... 
int up[2*N][19], tin[2*N], tout[2*N], dfs_time; // for lca 
int child[2*N][2], t[2*N], deg_in[2*N]; // reach.. tree
int e1[M], e2[M]; // edges
int qt[R], q[R]; // queries 
int st[4*N]; // st
bool us[M]; // id - queries used 

void dfs(int u, int f){
    up[u][0] = f; 
    f(i,1,19) up[u][i] = up[up[u][i-1]][i-1]; 
    tin[u] = dfs_time++; 

    l[u] = 1e9, r[u] = -1e9; 

    bool leaf = 1; 
    f(i,0,2){  
        if(child[u][i] != 0){
            dfs(child[u][i], u); 
            l[u] = min(l[u], l[child[u][i]]); 
            r[u] = max(r[u], r[child[u][i]]); 
            leaf = 0; 
        }
    }

    // check if it's a leaf
    if(leaf){
        a[ID] = val[u]; // array of values for the st
        l[u] = r[u] = ID++;  
    }

    tout[u] = dfs_time++; 
}
bool is(int u, int v){
    return tin[u] <= tin[v] and tout[u] >= tout[v]; 
}
int lca(int u, int v){
    if(is(u, v)) return u; 
    if(is(v, u)) return v; 
    fa(i,18,0){
        if(up[u][i] == 0 or is(up[u][i], v)) continue; 
        u = up[u][i]; 
    }
    return up[u][0]; 
}
int find(int x){
    if(p[x] == x) return x; 
    return p[x] = find(p[x]); 
}
void uni(int x, int y, int TIME){
    x = find(x), y = find(y); 
    if(x == y) return; 
    p[x] = p[y] = p[reach_id] = reach_id; 
    child[reach_id][0] = x, child[reach_id][1] = y;
    deg_in[x]++, deg_in[y]++; 
    t[reach_id++] = TIME;  
}
void ini(){
    reach_id = n+1; 
    f(i,1,n+1) p[i] = i; 
}
void create_reachy(){
    ini(); 

    Time = 0; 
    f(i,1,m+1){ // edges
        if(!us[i]) uni(e1[i], e2[i], Time); 
    }
    fa(i,que,1){
        if(qt[i] == 2){
            Time++;  
            uni(e1[q[i]], e2[q[i]], Time); 
        }
    }

    // dfs to find lca + get array for the st 
    ID = 1; 
    fa(i,reach_id-1, 0){
        if(deg_in[i] == 0) dfs(i, 0); 
    }
}
int highest_node_time_less_than(int u, int TIME){
    fa(i,18,0){
        if(up[u][i] == 0 or t[up[u][i]] > TIME) continue;
        u = up[u][i]; 
    }
    return u; 
}
int merge(int u, int v){
    return (a[u] > a[v]) ? u : v;
}
void build(int id, int l, int r){
    if(l == r){
        st[id] = l; 
        return; 
    }
    int m = (l+r)>>1; 
    build(id<<1, l, m), build(id<<1|1, m+1, r); 
    st[id] = merge(st[id<<1], st[id<<1|1]); 
}
void upd(int id, int l, int r, int x){ // set a[x] to 0
    if(x < l or r < x) return; 
    if(l == r and l == x){
        st[id] = l; 
        a[l] = 0; 
        return; 
    }
    int m = (l+r)>>1; 
    upd(id<<1, l, m, x), upd(id<<1|1, m+1, r, x); 
    st[id] = merge(st[id<<1], st[id<<1|1]); 
}
int query(int id, int l, int r, int x, int y){
    if(y < l or r < x) return 0; 
    if(x <= l and r <= y) return st[id]; 
    int m = (l+r)>>1; 
    return merge(query(id<<1, l, m, x, y), query(id<<1|1, m+1, r, x, y)); 
}
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); 

    cin >> n >> m >> que; 
    
    f(i,1,n+1) cin >> val[i]; 

    f(i,1,m+1) cin >> e1[i] >> e2[i]; 

    f(i,1,que+1){
        cin >> qt[i] >> q[i];  
        if(qt[i] == 2) us[q[i]] = 1; 
    } 

    // reachability tree
    create_reachy(); 

    // segment tree (maximum) 
    build(1, 1, n); 

    // answer queries
    f(i,1,que+1){
        if(qt[i] == 2){
            Time--; 
            continue; 
        }
        int node = highest_node_time_less_than(q[i], Time); 
        int pos_maxi = query(1, 1, n, l[node], r[node]);  

        cout << a[pos_maxi] << "\n";  // print 
        upd(1, 1, n, pos_maxi); // update a[pos_maxi] in the st
    }
    return 0; 
}