[luogu] P1774 最接近神的人 树状数组求逆序对

前言

树状数组有点难理解hh 传送门 :

思路

一开始就想到是逆序对 (为什么呢?习惯吧)

但是如何求逆序对呢 ?

朴素做法 :

冒泡排序,对于每次插入的一个数,我们都向前遍历所有循环 但是 O n 2 O n^2 On2显然

所有我们能否通过某个数据结构优化呢 ?

我们发现 如果对原有下标 通过数值排序 , 出现在他前面的数且比他大的数的个数 就是逆序对的个数

因此不难发现我们可以使用树状数组 进行维护,前缀和 和 区间维护数的个数

CODE

int n,m,t;
int tr[N],a[N],b[N];

ll ans;
bool cmp(int x,int y)
{
	return a[x]n;
	for(int i=1;i>a[i];
		b[i] = i;
	}
	stable_sort(b+1,b+n+1,cmp);
	for(int i=1;i=1;i--)
	{
		ans+=ask(a[i]-1);
		add(a[i]);
	}
	cout