自动搬运

查看原文

来自洛谷，原作者为

	Frozencode 消失在你的世界里，是我最后最深的惦记.

搬运于2025-08-24 22:11:01，当前版本为作者最后更新于2019-07-14 19:04:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

考虑一组逆序对$(a[i],a[j])$贡献了几次,不难发现贡献了$i*(n - j + 1)$次。

考虑怎么统计，通常求逆序对我们是让树状数组上的值$+1$，现在我们实际上只要把$+1$改成$+(n - j + 1)$就行了（想想乘法分配律就知道这是对的）。

那么接下来就是常规的离散化加树状数组辣~

（答案会爆$longlong$,我偷懒写了个$int128$就欧克了QWQ)

#include<bits/stdc++.h>
using namespace std;
typedef __int128 ll;
const ll maxn=1000010;
const ll INF=2147483647;
ll n,a[maxn],b[maxn],c[maxn],tot,res,f[maxn];
inline ll read()
{
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-')f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9')
	{
		x=(x<<3)+(x<<1)+ch-'0';
		ch=getchar();
	}
	return x*f;
}
inline void write(ll x)
{
	if(x<0)
	{
		putchar('-');
		x=-x;
	}
	if(x>9)
	{
		write(x/10);
	}
	putchar(x%10+'0');
}
ll lowbit(ll x)
{
	return x & (-x);
}
void update(ll x,ll det)
{
	while(x <= n)
	{
		f[x] += det;
		x += lowbit(x);
	}
	return;
}
ll qry(ll x)
{
	ll tem = 0;
	x--;
	while(x)
	{
		tem += f[x];
		x -= lowbit(x);
	}
	return tem;
}
int main()
{
	n = read();
	for(int i = 1;i <= n;i++)
	{
		a[i] = read();
		b[i] = a[i];
	}
	sort(b + 1,b + n + 1);
	tot = unique(b + 1,b + n + 1) - b - 1;
	for(int i = 1;i <= n;i++)
	{
		c[i] = lower_bound(b + 1,b + tot + 1,a[i]) - b;
	}
	for(int i = n;i >= 1;i--)
	{
		ll item = i;
		ll idet = n - i + 1;
		res += (ll)(item * qry(c[i]));
		update(c[i],idet);
	}
	write(res);
	return 0;
}