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)$.

Copy
#include <bits/stdc++.h>

#define MAXN 100005
#define bitinc(x) (x & -x);

using namespace std;

int n, arr[MAXN], bit[4 * MAXN], in[MAXN], ot[MAXN], par[MAXN][22];
vector<int> adj[MAXN];

Copy
import java.io.*;
import java.util.*;

// this one uses a segment tree for the xor-ing instead of a BIT, but overall
// it's the same philosophy
public class CowLand {
	private static class MinSegTree {
		private final int[] segtree;
		private final int arrSize;
		private final int size;