Official Analysis (C++, Java)

Explanation

Let's fix the left endpoint $l$ and compute how many right endpoints $r$ work for that $l$. First, consider the first position $x>l$ such that $b_x=b_l$. If this doesn't exist, let $x = N + 1$. We can't select any right endpoint $r \ge x$, because this results in the left endpoint leader having the same breed as the cow in position $x$. We can find this position $x$ by either binary searching the index map of $b$ or precomputation.

The right endpoint leader can be handled similarly. For all breeds in the range $(l, x)$, we can only select the first position of that breed $>l$. Thus, the number of right endpoints that work for this $l$ are the number of distinct elements in $(l, x)$. This can be found using a data structure like a BIT (Binary Indexed Tree).

We sweep from left to right, and maintain the BIT accordingly by inserting breeds as we go. This ensures we don't overcount delegations, and allows us to efficiently query the number of valid right endpoints for each fixed $l$.

Implementation

Time Complexity: $\mathcal{O}(N\log N)$

Copy
#include <bits/stdc++.h>
using namespace std;

 Code Snippet: BIT (Click to expand)

int main() {
	int n;
	cin >> n;

	vector<int> breed(n);