Nowcoder-2018ACM多校训练营（第五场）D inv

时间限制：C/C++ 2秒，其他语言4秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述 

Kanade has an even number n and a permutation b of all of the even numbers in [1,n]

Let a denote an array [1,3,5....n-1] , now you need to find a permutation of [1,n] satisfy both a and b are subsequence of it and minimize the number of inverse pair of it.

 

输入描述:

The first line has a positive even integer n

The second line has n/2 positive even integers b[i]

输出描述:

Output the number of inverse pair of the permutation you find.

示例1

输入

复制

6
2 6 4

输出

复制

2

说明

[1,2,3,5,6,4]

备注:

1≤ n≤ 2*105

题解：由于奇数序列是递增的，考虑将奇数序列插入偶数系列中。设偶数序列中当前遍历到A[i]，假设前i-1项中最大的为mx

1. 当A[i] < mx时，值为(A[i],mx)的奇数个数有cnt=(mx-A[i])/2，这些数要么全部放在mx前面，要么全部放在A[i]的后面，逆序贡献总是cnt（放在中间的话逆序贡献为2*cnt），我们选择放在A[i]的后面。
2. 当A[i] >= mx时，原本放在mx后面的且大于A[i]的奇数，可以选择放在A[i]的后面，此时没有贡献。

对于偶数序列之间的逆序，用归并或者树状数组求一下即可。

#include <bits/stdc++.h>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define x first
#define y second
#define rep(i,a,b) for(int i=a;i<b;++i)
#define per(i,a,b) for(int i=a-1;i>=b;--i)
#define fuck(x) cout<<'['<<#x<<' '<<(x)<<']'
#define FIN freopen("in.txt","r",stdin);
using namespace std;
typedef long long ll;
typedef vector<int> VI;
typedef pair<int, int> PII;

const int INF = 0x3f3f3f3f;
const ll INFLL = 0x3f3f3f3f3f3f3f3fll;
const int mod = 1e9 + 7;
const int MX = 2e5 + 5;

ll pow(ll a, int b) {
    ll ret = 1;
    while(b) {if(b & 1) ret = ret * a % mod; a = a * a % mod; b >>= 1;}
    return ret;
}
inline ll mul(ll a, ll b, ll c) {return a * b % mod * c % mod;}

int b[MX], c[MX];
ll ans;
void solve(int l, int r) {
    if(r - l <= 1) return;
    int m = (l + r) >> 1, p1 = l, p2 = m;
    solve(l, m), solve(m, r);
    rep(i, l, r) {
        if(p2 >= r || (p1 < m && b[p1] < b[p2])) c[i] = b[p1++];
        else c[i] = b[p2++], ans += m - p1;
    }
    rep(i, l, r) b[i] = c[i];
}
int main() {
    //FIN;
    int n; cin >> n;
    rep(i, 0, n / 2) scanf("%d", &b[i]);
    priority_queue<int>q;
    rep(i, 0, n / 2) {
        int x = b[i] / 2;
        q.push(x);
        if(q.top() > x) {
            ans += q.top() - x;
            fuck(b[i]),fuck(q.top()-x),puts("");
            q.pop();
            q.push(x);
        }
    }
    solve(0, n / 2);
    cout << ans << endl;
    return 0;
}