P6278 [USACO20OPEN]Haircut G

[USACO20OPEN]Haircut G - 洛谷

核心算法：树状数组

难度：普及+/提高

前置知识：逆序对

逆序对 - 洛谷

首先我们可以很快求出在不进行任何操作的情况下头发的不良度。（逆序对）

然后我们考虑下面这个问题：

所有长度大于 k 的头发的长度均减少到 k 时，对于一根头发 j 而言，哪些头发 i （i

当 k <= a[ j ] < a[ i ] 时，a [ i ] 的值变成 k 会对答案产生影响。

因此我们可以用 s[ i ] 表示长度为 i 的头发前面长度< i 的头发数量。

每次k--，ans -= s[ k ];//答题思路就是计算每次减少多少对逆序对，其实也就是前缀和。

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define N 100010
int n,a[N],c[N];
long long s[N];

int read ()
{
	int x=0,k=1;char ch=getchar ();
	while (!isdigit (ch)) {if (ch=='-') k=-1;ch=getchar ();}
	while (isdigit (ch)) {x=x*10+ch-'0';ch=getchar ();}
	return x*k;
}

void Init ()
{
	n=read ();
	for (int i=1;i<=n;i++)
		a[i]=read ();
}

void update (int x)
{
	for (int i=x;i<=n;i+=i&(-i))
		c[i]++;
}

int getsum (int x)
{
	int ans=0;
	for (int i=x;i;i-=i&(-i))
		ans+=c[i];
	return ans;
}

void Work ()
{
	for (int i=1;i<=n;i++)
	{
		update (a[i]+1);
		s[a[i]+1]+=i-getsum (a[i]+1);
	}
	for (int i=1;i<=n;i++)
		s[i]+=s[i-1];
	for (int i=0;i