题意：给一个偶数序列和一个固定的奇数序列[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) 回帖