CF#609E|二分+树状数组

CF#609E 题目地址
复习树状数组求逆序数1
复习树状数组求逆序数2
参考博客1
参考博客2

题目大意：每次可以移动相邻的结点，求最小能够出现1~k子序列的交换次数

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn = 2e5+5;
ll sum1[maxn];
ll sum2[maxn];
ll a[maxn];
ll pos[maxn];
int n;


//树状数组模板
ll lowbit(ll x){
    return x & -x;
}
void add(ll *sum,ll x,ll v){
    while(x <= n){
        sum[x] += v;
        x += lowbit(x);
    }
}
ll query(ll *sum,ll x){
    ll res = 0;
    while(x > 0){
        res += sum[x];
        x -= lowbit(x);
    }
    return res;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        pos[a[i]] = i;//值为a[i]的元素 "位置"在为i的地方
    }
    ll ans1 = 0;
    for(int i=1;i<=n;i++){
        ans1 += i - 1 - query(sum1,pos[i]); //求逆序数 和相加
        add(sum1,pos[i],1); //前i个位置中已经出现了的比当前数要小的数的个数+1
        add(sum2,pos[i],pos[i]); //比第i个位置小的 位置+pos[i]
        int mid,l = 1,r = n;
        while(l<=r){ //二分需要靠拢的最中间的位置
            mid = (l+r)>>1;
            if(query(sum1,mid)*2 <= i) l = mid+1;
            else r = mid - 1;
        }
        //将mid左边的数靠拢到mid附近的花费
        //cnt:mid左边部分的个数 sum1(mid):维护的是前mid个元素的比mid小的元素个数(比mid小才需要移动)
        //sum:mid前的位置和  sum2(mid)维护的是第mid个元素前的所有元素的位置和
        ll ans2 = 0;
        ll cnt = query(sum1,mid);
        ll sum = query(sum2,mid);
        ans2 += mid*cnt-sum-cnt*(cnt-1)/2;
        //将mid右边的数靠拢到mid附近的花费
        //cnt是每个mid右边的个数 sum = 总的所有元素位置和 - mid前位置和 = 右边元素位置和
        cnt = i-cnt;
        sum = query(sum2,n) - sum;
        ans2 += sum-cnt*(mid+1)-cnt*(cnt-1)/2;
        cout<<ans1+ans2<<" ";
    }
    return 0;
}