(Analysis by Benjamin Qi)

Note: I index the cows as 0N1 rather than 1N.

To solve this problem in O(N2) time, fix r and iterate over all possible l in decreasing order. Let uniquel,r equal the number of cows in the interval lr whose breeds are unique within that interval. When we decrease l by one,

#include<bits/stdc++.h>
using namespace std;
 
int main() {
	int N; cin >> N;
	vector<int> B(N); for (int& b: B) cin >> b;
	int64_t ans = 0;
	for (int r = 0; r < N; ++r) {
		vector<int> occ(N+1);
		int unique = 0;
		for (int l = r-1; l >= 0; --l) {
			if (B[l] == B[r]) break;
			int& o = occ[B[l]]; ++o;
			if (o == 1) {
				ans += unique;
				++unique;
			} else if (o == 2) {
				--unique;
			}
		}
	}
	cout << ans << "\n";
}

Essentially, we're computing arrays activer[l], uniquer[l], valr[l] for each r from 0N1. For each lr, define

For every r, we add a suffix of valr to the answer.

To solve this problem in O(NlogN) time, we must be able to efficiently transition from r1 to r. Define prev_oc[j] to equal the maximum index i<j such that Bi=Bj. activer and uniquer are the same as activer1 and uniquer1 respectively except for the following changes:

These updates and range sum queries over valr can be supported in O(logN) time each using a segment tree with lazy propagation. At each segment xy of the tree, maintain i=xyactiver[i], i=xyvalr[i], and a lazy value that the values of all active indices in the segment should be increased by. You can check the analysis for Counting Haybales for an introduction to lazy segment trees.

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

using T = uint64_t;
const int SZ = 1<<18;

struct LazySeg {
	T sum[2*SZ], lazy[2*SZ], num_active[2*SZ];
	LazySeg() {
		for (int i = 0; i < SZ; ++i) 
			num_active[SZ+i] = 1;
		for (int i = SZ-1; i > 0; --i) 
			num_active[i] = num_active[2*i]+num_active[2*i+1];
	}
	void push(int ind, int L, int R) {
		sum[ind] += num_active[ind]*lazy[ind];
		if (L != R) for (int i = 0; i < 2; ++i) 
			lazy[2*ind+i] += lazy[ind];
		lazy[ind] = 0;
	}
	void pull(int ind) {
		sum[ind] = sum[2*ind]+sum[2*ind+1];
		num_active[ind] = num_active[2*ind]+num_active[2*ind+1];
	}
	void increment(int lo,int hi, int val, int ind=1,int L=0, int R=SZ-1) {
		push(ind,L,R); if (hi < L || R < lo) return;
		if (lo <= L && R <= hi) { 
			lazy[ind] = val; push(ind,L,R); return; }
		int M = (L+R)/2; 
		increment(lo,hi,val,2*ind,L,M); 
		increment(lo,hi,val,2*ind+1,M+1,R); 
		pull(ind);
	}
	T query(int lo, int hi, int ind=1, int L=0, int R=SZ-1) {
		push(ind,L,R); 
		if (lo > R || L > hi) return 0;
		if (lo <= L && R <= hi) return sum[ind];
		int M = (L+R)/2;
		return query(lo,hi,2*ind,L,M)+query(lo,hi,2*ind+1,M+1,R);
	}
	void deactivate(int pos, int ind=1, int L=0, int R=SZ-1) {
		push(ind,L,R); 
		if (pos > R || L > pos) return;
		if (pos <= L && R <= pos) {
			assert(num_active[ind] == 1);
			sum[ind] = num_active[ind] = 0;
			return;
		}
		int M = (L+R)/2; 
		deactivate(pos,2*ind,L,M);
		deactivate(pos,2*ind+1,M+1,R);
		pull(ind);
	}
} Seg;

