题意:给你一个长度为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; }
全部评论
(0) 回帖