Codeforces609 Div2 E. K Integers(思维+数据结构)

分析：这题据说老掉牙了，但是对我来说还是挺新的，毕竟刷题少。题目可以拆成两部分。

第一部分，把1 ~ K 的数聚集在一起。

将原数组中1 ~ K 的数中位置在最中间的数称作中间数位置为pos，肯定是把其他 K - 1 个数向中间数靠拢最划算。令原来这 K 个数的位置为 $p\left[ 1 \right]$ $\sim$ $p\left[ k \right]$ ，移动之后位置为 $t\left[ 1 \right]\sim$ $t\left[ k \right]$ ，那么在这一部分对答案的贡献 $sum=\sum_{}^{}{\left| t[i]-p[i] \right|}=\sum_{t[i]>p[i]}^{}{(t[i] - p[i])} + \sum_{p[i]>t[i]}^{}{(p[i]-t[i])}$ 拆开算 $sum=\sum_{t[i]>p[i]}^{}{t[i]}-\sum_{t[i]<p[i]}^{}{t[i]}+\sum_{t[i]<p[i]}^{}{p[i]}-\sum_{t[i]>p[i]}^{}{p[i]}$ 对于 t 的这一部分可以直接是连续的一段数，等差数列算一下。对于 p 的部分

用树状数组计算。对 pos ，需要二分得到

第二部分，经典的逆序对数数，cnt 的计算挺有意思的，之前想的很麻烦，这样累加不管是思维还是代码都方便很多。

code :

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e5 + 5;
ll b[maxn],c[maxn],p[maxn],n;
ll lowbit(ll x){return x&-x;}
void update(ll *num,ll x,ll y)
{
	while(x<=n)
	{
		num[x]+=y; x+=lowbit(x);
	}
}
ll query(ll *num,ll x)
{
	ll sum=0;
	while(x)
	{
		sum+=num[x]; x-=lowbit(x);
	}
	return sum;
}
int main()
{
	ll x;
	scanf("%lld",&n);
	for(ll i=1;i<=n;i++) {
		scanf("%lld",&x);
		p[x]=i;
	}
	ll cnt=0; // 当前逆序对，是个累积的变量
	for(ll i=1;i<=n;i++) {
		ll sum=0;
		update(b,p[i],1);
		update(c,p[i],p[i]);
		cnt+=i-query(b,p[i]);
		if(i==1) {
			printf("0 "); continue;
		}
		ll l=1,r=n,pos;
		while(l<=r) 
		{
			ll mid=(l+r)>>1;
			if(query(b,mid)*2<=i) { pos=mid,l=mid+1; }
			else r=mid-1;
		}
		ll cntL,cntR,idsumL,idsumR;
		cntL=query(b,pos);//包含pos位置
		cntR=i-cntL;
		idsumL=query(c,pos);
		idsumR=query(c,n)-idsumL;
		sum+=(pos+pos-cntL+1)*cntL/2-(pos+1+pos+cntR)*cntR/2;
		sum+=idsumR-idsumL;
		printf("%lld ",sum+cnt);
	}
	return 0;
}