小朋友排队——树状数组

设第k个小朋友应该移动n次，则n=(1-k)个小朋友中身高大于k的人数+((k+1)-n)个小朋友中身高小于k的人数

满足前大后小原则

例如

3

3 2 1

0 1 2（前大）

2 1 0（后小）

故总移动次数为

2 2 2

因此不搞笑值=3+3+3=9

所以问题转化为求解每一位数的前k个身高大于k的人数+后(k+1-n)个身高小于k的人数和

题干中1< =n< =100000，0< =Hi< =1000000。

因此使用暴力破解法一定超时

h故考虑使用树状数组

设tree为一个树状数组

k的值为每个数字出现的次数

对于

3 2 1而言

由于存在身高=0的情况，而树状数组不包括0

因此对每一位数加一

得

4 3 2

对于第一位数4

tree的前4项和为1

因此b[1]=i-1;

(b为每一位数的移动次数）

(i为当前输入的个数）

对于第二位数3

tree前3项和为1

因此b[2]=i-1=2-1=1

对于第三项1

tree前1项和为1

因此b[3]=i-1=2

故得到前大的解为

0 1 2

对于后小只需要将3 2 1反向输入

重新得到一个tree

用同样的方法就可以得到

2 2 2

最后求解每一位数对应的不搞笑度

3 3 3

(切记，中间值temp也必须是long long，因为存在某一位数过大导致temp溢出)

#include<iostream>
#include<cstring>
#define lowbit(x) x&(-x)
using namespace std;
long long  a[1000001];
long long  b[1000001];
long long  c[1000001];
long long  tree[1000001];
long long  s;
long long  temp;
long long  n;
int sum(int num)
{
	int ans = 0;
	while (num)
	{
		ans += tree[num];
		num -= lowbit(num);
	}
	return ans;
}
void insert(int num,int insert_num)
{
	while (num < 1000001)
	{
		tree[num] += insert_num;
		num += lowbit(num);
	}
}
int main()
{
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		cin >> c[i];
		c[i] += 1;
		a[c[i]]++;
		insert(c[i], 1);
		b[i] += i - sum(c[i]);
	}
	memset(tree, 0, sizeof(tree));
	memset(a, 0, sizeof(a));
	for (int i = n; i > 0; i--)
	{
		a[c[i]]++;
		insert(c[i], 1);
		b[i] += sum(c[i]) - a[c[i]];
	}

	for (int i = 1; i <= n; i++)
	{
		temp = (b[i] + 1) * b[i] / 2;
		s += temp;
	}
	cout << s;
	return 0;
}