CF1601C
_YyD_
·
·
个人记录
吐槽：题解里为啥都是线段树，这里来提供一种其他的做法。
先做一种简单的情况，a 为 1 到 n 之间所有的奇数，b 为 1 到 n 之间所有的偶数（原题直接讲涉及到元素不存在与元素重复的元素，会了这个后直接改一改就好了）：
c的逆序对数=a的逆序对数+b的逆序对数+ab合在一起的逆序对数
前两者直接树状数组算就好了，难点是后一个。
对于 b，显然升序排序一定是更优的（自己证明一下）。
一些定义：
设 x 为目前最靠右（最大）的数（根据状态动态变化）。
对于 a，我们 i 从 1~n 考虑插入，新加入的一个，如果比 x 还要大，那么直接插在 b 中它权值的位置，不会产生贡献。接下来是比它小的情况，比较复杂，换一下行。
先将 a[i] 加入在x的右边，逆序对数贡献为 a[i] 的数值到x之间b序列中数的个数，因为现在考虑的是一个排列的情况（所有元素都出现过），所以直接是 x-a[i]。
但是这样子 x 一直会变大，之后插入的数比 x 小的情况只会越来越少，咋办捏。
我们考虑移动 a[i]，把 x 和它一起向左移动，一直移到 a[i] 的时候，逆序对的个数都是不变的（a[i] 贡献的 -1，x 的贡献 +1）（再移 a[i] 也加，x 也加），这样子 x 就会变小，之后加进来的数比 x 大（不产生贡献）的可能就更大。
但这样有个明显的问题，在 a[i] 与 x 之间如果有数，移动了原先放在那里的数，逆序对个数不一定相比之前还是不变（有可能增加），有了这个阻碍，移动不一定比放着不动要优。
移动or不移动？这很难决策。
接下来就到了做法的重难点，怎么维护？
我们考虑用一个堆来维护 x。
先放代码再解释（注意我们说的是简单化的情况，没有重复元素，每个元素都出现过，不然放一起说比较乱）：
priority_queue<int> q;
q.push(a[1]);
for(int i=2;i<=(n/2);++i){
if(q.top()>a[i]) ans+=q.top()-a[i],q.pop(),q.push(a[i]);
q.push(a[i]);
}
先说if里面的内容：
$q.pop(),q.push(a[i])$ 把 $x$ 移动到 $a[i]$ 的位置。
但大家应该立马发现不对了，之前不是说移动不一定优嘛？
对，你说的没错，所以这里不是真正的移动，只是我们当作了它移动。
为什么能这样呢，因为我们用的是堆，如果再次用到现在这个移动过的 $x$，只有当大于它的所有元素都没了（被假装移动了），这时我们再真正的移动它。
再解释一遍，只有当它被访问了，它才算真正的移动，也只有比它大的，也就是我们之前说的阻碍都被清空了，它才能被访问了，这样一切就变得合理起来了！
同理，$q.push(a[i])$ 是直接当作了 $a[i]$ 放到了 $c$ 中 $a[i]$ 的位置。
而且这样堆中的数字个数总会是 $i$，很合理吧。
简化版题意的代码（其实这个就是正睿的一道题目，有权限可以自己看看）：
[简化题意原地址](http://www.zhengruioi.com/problem/247)
```cpp
int a[N],c[N];
priority_queue<int> q;
int main(){
int n;
scanf("%d",&n);
for(int i=1;i<=n>>1;++i) scanf("%d",&a[i]),a[i]>>=1;
ll ans=0;
for(int i=n/2;i;--i){
for(int j=a[i]-1;j;j^=j&(-j)) ans+=c[j];
for(int j=a[i];j<=n;j+=j&(-j)) ++c[j];
}
q.push(a[1]);
for(int i=2;i<=n>>1;++i){
if(q.top()>a[i]) ans+=q.top()-a[i],q.pop(),q.push(a[i]);
q.push(a[i]);
}
printf("%lld",ans);
}
```
这样这个简化的题意就做完了，考虑复杂的：
其实就是左右端点细节处理一下就好了，相信之前的内容看懂了再看下面的代码也不难，就自己理解一下吧（bushi。
```cpp
int n,m,a[N],b[N],va[N],pu,fw[N],ans;
void add(int x,int d){for(;x<=n;x+=x&-x) fw[x]+=d;}
int query(int x){int res=0;for(;x;x-=x&-x) res+=fw[x];return res;}
void task(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=m;i++) scanf("%d",&b[i]);
ans=0;
for(int i=1;i<=n;i++) va[i]=a[i];
sort(va+1,va+n+1);
for(int i=1;i<=n;i++) fw[i]=0;
for(int i=n;i>=1;i--){
int v=lower_bound(va+1,va+n+1,a[i])-va;
ans+=query(v-1);
add(v,1);
}
sort(b+1,b+m+1);
priority_queue<int> q;
for(int i=1;i<=n;i++){
int x=lower_bound(b+1,b+m+1,a[i])-b;
int y=upper_bound(b+1,b+m+1,a[i])-b;
if(!q.empty()&&q.top()>y) {
ans+=q.top()-y;
q.pop();
q.emplace(y);
}
q.emplace(x);
}
printf("%lld\n",ans);
}
```