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]