int main() {
	cin.tie(0)->sync_with_stdio(0);
	int N; cin >> N;
	vector<int> B(N); for (int& b: B) cin >> b;
	vector<int> last(N+1,-1), prev_oc(N);
	int64_t ans = 0;
	for (int r = 0; r < N; ++r) {
		int& last_oc = last[B[r]];
		ans += Seg.query(last_oc+1,SZ-1);
		if (last_oc != -1) {
			Seg.deactivate(last_oc);
			Seg.increment(prev_oc[last_oc],last_oc-1,-1);
		}
		Seg.increment(last_oc,r-1,1);
		prev_oc[r] = last_oc; last_oc = r;
	}
	cout << ans << "\n";
}

Danny Mittal's code:

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class TriplesOfCows {
 
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        StringTokenizer tokenizer = new StringTokenizer(in.readLine());
        int[] last2 = new int[n + 1];
        int[] last = new int[n + 1];
        long answer = 0;
        SegmentTree segTree = new SegmentTree(n);
        for (int j = 1; j <= n; j++) {
            int k = Integer.parseInt(tokenizer.nextToken());
            segTree.updateSingle(last[k], -1);
            segTree.updateRange(last2[k] + 1, last[k] - 1, -1);
            answer += segTree.query(last[k] + 1, j - 1);
            segTree.updateRange(last[k] + 1, j - 1, 1);
            segTree.updateSingle(j, 1);
            last2[k] = last[k];
            last[k] = j;
        }
        System.out.println(answer);
    }
 
    static class SegmentTree {
        final int n;
        final long[] value = new long[530000];
        final long[] singles = new long[530000];
        final long[] lazy = new long[530000];
 
        SegmentTree(int n) {
            this.n = n;
        }
 
        void propagate(int node) {
            value[2 * node] += lazy[node] * singles[2 * node];
            value[(2 * node) + 1] += lazy[node] * singles[(2 * node) + 1];
            lazy[2 * node] += lazy[node];
            lazy[(2 * node) + 1] += lazy[node];
            lazy[node] = 0;
        }
 
        void updateSingle(int index, long delta, int node, int segFrom, int segTo) {
            if (segFrom == segTo) {
                value[node] += delta * lazy[node];
                singles[node] += delta;
            } else {
                propagate(node);
                int mid = (segFrom + segTo) / 2;
                if (index <= mid) {
                    updateSingle(index, delta, 2 * node, segFrom, mid);
                } else {
                    updateSingle(index, delta, (2 * node) + 1, mid + 1, segTo);
                }
                value[node] = value[2 * node] + value[(2 * node) + 1];
                singles[node] = singles[2 * node] + singles[(2 * node) + 1];
            }
        }
 
        void updateSingle(int index, long delta) {
            if (index > 0) {
                updateSingle(index, delta, 1, 1, n);
            }
        }
 
        void updateRange(int from, int to, long delta, int node, int segFrom, int segTo) {
            if (segTo < from || to < segFrom) {
 
            } else if (from <= segFrom && segTo <= to) {
                value[node] += delta * singles[node];
                lazy[node] += delta;
            } else {
                propagate(node);
                int mid = (segFrom + segTo) / 2;
                updateRange(from, to, delta, 2 * node, segFrom, mid);
                updateRange(from, to, delta, (2 * node) + 1, mid + 1, segTo);
                value[node] = value[2 * node] + value[(2 * node) + 1];
                singles[node] = singles[2 * node] + singles[(2 * node) + 1];
            }
        }
 
        void updateRange(int from, int to, long delta) {
            updateRange(from, to, delta, 1, 1, n);
        }
 
        long query(int from, int to, int node, int segFrom, int segTo) {
            if (segTo < from || to < segFrom) {
                return 0;
            } else if (from <= segFrom && segTo <= to) {
                return value[node];
            } else {
                propagate(node);
                int mid = (segFrom + segTo) / 2;
                return query(from, to, 2 * node, segFrom, mid) + query(from, to, (2 * node) + 1, mid + 1, segTo);
            }
        }
 
        long query(int from, int to) {
            return query(from, to, 1, 1, n);
        }
    }
}