USACO Gold 2019 February - Cow Land

Time Complexity: $\mathcal{O}((n+q)\log n)$

Main Idea: We use Euler tour technique to initialize a binary indexed tree, and use the binary indexed tree to run range XOR queries.

Check the official solution for another, more complicated, solution with HLD.

Let $e_x$ be the enjoyment values for each of the attractions, and $lca(i,j)$ be the lowest common ancestor between nodes $i$ and $j$.

Euler Tour Technique

Let $i_x$ and $o_x$ be the in and out times for the tree, which we find through DFS with the Euler tour technique mentioned in this section.

Binary Indexed Tree

We create a binary indexed tree which supports range updates and XOR queries. Note that the inverse of XOR is XOR itself.

Store $e_x$ at indices $i_x$ and $o_x$ for all $x$ in the BIT. Note that the prefix XOR to $i_x$ is now the path XOR from the root node to each node at the tree. See the solution for Path Queries for a comprehensive explanation.

Let the prefix XOR at $i$ be $X(i)$.

The difference between the explanation for Path Queries and this problem is that we have range XOR queries instead of range sum queries.

This precomputation takes $\mathcal{O}(n\log n)$.

Responding to Queries

We now need to respond to path queries and updates. To update node $x$, we remove the current values at $i_x$ and $o_x$ and replace these indices with the new value. For a path query, we just output $X(i)\oplus X(j)\oplus e_{lca(i,j)}$ (where $\oplus$ represents the XOR operation). The $X(i)$ and $X(j)$ are the XOR queries for the paths from $0$ to $i$ and $0$ to $j$, respectively. The path from $0$ to $lca(i,j)$ is counted twice and thus negates itself. Thus, we need to also XOR $e_{lca(i,j)}$ to account for the full path XOR from $i$ to $j$.

LCA precomputation is known to take $\mathcal{O}(n\log n)$ with sparse table. Additionally, updates and queries both take $\mathcal{O}(\log n)$ each, the complexity of the LCA and BIT queries. As there are $q$ updates and queries in total, the total complexity for the querying step is $\mathcal{O}(q\log n)$. Hence, the total complexity is $\mathcal{O}((n+q)\log n)$.

1#include <bits/stdc++.h>
2
3#define MAXN 100005
4#define bitinc(x) (x&-x);
5
6using namespace std;
7
8int n,arr[MAXN],bit[4*MAXN],in[MAXN],ot[MAXN],par[MAXN][22];
9vector<int> adj[MAXN];
10