贪心+平衡树

题意：给你一个长度为n/2，并且是2,4,6,8,…n的排列，让你再往其中插入1,3,5,7,9…n-1共n/2个数，使最后长度为n的序列逆序数最小。考虑从小到大依次将奇数插入到序列中，可以贪心的想，如果每次都插入到与其他数字组成逆序数最小的位置，那么最后总逆序数最小。可以建立一颗平衡二叉树，并在其中插入两种节点，一种用来表示当前序列中的数字，权值赋为inf，另一种为决策点，权值为把当前数字插入到这个位置与其他数字构成的逆序数。维护最小值和产生最小值的节点编号。
比如案例中的2,6,4。建好树以后如下图

那么此时将1插入在最左边的决策点所在的位置，并且这将会引入新的两个决策点。权值与插入位置原来的权值相同。

接下来继续插入的时候，需要插入的数字由1变为了3，所以1的左侧子树上所有决策点对答案的贡献将会多1个逆序数。并且由于2比3要小，所以数字2的右侧上所有的决策点对答案的贡献将会减少1个逆序数，数字2左侧上所有决策点对答案的贡献将会增加1个逆序数，直接做区间修改操作。

现在决策点中，权值最小的节点是2和6中间的节点，所以将3插入到2和6的中间，并重复这一过程。就可以算出将奇数插入到偶数排列中，逆序数的增加量，再加上这个排列一开始的逆序数，就是答案。

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1000005;
int stot,stop,sstk[MAXN],n,a[MAXN],b,c,root1,root2,root3,root,l1,r1,m,number[MAXN],tail;
int numpos[MAXN],kpos[MAXN];
long long ans;
char Q[5];
struct tree
{
    int ch[2];
    int fa;
    int size;
    long long minnum;
    int minpos;
    long long lazy;
    int num;
} t[MAXN];

