CSES - Distinct Colors

Author: Timothy Gao

Solution 1 - Small to Large Merging

See here.

Solution 2 - PURS

Let us consider the Euler Tour of the tree. We flatten the tree into an array, where each node corresponds to a range in this array. Now, we are essentially tasked to find the number of distinct values in a range NN times (once for each node).

Let us consider iterating through the Euler Tour array from left to right. When we consider a node at index ii in the Euler Tour array, its subtree range will be [j,i][j, i], where jij\leq i. Now, let's focus on a single color. Notice that if there are multiple colors cc to the left of a certain index ii, only cc's most rightmost occurrence is relevant. We only want to count cc once so we choose to only count the most rightmost occurence. This is because any non-rightmost occurrence of cc from ii must include the rightmost occurrence of cc. More formally, any segment [l,r][l, r] must contains ii if l<=i<=rl <= i <= r.

With this observation, we can essentially reduce the distinct colors queries to a simple range query. As we iterate through the Euler Tour from left to right, mark the current index (in the BIT) as 11, and if the color of the node at the current index has occurred before, make it 00 in the BIT. We can find the solution to every node by doing a sum query as we iterate.

Time Complexity: O(NlogN)\mathcal O(N\log N)

C++

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
struct BIT {
vector<int> bit;
int n;
BIT(int n) : n(n + 1), bit(n + 1) { }
int sum(int r) {

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!