历届试题 小朋友排队

显然每个人的最少次数是左边大于他的人数和右边小于他的人数，两次树状数组扫一下就ok了，由于H=1e6，所以先离散化一下，再套树状数组。

Code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll calc(int k)
{
	return 1LL * k * (k + 1) / 2;
}
int a[100005], c[100005], cnt[100005], t[100005];
int lowbit(int k)
{
	return k & -k;
}
void update(int k, int x)
{
	while (k < 100005)
	{
		c[k] += x;
		k += lowbit(k);
	}
}
int query(int k)
{
	int ans = 0;
	while (k)
	{
		ans += c[k];
		k -= lowbit(k);
	}
	return ans;
}
int main()
{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		scanf("%d", &a[i]);
		t[i] = a[i];
	}
	sort(t, t + n);
	int num = unique(t, t + n) - t;
	for (int i = 0; i < n; i++)
		a[i] = lower_bound(t, t + num, a[i]) - t + 1;
	for (int i = 0; i < n; i++)
	{
		cnt[i] += i - query(a[i]);
		update(a[i], 1);
	}
	memset(c, 0, sizeof c);
	for (int i = n - 1; i >= 0; i--)
	{
		update(a[i], 1);
		cnt[i] += query(a[i] - 1);
	}
	ll ans = 0;
	for (int i = 0; i < n; i++)
		ans += calc(cnt[i]);
	printf("%lld", ans);
}