牛客多校4.I.Inverse Pair 构造

牛客多校4.I.Inverse Pair

Analysis

定义序列的全忠表示序列中逆序对的数量。

则给定序列 a a a​，构造序列 b b b​，其中 b i b_i bi​​为 0 或 1 0 或 1 0或1，使得 c i = a i + b i c_i = a_i+ b_i ci​=ai​+bi​​得出的 c c c序列权重最小。

首先分析 c i c_i ci​​​，对于其而言，容易知道 c i c_i ci​只可能取 a i a_i ai​或 a i + 1 a_i + 1 ai​+1，因为题目要求 c c c​权重最小化，那么我们应该考虑如何使权重最小化：也就是什么时候+1才能使逆序对数量最小。

显然：如果 x x x 在 x + 1 x+1 x+1 的后面, 则我们把 x x x 这个数 + 1 +1 +1, x + 1 x+1 x+1 不变, 就能让逆序对减少 1 1 1。那么我们只需要统计逆序对的个数，按上述规则确定 B B B的 0 , 1 0 , 1 0,1取值:如果在前面的数改变之后还存在比它大 1 1 1的数，那么这个位置 B B B为 1 1 1​，逆序对数减 1 1 1，统计逆序对个数可以归并，也可以树状数组等等。

AC Code

#include 
#define int long long
#define mod 1000000007
#define N 100005
using namespace std;
int n, d, a1, a2, t, sum, tot;
int a[200005], c[200005], b[200005];
int lowbit(int x){ return x & -x; }
void add(int x){
    while (x > n;
    for (int i = 1; i > a[i];
        sum += query(a[i]);
        add(a[i]);
        b[a[i]] = i;
    }
    sum = n * (n - 1) / 2 - sum;
    t = 1;
    while (t  b[t + 1])  sum--, t += 2;
        else t += 1;
    }
    cout