void pushdown(int root)
{
    if(!root)return;
    if(t[root].lazy)
    {
        t[root].minnum+=t[root].lazy;
        t[root].num+=t[root].lazy;
        if(t[root].ch[0])
        {
            t[t[root].ch[0]].lazy+=t[root].lazy;
        }
        if(t[root].ch[1])
        {
            t[t[root].ch[1]].lazy+=t[root].lazy;
        }
        t[root].lazy=0;
    }
    return;
}
void update (int root)
{
    if(!root)return;
    pushdown(t[root].ch[0]);
    pushdown(t[root].ch[1]);
    t[root].size=1+t[t[root].ch[0]].size+t[t[root].ch[1]].size;
    t[root].minnum=t[root].num;
    t[root].minpos=root;
    if(t[root].minnum>t[t[root].ch[0]].minnum)
    {
        t[root].minnum=t[t[root].ch[0]].minnum;
        t[root].minpos=t[t[root].ch[0]].minpos;
    }
    if(t[root].minnum>t[t[root].ch[1]].minnum)
    {
        t[root].minnum=t[t[root].ch[1]].minnum;
        t[root].minpos=t[t[root].ch[1]].minpos;
    }
    return;
}
void push_until(int root)
{
    while(root)
    {
        sstk[++stop]=root;
        root=t[root].fa;
    }
    while(stop)
    {
        pushdown(sstk[stop--]);
    }
    return;
}
void rot(int root)
{
    int fa=t[root].fa;
    int gfa=t[fa].fa;
    int t1=(root!=t[fa].ch[0]);
    int t2=(fa!=t[gfa].ch[0]);
    int ch=t[root].ch[1^t1];
    t[root].fa=gfa;
    t[root].ch[1^t1]=fa;
    t[fa].ch[0^t1]=ch;
    t[fa].fa=root;
    t[ch].fa=fa;
    t[gfa].ch[0^t2]=root;
    update(fa);
    return;
}
int splay(int root)
{
    push_until(root);
    while(t[root].fa)
    {
        int fa=t[root].fa,gfa=t[fa].fa;
        if(gfa)
        {
            (t[fa].ch[0]==root)^(t[gfa].ch[0]==fa)?rot(root):rot(fa);
        }
        rot(root);
    }
    update(root);
    return root;
}
int kth(int root,int k)
{
    for(;;)
    {

        pushdown(root);
        if(k<=t[t[root].ch[0]].size)
        {
            root=t[root].ch[0];
        }
        else if(k>t[t[root].ch[0]].size+1)
        {
            k-=t[t[root].ch[0]].size+1;
            root=t[root].ch[1];
        }
        else
        {
            return splay(root);
        }
    }
}
int links(int root1,int root2)
{
    if(!root1||!root2)return root1|root2;
    root1=kth(root1,t[root1].size);
    t[root1].ch[1]=root2;
    t[root2].fa=root1;
    update(root1);
    return root1;
}
void cuts(int root,int k,int &root1,int &root2)
{
    if(k==0)
    {
        root1=0;
        root2=root;
        return;
    }
    root1=kth(root,k);
    root2=t[root1].ch[1];
    t[root1].ch[1]=t[root2].fa=0;
    update(root1);
    return;
}
int build(int l,int r)
{
    if(r<l)return 0;
    int mid=(l+r)>>1;
    int new_node=++stot;
    t[new_node].num=number[mid];
    if(number[mid]>999999999)
    {
        kpos[number[mid]-999999999]=new_node;
    }
    t[new_node].fa=0;
    t[new_node].lazy=0;
    t[new_node].ch[0]=build(l,mid-1);
    t[new_node].ch[1]=build(mid+1,r);
    t[t[new_node].ch[0]].fa=new_node;
    t[t[new_node].ch[1]].fa=new_node;
    update(new_node);
    return new_node;
}
int newnodes(long long num)
{
    t[++stot].fa=0;
    t[stot].ch[0]=t[stot].ch[1]=0;
    t[stot].lazy=0;
    t[stot].num=t[stot].minnum=num;
    t[stot].size=1;
    t[stot].minpos=stot;
    return stot;
}
void init()
{
    stot=0;
    root=0;
}
long long sum[MAXN];
int lowbit(int x)
{
    return x&-x;
}
long long q(int x)
{
    long long ans=0;
    while(x)
    {
        ans+=sum[x];
        x-=lowbit(x);
    }
    return ans;
}
void change(int x,long long num)
{
    while(x<=n)
    {
        sum[x]+=num;
        x+=lowbit(x);
    }
    return;
}
int main()
{
    while(scanf("%d",&n)!=EOF)
    {
        init();
        ans=0;
        t[0].num=t[0].minnum=999999999;
        int cnt=0;
        for(int i=1;i<=n+1;++i)
        {
            if(i&1)
            {
                number[i]=cnt++;
            }
            else
            {
                number[i]=999999999+cnt;
            }
            sum[i]=0;
        }
        root=build(1,n+1);
        for(int i=1;i<=n/2;++i)
        {
            scanf("%d",&a[i]);
            numpos[a[i]]=kpos[i];
        }
        for(int i=n/2;i;--i)
        {
            ans+=q(a[i]-1);
            change(a[i],1);
        }
        for(int i=1;i<=n;i+=2)
        {
            root=splay(t[root].minpos);
            root1=t[root].ch[0];
            t[root1].fa=t[root].ch[0]=0;
            root2=t[root].ch[1];
            t[root2].fa=t[root].ch[1]=0;
            long long costs=t[root].num;
            ans+=costs;
            int temp1=newnodes(costs);
            int temp2=newnodes(costs);
            int temproot=newnodes(999999999);
            t[temproot].ch[0]=temp1;
            t[temp1].fa=temproot;
            t[temproot].ch[1]=temp2;
            t[temp2].fa=temproot;
            update(temproot);
            root=links(root1,temproot);
            root=links(root,root2);
            root=splay(temproot);
            t[t[root].ch[0]].lazy+=1;
            update(root);
            root=splay(numpos[i+1]);
            t[t[root].ch[0]].lazy+=1;
            t[t[root].ch[1]].lazy-=1;
            update(root);
        }
        printf("%lld\n",ans);
    }
    return 0;
}