inv 牛客网多校

本文主要是介绍inv 牛客网多校，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.nowcoder.com/acm/contest/143/D

给一个1 3 ... n-1的a序列 和一个2 4 ... n的排列的b序列 问归并后最小逆序对数 肯定考虑用a插b 因为a是有序的(无脑解释)

首先有个结论 a序列插入时 a[i+1]插入的最优位置一定在a[i]的右边

//(1,i)|(b[j]>a[i]) 代表[1,n]内有多少b[j]大于a[i]

对于每个a[i] 找一个p使(1,i)|(b[p]>a[i])+(i+1,n)|(b[p]<a[i])最小 该式子可以化为a[i]/2+( (1,i)|(b[p]>a[i])-(1,i)|(b[p]<a[i]) ) 设对于i来说 f[i][j]=( (1,i)|(b[j]>a[i])-(1,i)|(b[j]<a[i]) ) 即我们需要在f[i][1] ... f[i][n]内选一个最小值作为最优解

当i==1是 显然f[i][1]是最小的 当i>1时我们需要根据f[i-1][1] ... f[i-1][n]来得出f[i][1] ... f[i][n]

假设a[i]=2*i-1 a[i+1]=2*i+1 且b序列中2*i这个数的位置在v

(1) 对于j>=v 之前在i-1时 a[i-1]=2*i-1<b[v]=2*i 而现在变为a[i]=2*i+1>b[v]=2*i 也就是b[v]由(1,i)|(b[j]>a[i])-(1,i)|(b[j]<a[i])的左边跑的了右边 此消彼长 f[i][j]=f[i-1][j]-2

(2) 对于i<v b[v]并没有造成什么影响 故f[i][j]=f[i-1][j]

这样每次对一个后缀[v,n]减二 最后取个min即可

最巧的地方在于a是全奇 b是全偶 枚举a时每次只增加2 只用考虑夹在a[i-1]与a[i]之间的那个b值即可

至于为什么会有 a序列插入时 a[i+1]插入的最优位置一定在a[i]的右边 我的理解是因为每次对一个后缀减二 所以每次更新后的f[i]是递减的 所以最优解肯定出现在右边(强行解释)

#include <bits/stdc++.h>
using namespace std;
#define ll long longstruct node
{int l;int r;ll val;ll laz;
};node tree[400010];
int ary[100010],pos[100010];
int n;void buildI(int l,int r,int cur)
{int m;tree[cur].l=l;tree[cur].r=r;tree[cur].val=0;if(l==r) return;m=(l+r)/2;buildI(l,m,2*cur);buildI(m+1,r,2*cur+1);
}ll queryI(int pl,int pr,int cur)
{ll res;if(pl<=tree[cur].l&&tree[cur].r<=pr){return tree[cur].val;}res=0;if(pl<=tree[2*cur].r) res+=queryI(pl,pr,2*cur);if(pr>=tree[2*cur+1].l) res+=queryI(pl,pr,2*cur+1);return res;
}void updateI(int tar,int cur)
{tree[cur].val++;;if(tree[cur].l==tree[cur].r) return;if(tar<=tree[2*cur].r) updateI(tar,2*cur);else updateI(tar,2*cur+1);
}void pushup(int cur)
{tree[cur].val=min(tree[2*cur].val,tree[2*cur+1].val);
}void pushdown(int cur)
{if(tree[cur].laz!=0){tree[2*cur].val+=tree[cur].laz;tree[2*cur].laz+=tree[cur].laz;tree[2*cur+1].val+=tree[cur].laz;tree[2*cur+1].laz+=tree[cur].laz;tree[cur].laz=0;}
}void buildII(int l,int r,int cur)
{int m;tree[cur].l=l;tree[cur].r=r;tree[cur].val=l;tree[cur].laz=0;if(l==r) return;m=(l+r)/2;buildII(l,m,2*cur);buildII(m+1,r,2*cur+1);
}void updateII(int pl,int pr,int cur)
{if(pl<=tree[cur].l&&tree[cur].r<=pr){tree[cur].val-=2;tree[cur].laz-=2;return;}pushdown(cur);if(pl<=tree[2*cur].r) updateII(pl,pr,2*cur);if(pr>=tree[2*cur+1].l) updateII(pl,pr,2*cur+1);pushup(cur);
}int main()
{ll ans;int i;scanf("%d",&n);for(i=1;i<=n/2;i++){scanf("%d",&ary[i]);pos[ary[i]/2]=i;}buildI(1,n/2,1);ans=0;for(i=1;i<=n/2;i++){ans+=queryI(ary[i]/2,n/2,1);updateI(ary[i]/2,1);}//printf("***%lld***\n",ans);buildII(0,n/2,1);for(i=1;i<=n/2;i++){ans+=((i-1)+tree[1].val);updateII(pos[i],n/2,1);}printf("%lld\n",ans);return 0;
}

 

这篇关于inv 牛客网多校的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---