Home » 国际竞赛 » Details

USACO 2021 US Open, Platinum Problem 1. United Cows of Farmer John Return to Problem List

Category: 国际竞赛, 计算机国际竞赛 Date: 2022年7月4日下午6:13

USACO 2021 US Open, Platinum Problem 1. United Cows of Farmer John Return to Problem List

The United Cows of Farmer John (UCFJ) are sending a delegation to the International bOvine olympIad (IOI).

There are $N$ cows participating in delegation selection ( $1 \leq N \leq 2 \cdot 10^{5}$ ). They are standing in a line, and cow $i$ has breed $b_{i}$ .

The delegation will consist of a contiguous interval of at least three cows - that is, cows $l \dots r$ for integers $l$ and $r$ satisfying $1 \leq l < r \leq N$ and $r - l \geq 2$ . Three of the cows in the chosen interval are marked as delegation leaders. For legal reasons, the two outermost cows of the chosen interval must be leaders. Moreover, to avoid intra-breed conflict, every leader must be of a different breed from the rest of the delegation (leaders or not).

Help the UCFJ determine (for tax reasons) the number of ways they might choose a delegation to send to the IOI. Two delegations are considered different if they have different members or different leaders.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $N$ .The second line contains $N$ integers $b_{1}, b_{2}, \dots, b_{N}$ , each in the range $[1, N]$ .

OUTPUT FORMAT (print output to the terminal / stdout):

The number of possible delegations, on a single line.Note that the large size of integers involved in this problem may require the use of 64-bit integer data types (e.g., a "long long" in C/C++).

SAMPLE INPUT:

7
1 2 3 4 3 2 5

SAMPLE OUTPUT:

Each delegation corresponds to one of the following triples of leaders:

(1, 2, 3), (1, 2, 4), (1, 3, 4), (1, 4, 7), (2, 3, 4), (4, 5, 6), (4, 5, 7), (4, 6, 7), (5, 6, 7) .

SCORING:

Test cases 1-2 satisfy $N \leq 50$ .
Test cases 3-4 satisfy $N \leq 500$ .
Test cases 5-8 satisfy $N \leq 5000$ .
Test cases 9-20 satisfy no additional constraints.

Problem credits: Benjamin Qi

USACO 2021 US Open, Platinum Problem 1. United Cows of Farmer John Return to Problem List 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Benjamin Qi)

Note: I index the cows as $0 \dots N - 1$ rather than $1 \dots N$ .

To solve this problem in $O (N^{2})$ time, fix $r$ and iterate over all possible $l$ in decreasing order. Let ${unique}_{l, r}$ equal the number of cows in the interval $l \dots r$ whose breeds are unique within that interval. When we decrease $l$ by one,

If $B_{l} = B_{r}$ , then cow $r$ cannot be a leader in $l \dots r$ . Break.
If $B_{l}$ is unique in the range $l \dots r$ , then add ${unique}_{l + 1, r - 1}$ to the answer and set ${unique}_{l, r - 1} = {unique}_{l + 1, r - 1} + 1$ .
If $B_{l}$ occurs exactly once in the range $l + 1 \dots r$ , then $B_{l}$ was unique in $l + 1 \dots r$ but not $l \dots r$ . Set ${unique}_{l, r - 1} = {unique}_{l + 1, r - 1} - 1$ .

#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 ${active}_{r} [l]$ , ${unique}_{r} [l]$ , ${val}_{r} [l]$ for each $r$ from $0 \dots N - 1$ . For each $l \leq r$ , define

${active}_{r} [l] = 1$ if $B_{l}$ is unique among $B_{l}, B_{l + 1}, \dots, B_{r}$ , and $0$ otherwise.
${unique}_{r} [l] = {unique}_{l + 1, r - 1}$ .
${val}_{r} [l] = {active}_{r} [l] \cdot {unique}_{l + 1, r - 1}$ .

For every $r$ , we add a suffix of ${val}_{r}$ to the answer.

To solve this problem in $O (N \log N)$ time, we must be able to efficiently transition from $r - 1$ to $r$ . Define $prev_oc [j]$ to equal the maximum index $i < j$ such that $B_{i} = B_{j}$ . ${active}_{r}$ and ${unique}_{r}$ are the same as ${active}_{r - 1}$ and ${unique}_{r - 1}$ respectively except for the following changes:

${active}_{r} [r] = 1$ .
${active}_{r} [prev_oc [r]] = 0$ .
${unique}_{r} [prev_oc [r] \dots r - 1]$ must be incremented by $1$ .
${unique}_{r} [prev_oc [prev_oc [r]] \dots prev_oc [r] - 1]$ must be decremented by $1$ .

These updates and range sum queries over ${val}_{r}$ can be supported in $O (\log N)$ time each using a segment tree with lazy propagation. At each segment $x \dots y$ of the tree, maintain $\sum_{i = x}^{y} {active}_{r} [i]$ , $\sum_{i = x}^{y} {val}_{r} [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);
        }
    }
}

[/hide]