题意:给一个偶数序列和一个固定的奇数序列[1、3、5...n-1],要求归并两个序列使得最终序列逆序对数最少
思路:考虑偶数序列不动,用奇数去插入,假设奇数i已经插入到最优位置k,考虑i+2的最优位置,假设已经算出i在每个插入位置的贡献,转移到i+2的话,只有i+1会产生影响,此时有两种情况
1)i+1位置在k左边,此时i+1对i+2不产生贡献,k依旧是最优位置
2)i+1位置在k右边,此时i+1对i+2产生了贡献,而最优位置只可能在右边
所以,每个奇数的最优位置已经满足从左到右的排列,那只需要计算每个奇数的最优位置的贡献相加即可(当然偶数序列内部的逆序对也要算)。
如何计算:假设奇数i在每个插入位置的贡献已经算出,考虑i+2在每个插入位置的贡献,此时依旧只有i+1产生影响。假设i+1位置为k,那么在k前面的所有位置,本来i放i+1前面不产生贡献,现在i+2放到i+1前面会产生贡献,后面同理,本来有贡献现在没了贡献,所以是k前面的位置全部加一,k后面的位置全部减一,用线段树维护一下,答案取所有位置最小值
核心代码:
struct Node{ int l,r,min; int tag; int mid(){return l+r>>1;} int len(){return r-l+1;} }seg[N<<2]; #define lc i<<1 #define rc i<<1|1 void build(int i,int l,int r){ seg[i].l = l; seg[i].r = r; seg[i].tag = 0; seg[i].min = 0; if(l!=r){ seg[i].min = inf; int mid = seg[i].mid(); build(lc,l,mid); build(rc,mid+1,r); } } void pushdown(int i){ if(seg[i].tag){ seg[lc].min += seg[i].tag; seg[rc].min += seg[i].tag; seg[lc].tag += seg[i].tag; seg[rc].tag += seg[i].tag; seg[i].tag = 0; } } void update(int i,int l,int r, int v){ if(seg[i].l == l && seg[i].r == r){ seg[i].tag += v; seg[i].min += v; return; } pushdown(i); int mid = seg[i].mid(); if(r<=mid)update(lc,l,r,v); else if (l>mid) update(rc,l,r,v); else { update(lc,l,mid,v); update(rc,mid+1,r,v); } seg[i].min = min(seg[lc].min, seg[rc].min); } int query(int i,int l,int r){ if(seg[i].l == l && seg[i].r == r){ return seg[i].min; } pushdown(i); int mid = seg[i].mid(); if(r<=mid)return query(lc,l,r); else if (l>mid) return query(rc,l,r); else return min(query(lc,l,mid),query(rc,mid+1,r)); } int pos[N]; int b[N]; void work(){ int n;scanf("%d", &n); for(int i = 1;i<n/2;i++){ scanf("%d", &b[i]); pos[b[i]] = i; } build(1,0,n/2); update(1,0,0,0); for(int i = 1;i<n/2;i++){ update(1,i,i,i); } ll ans = 0; for(int i = 3;i<n;i+=2){ int k = pos[i-1]; update(1,0,k-1,1); update(1,k,n/2,-1); ans += query(1,0,n/2); } }
全部评论
(0) 回帖