Home » 國際競賽 » Details

USACO 2020 US Open Contest, Gold Problem 1. Haircut

Category: 國際競賽, 計算機國際競賽 Date: 2022年7月6日下午5:10

USACO 2020 US Open Contest, Gold Problem 1. Haircut

Tired of his stubborn cowlick, Farmer John decides to get a haircut. He has? $N$ ?( $1 \leq N \leq 10^{5}$ ) strands of hair arranged in a line, and strand? $i$ ?is initially? $A_{i}$ ?micrometers long ( $0 \leq A_{i} \leq N$ ). Ideally, he wants his hair to be monotonically increasing in length, so he defines the "badness" of his hair as the number of inversions: pairs? $(i, j)$ ?such that? $i < j$ ?and? $A_{i} > A_{j}$ .

For each of? $j = 0, 1, \dots, N - 1$ , FJ would like to know the badness of his hair if all strands with length greater than? $j$ ?are decreased to length exactly? $j$ .

(Fun fact: the average human head does indeed have about? $10^{5}$ ?hairs!)

INPUT FORMAT (file haircut.in):

The first line contains? $N$ .The second line contains? $A_{1}, A_{2}, \dots, A_{N} .$

OUTPUT FORMAT (file haircut.out):

For each of? $j = 0, 1, \dots, N - 1$ , output the badness of FJ's hair on a new 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:

5
5 2 3 3 0

SAMPLE OUTPUT:

The fourth line of output describes the number of inversions when FJ's hairs are decreased to length 3. Then? $A = [3, 2, 3, 3, 0]$ ?has five inversions:? $A_{1} > A_{2}, A_{1} > A_{5}, A_{2} > A_{5}, A_{3} > A_{5},$ ?and? $A_{4} > A_{5}$ .

SCORING:

Test case 2 satisfies? $N \leq 100.$
Test cases 3-5 satisfy? $N \leq 5000.$
Test cases 6-13 satisfy no additional constraints.

Problem credits: Dhruv Rohatgi

USACO 2020 US Open Contest, Gold Problem 1. Haircut 題解(翰林國際教育提供，僅供參考)

題解請注冊或登錄查看

[/hide]

(Analysis by Benjamin Qi)

For each? $0 \leq j < N$ ?we need to count the number of pairs? $(x, y)$ ?such that? $x < y$ ,? $A [x] > A [y]$ ?and? $A [y] < j$ . It suffices to compute the number of? $x < y$ ?such that? $A [x] > A [y]$ ?for every? $y$ ; call this quantity? $n [y]$ . Then? $a n s [j] = \sum_{A [y] < j} n [y]$ ?can be computed with prefix sums.

The value of? $n [y]$ ?for each? $y$ ?can be found via the following process:

Set? $h = N .$
Maintain a collection of indices, initially empty.
For each? $y$ ?with? $A [y] = h$ , set the corresponding quantity for? $y$ ?equal to the number of indices in the collection less than? $y$ .
For each? $y$ ?with? $A [y] = h$ , insert? $y$ ?into the set.
If? $h = 0,$ ?terminate. Otherwise, decrease? $h$ ?by one and repeat from step 2.

The collection can be a?policy-based data structure?in C++ or a binary indexed tree.

My code:

#include "bits/stdc++.h"
 
using namespace std;
 
void setIO(string s) {
	ios_base::sync_with_stdio(0); cin.tie(0); 
	freopen((s+".in").c_str(),"r",stdin);
	freopen((s+".out").c_str(),"w",stdout);
}

#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <class T> using Tree = tree<T, null_type, less<T>, 
	rb_tree_tag, tree_order_statistics_node_update>; 
 
const int MX = 1e5+5;

int N;
long long numInv[MX];
vector<int> todo[MX];
 
int main() {
	setIO("haircut");
	int N; cin >> N;
	vector<int> A(N); for (int& t: A) cin >> t;
	for (int i = 0; i < N; ++i) todo[A[i]].push_back(i);
	Tree<int> T;
	for (int i = N; i >= 0; --i) {
		for (int t: todo[i]) numInv[i+1] += T.order_of_key(t);
		for (int t: todo[i]) T.insert(t);
	}
	for (int i = 1; i < N; ++i) numInv[i] += numInv[i-1];
	for (int i = 0; i < N; ++i) cout << numInv[i] << "\n";
}

Dhruv Rohatgi's code:

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100005
 
int N;
int A[100000];
int T[MAXN+1];
 
int getSum(int i)
{
	int c=0;
	for(++i; i > 0 ; i -= (i & -i))
		c += T[i];
	return c;
}
void set(int i,int dif)
{
	for(++i; i < MAXN ; i += (i & -i))
		T[i] += dif;
}
 
long long cnt[100000];
 
int main()
{
	freopen("haircut.in","r",stdin);
	freopen("haircut.out","w",stdout);
	cin >> N;
	int a;
	for(int i=0;i<N;i++)
	{
		cin >> a;
		a++;
		cnt[a] += i - getSum(a);
		set(a, 1);
	}
	long long ans = 0;
	for(int j=1;j<=N;j++)
	{
		cout << ans << '\n';
		ans += cnt[j];
	}
}

[/hide]