P6278 [USACO20OPEN] Haircut G

题目描述

Farmer John 由于对整理他难以整平的头发感到疲惫，于是决定去理发。他有一排 $N$ 缕头发，第 $i$ 缕头发初始时长度为 $A_i$ 微米（$0\le A_i\le N$）。理想情况下，他想要他的头发在长度上单调不降，所以他定义他的头发的“不良度”为逆序对的数量：满足 $i<j$ 及 $A_i>A_j$ 的二元对 $(i,j)$。
对于每一个 $j=0,1,\dots ,N-1$，Farmer John 想要知道他所有长度大于 $j$ 的头发的长度均减少到 $j$ 时他的头发的不良度。

（有趣的事实：人类平均确实有大约 $10^5$ 根头发！）

输入格式

输入的第一行包含 $N$。
第二行包含 $A_1,A_2,\dots ,A_N$。

输出格式

对于每一个 $j=0,1,\dots ,N-1$，用一行输出 Farmer John 头发的不良度。

注意这个问题涉及到的整数大小可能需要使用 $64$ 位整数型存储（例如，C/C++ 中的“long long”）。

输入输出样例 #1

输入 #1

5
5 2 3 3 0

输出 #1

0
4
4
5
7

说明/提示

样例解释：

输出的第四行描述了 Farmer John 的头发长度减少到 $3$ 时的逆序对数量。
$A=[3,2,3,3,0]$ 有五个逆序对：$A_1>A_2,A_1>A_5,A_2>A_5,A_3>A_5,$ 和 $A_4>A_5$。

对于 $100\%$ 的数据，$1\le N\le 10^5$。

共 $13$ 个测试点，其中 $1$ 为样例，其余性质如下：

测试点 $2$ 满足 $N\le 100$。
测试点 $3\sim 5$ 满足 $N\le 5000$。
测试点 $6\sim 13$ 没有额外限制。

出题人：Dhruv Rohatgi

C++实现

#include<bits/stdc++.h>
#define MAXN 100100
#define int long long//别忘记longlong哦
using namespace std;
int n,a[MAXN];
class tarray
{
private:
	int tree[MAXN];
	int lowbit(int x){return x&(-x);}
public:
	void update(int x,int y){while(x<=n){tree[x]+=y;x+=lowbit(x);}}
	int query(int x){int ret=0;while(x){ret+=tree[x];x-=lowbit(x);}return ret;}
}t;//树状数组
int s[MAXN],ans;
signed main()
{
	scanf("%lld",&n);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]),a[i]++;
	for(int i=1;i<=n;i++)//统计逆序对
	{
		int x=n-a[i]+2;
		s[a[i]]+=t.query(x-1);
		t.update(x,1);
	}
	printf("0");//第0秒的答案
	for(int i=2;i<=n;i++)//统计答案
	{
		ans+=s[i-1];
		printf("\n%lld",ans);
	}
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容