树状数组和逆序对

逆序对的概念

在一个有 $__int128 $了，但是要注意 $__int128 $ 类型是不能用 $cin、cout、scanf、printf$ 的，要自己手写输入输出，这里不用输入，我写了一个输出。

#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define lowbit(x) x&(-x)
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef long long ll;
typedef __int128 lll;
const int maxn = 5e6+9;
lll  t[maxn];
int n,m,num[maxn];
vector<int>a;

void update(int now,int value){
    while(now<=m){
        t[now] += value;
        now += lowbit(now);
    }
}

ll query(int now){
    ll an = 0;
    while(now){
        an += t[now];
        now -= lowbit(now);
    }
    return an;
}

//__int128输出
void print(lll x){
    if(x == 0) return;
    print(x/10);
    int tem = x%10;
    cout<<tem;
}

int main(){
    speedUp_cin_cout
    cin>>n;
    For(i,1,n) cin>>num[i],a.push_back(num[i]);
    sort(a.begin(),a.end());
    a.erase(unique(a.begin(),a.end()),a.end());
    m = a.size();
    lll ans = 0;
    For(i,1,n) {
        num[i] = lower_bound(a.begin(),a.end(),num[i])-a.begin()+1;
        //计算比num[i]大的数的坐标和
        lll l = (query(m)-query(num[i]));
        //右边部分的区间长度
        lll r = n-i+1;
        ans += l*r;
        //加入坐标
        update(num[i],i);
    }
    if(ans) print(ans);
    else cout<<0;
    return 0;
}

逆序对和排序问题

P1966 火柴排队
NC16526火柴排队

题意概括

有两列都是 $n$ 根的火柴，同一列高度互不相同，将两列火柴直接的距离定义为 $\sum\left(a_{i}-b_{i}\right)^{2}$ 。其中 $a_i$ 表示第一列火柴中第 $i$ 个火柴的高度，$b_i$ 表示第二列火柴中第 $i$ 个火柴的高度。仅可以交换相邻两根火柴的位置，求要让两列火柴距离最小的最小交换次数，并对 $10^8-3$ 取模。数据满足 $1 \leq n \leq 10^{5}, 0 \leq$ 火柴高度 $<2^{31}$ 。

分析

这道题看起来和逆序对好像没有什么关系，需要一些分析后才可以和逆序对联系起来。
首先我们要分析出什么时候火柴距离最小。展开火柴距离的式子：

\[\begin{array}{c}\sum_{i=1}^{n}\left(a_{i}-b_{i}\right)^{2} \\\\=\sum_{i=1}^{n}\left(a_{i}^{2}-2 a_{i} b_{i}+b_{i}^{2}\right) \\\\=\sum_{i=1}^{n}\left(a_{i}^{2}+b_{i}^{2}\right)-\sum_{i=1}^{n}\left(2 a_{i} b_{i}\right)\end{array}\]

因为所有火柴高度已经定下来了，即 $\sum_{i=1}^{n}\left(a_{i}^{2}+b_{i}^{2}\right)$ 大小不会随着交换而改变。所以我们要最大化 $\sum_{i=1}^{n}\left(2 a_{i} b_{i}\right)$ 才能使这个式子最小。根据排序不等式，我们知道同序和 $\geqslant$ 乱序和 $\geqslant$ 逆序和（证明可以自行百度，会用就行了）。所以我们要让火柴排成“同序和”的顺序即可。换句话说，假如我们仅交换 $b$ 列火柴（交换 $a$ 和 $b$ 是等效的，我们选一列交换，让另一列不动就行）就是让 $b$ 的第 $i$ 小与 $a$ 的第 $i$ 小怼齐。
这其实是一种排序，认识到这一点很重要。我们原来平时的排序，以升序为例，其实是把下标当做一个标准序列 $standard[~]=\{1,2,3,···,n\}$ ,然后把要排序的数组 $num$ 按照 $standard$ 从小到大怼齐，也就是 $num$ 的第 $i$ 小与 $standard$ 的第 $i$ 小怼齐。而在只能进行相邻交换的前提下，最小的交换次数就是 $num$ 的逆序对数目（可以自己感性证明一下）。现在我们把标准序列的定义换成一个指示 $a$ 的第 $i$ 小的位置的数组，即 $a[~standard[i]~]$ 是 $a$ 的第 $i$ 小，要排序的数组定义改为指示 $b$ 的第 $i$ 小的位置的数组 ,即 $b[~num[i]~]$ 是 $b$ 的第 $i$ 小。然后新建一个序列 $q$,让 $q[~standard[i]~] = num[i]$ ,即让 $num[~]$ 按照 $standard[~]$ 进行“排序”，最终答案就是 $q$ 的逆序对数目。
这里是比较难理解的，需要自己列几个例子辅助思考。剩下部分其实就是求逆序对的模板。虽然数据范围很大，但是我们用了一种特殊的离散化方式，将离散化数组 $p_i$ 定义为 $a$ 或 $b$ 的第 $i$ 小的位置（也就是上文中的 $standard$ 和 $num$）。

$Code:$

#include<bits/stdc++.h>
using namespace std;
#define For(i,sta,en) for(int i = sta;i <= en;i++)
#define lowbit(x) x&(-x)
#define speedUp_cin_cout ios::sync_with_stdio(false);cin.tie(0); cout.tie(0);
typedef long long ll;
const int maxn = 2e5+9;
const int mod = 1e8-3;
int a[maxn],b[maxn],q[maxn],pa[maxn],pb[maxn];
ll t[maxn],n;

void update(int now){
    while(now <= n){
        t[now]++;
        now += lowbit(now);
    }
}

ll query(int now){
    ll an = 0;
    while(now){
        an =  (an + t[now])%mod;
        now -= lowbit(now);
    }return an;
}
bool cmp1(int &x,int &y){
    return a[x] < a[y];
}
bool cmp2(int &x,int &y){
    return b[x] < b[y];
}
int main(){
    speedUp_cin_cout  //读写优化
    cin>>n;
    For(i,1,n) cin>>a[i],pa[i] = i;  //pa，pb为离散化数组
    For(i,1,n) cin>>b[i],pb[i] = i;
    sort(pa+1,pa+1+n,cmp1);
    sort(pb+1,pb+1+n,cmp2);
    For(i,1,n)  q[pa[i]] = pb[i];      //新建序列
    ll ans = 0;
    //求q的逆序对
    For(i,1,n){
        ans = (((query(n) - query(q[i]))%mod + ans)%mod+mod)%mod;
        update(q[i]);
    }
    cout<<ans<<endl;
    return 0;
}

总结

逆序对和树状数组的联系还是挺大的，很多涉及逆序对的题目都可以尝试用树状数组冲一下，当然归并排序也是一定要掌握的啦。

ailanxier