Hi all!
Recently, I tried to implement a HLD struct. However, my local computer shows Segmentation Fault verdict as soon as I set the constraint of N to 1e5, the online judge shows TLE verdict btw. Small constraint on N works just fine. Here is the code:
Segmentation Fault Code
#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
const int N = 1e5 + 5;
int n;
template<typename seg_t>
struct HLD{
int P[N][20];
int parent[N];
int depth[N];
int child[N];
int bigChild[N];
int chain[N];
seg_t arr[N];
seg_t tree[3 * N];
int label[N];
int label_time = 0;
vector<int> g[N];
void update(int u, int low, int high, int idx, int val){
if(low > idx || high < idx) return;
if(low == high){
tree[u] = val;
return;
}
int mid = (low + high) / 2;
update(2 * u, low, mid, idx, val);
update(2 * u + 1, mid + 1, high, idx, val);
tree[u] = tree[2 * u] ^ tree[2 * u + 1];
}
seg_t get(int u, int low, int high, int l, int r){
if(low > r || high < l) return 0;
if(low >= l && high <= r) return tree[u];
int mid = (low + high) / 2;
return get(2 * u, low, mid, l, r) ^ get(2 * u + 1, mid + 1, high, l, r);
}
void init(int root){
for(int i = 0; i < 3 * N; i++)
tree[i] = 0;
for(int i = 1; i < n; i++){
int u, v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for(int i = 0; i <= n; i++){
parent[i] = -1;
chain[i] = i;
}
parent[root] = root;
dfs(root, 0);
buildLCA();
dfs_labels(arr, 1, -1);
}
void dfs(int u, int level){
depth[u] = level;
child[u] = 1;
int bigc = -1, bigv = -1;
for(auto x: g[u]){
if(parent[x] == -1){
parent[x] = u;
dfs(x, level + 1);
child[u] += child[x];
if(child[x] > bigv){
bigc = x;
bigv = child[x];
}
}
}
bigChild[u] = bigc;
}
void buildLCA(){
for(int i = 0; i <= n; i++){
for(int j = 1; j <= trunc(log2(n)); j++)
P[i][j] = -1;
}
for(int i = 1; i <= n; i++)
P[i][0] = parent[i];
for(int j = 1; j <= trunc(log2(n)); j++)
for(int i = 0; i <= n; i++)
if(P[i][j - 1] != -1) P[i][j] = P[P[i][j - 1]][j - 1];
}
int lca(int u, int v){
if(depth[u] < depth[v]) swap(u, v);
int x = 1;
while(x <= log2(depth[u])) x++;
x--;
for(int i = x; i >= 0; i--)
if(depth[u] - (1<<i) >= depth[v]) u = P[u][i];
if(u == v) return u;
for(int i = x; i >= 0; i--)
if(P[u][i] != -1 && P[u][i] != P[v][i])
u = P[u][i], v = P[v][i];
return parent[u];
}
int k_th_ancestor(int u, int k){
if(k == 0) return u;
int cur = u;
for(int i = 17; i >= 0; i--){
if(k >= pow(2, i)){
k -= pow(2, i);
cur = P[cur][i];
}
}
return cur;
}
void dfs_labels(seg_t* a, int u, int v){
label[u] = label_time++;
update(1, 0, n - 1, label[u], a[u]);
if(bigChild[u] != -1) dfs_labels(a, bigChild[u], u);
for(auto x: g[u]){
if(x != v && x != bigChild[u])
dfs_labels(a, x, u);
}
}
void dfs_chains(int u, int v){
if(bigChild[u] != -1) chain[bigChild[u]] = chain[u];
for(auto x: g[u]){
if(x == v) continue;
dfs_chains(x, u);
}
}
seg_t query_chain(int u, int p){
seg_t res = 0;
while(depth[p] < depth[u]){
int top = chain[u];
if(depth[top] <= depth[p]){
int diff = depth[u] - depth[p];
top = k_th_ancestor(u, diff - 1);
}
res = res ^ get(1, 0, n - 1, label[top], label[u]);
u = parent[top];
}
return res;
}
seg_t query(int u, int v){
int anc = lca(u, v);
seg_t res = query_chain(u, anc) ^ query_chain(v, anc);
res ^= get(1, 0, n - 1, label[anc], label[anc]);
return res;
}
};
void Solve(){
int q;
cin>>n>>q;
HLD<int> h;
for(int i = 1; i <= n; i++)
cin>>h.arr[i];
h.init(1);
while(q--){
int t, x, y;
cin>>t>>x>>y;
if(t == 1) h.update(1, 0, n - 1, h.label[x], y);
else cout<<h.query(x, y)<<nl;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
Solve();
}
So, I tried to rewrite the same code without using struct. This time my local computer ran smoothly and the online judge showed AC verdict.
The AC code:
#include<bits/stdc++.h>
using namespace std;
#define nl '\n'
const int N = 1e5 + 5;
int n;
vector<int> g[N];
int arr[N];
int bigChild[N];
int child[N];
int depth[N];
int chain[N];
int label[N], label_time;
int parent[N];
int lca_lift[N][20];
int tree[3 * N];
int k_th_ancestor(int u, int k);
void lca_dfs(int u, int p);
void dfs_size(int u, int p, int level);
void dfs_chains(int u, int p);
void dfs_labels(int u, int p);
void update(int u, int low, int high, int idx, int val){
if(low > idx || high < idx) return;
if(low == high){
tree[u] = val;
return;
}
int mid = (low + high) / 2;
update(2 * u, low, mid, idx, val);
update(2 * u + 1, mid + 1, high, idx, val);
tree[u] = tree[2 * u] ^ tree[2 * u + 1];
}
int get(int u, int low, int high, int l, int r){
if(low > r || high < l) return 0;
if(low >= l && high <= r) return tree[u];
int mid = (low + high) / 2;
return get(2 * u, low, mid, l, r) ^ get(2 * u + 1, mid + 1, high, l, r);
}
void init_arrays(){
for(int i = 0; i < N; i++)
chain[i] = i;
for(int i = 0; i < 3 * N; i++)
tree[i] = 0;
}
void addEdge(int u, int v){
g[u].push_back(v);
g[v].push_back(u);
}
void initTree(int root){
lca_dfs(root, -1);
dfs_size(root, -1, 0);
dfs_chains(root, -1);
label_time = 0;
dfs_labels(root, -1);
}
void lca_dfs(int u, int p){
lca_lift[u][0] = p;
for(int i = 1; i < 20; i++){
if(lca_lift[u][i - 1] == -1) lca_lift[u][i] = -1;
else lca_lift[u][i] = lca_lift[lca_lift[u][i - 1]][i - 1];
}
for(auto x: g[u])
if(x != p) lca_dfs(x, u);
}
void dfs_size(int u, int p, int level){
child[u] = 1;
depth[u] = level;
parent[u] = p;
int bigc = -1, bigv = -1;
for(auto x: g[u]){
if(x == p) continue;
dfs_size(x, u, level + 1);
child[u] += child[x];
if(child[x] > bigv){
bigv = child[x];
bigc = x;
}
}
bigChild[u] = bigc;
}
void dfs_chains(int u, int p){
if(bigChild[u] != -1) chain[bigChild[u]] = chain[u];
for(auto x: g[u]){
if(x == p) continue;
dfs_chains(x, u);
}
}
void dfs_labels(int u, int p){
label[u] = label_time++;
update(1, 0, n - 1, label[u], arr[u]);
if(bigChild[u] != -1) dfs_labels(bigChild[u], u);
for(auto x: g[u]){
if(x == p || x == bigChild[u]) continue;
dfs_labels(x, u);
}
}
int lca(int a, int b){
if(depth[a] < depth[b]) swap(a, b);
int d = depth[a] - depth[b];
int u = k_th_ancestor(a, d);
if(u == b) return u;
for(int i = 19; i >= 0; i--){
if(lca_lift[u][i] != lca_lift[b][i]){
u = lca_lift[u][i];
b = lca_lift[b][i];
}
}
return lca_lift[b][0];
}
int k_th_ancestor(int u, int k){
for(int i = 19; i >= 0; i--){
if(u == -1) return u;
if((1 << i) <= k){
u = lca_lift[u][i];
k -= (1 << i);
}
}
return u;
}
int query_chain(int u, int v){
int res = 0;
while(depth[v] < depth[u]){
int top = chain[u];
if(depth[top] <= depth[v]){
int diff = depth[u] - depth[v];
top = k_th_ancestor(u, diff - 1);
}
res ^= get(1, 0, n - 1, label[top], label[u]);
u = parent[top];
}
return res;
}
int query(int u, int v){
int anc = lca(u, v);
int res = query_chain(u, anc) ^ query_chain(v, anc);
return res ^ get(1, 0, n - 1, label[anc], label[anc]);
}
void Solve(){
int q;
cin>>n>>q;
for(int i = 0; i < n; i++)
cin>>arr[i];
init_arrays();
for(int i = 1; i < n; i++){
int u, v;
cin>>u>>v;
u--; v--;
addEdge(u, v);
}
initTree(0);
while(q--){
int t, x, y;
cin>>t>>x>>y;
if(t == 1) update(1, 0, n - 1, label[x - 1], y);
else cout<<query(x - 1, y - 1)<<nl;
}
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
Solve();
}
Could someone plz explain why's there a difference verdict in my codes? Where did I get it wrong? I much appreciate it!
