Codeforces Round #609 (Div. 2) E. K Integers

K Integers
题意：给n个数的一个全排列，每次交换相邻两个数
求使 数字1-k相邻且递增的最小步骤，k（1，n）；
思路：
当1-k已经相邻时，ans即为1-k的逆序数。
那么只需逐步算出使1-k这些数相邻所需的最小步骤
容易看出 使这k个数 向中间靠拢时花费步数最小
并容易推出如下公式

本题难点在于如何计算向中间靠拢时的步数 自己一直在考虑怎样正向算出答案， 并且没有想到利用优先队列来维护这个步数，而是推出来另一个看似可解的办法导致浪费很多时间，最后也没有完成

逆向思维 容斥 两个优先队列维护左右边

#include<bits/stdc++.h>
using namespace std;
typedef long long L;
const int maxn=2e5+5;
const int oo=1e9+7;
int a[maxn],c[maxn],n;
int pos[maxn];
L ans[maxn];
void update(int x){for(int i=x;i<=n&&i;i+=i&(-i)) c[i]++;}
L    query (int x){L ans=0;while(x)ans=ans+1ll*c[x],x-=x&(-x);return ans;}
priority_queue<int>q1,q2;

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]),pos[a[i]]=i;
    //ans[1]=0;ans[2]=abs(pos[2]-pos[1])-1+(pos[2]>pos[1]?0:1);
    //update(pos[1]);update(pos[2]);

    L a1=0,ln=0,rn=0;
    for(L i=1;i<=n;i++){
        update(pos[i]);
        a1=a1+i-query(pos[i]);

        if(q1.size()&&pos[i]<q1.top()){
            ln+=pos[i];q1.push(pos[i]);
        } else {
            rn+=pos[i];q2.push(-pos[i]);
        }

        while(q1.size()<q2.size()){
            L c=-q2.top();

            ln+=c;rn-=c;

            q2.pop();q1.push(c);
        }

        while(q1.size()>q2.size()+1){

            L c=q1.top();
            ln-=c;rn+=c;

            q1.pop();q2.push(-c);
        }

        L top=q1.top();
        ans[i]=a1+1ll*top*q1.size()-ln-1ll*q1.size()*(q1.size()-1)/2
                 +rn-top*q2.size()-1ll*q2.size()*(q2.size()+1)/2;
        ;
    }
    for(int i=1;i<=n;i++){
        if(i!=1) printf(" ");
        printf("%lld",ans[i]);
    }
}
/* 10 5 1 6 2 8 3 4 10 9 7 */