题解 P2309 【loidc,卖卖萌】
lmrttx
2020-11-29 10:55:18
~~介绍详细的~~本文注重讲解如何把题目转化成求逆序对问题和如何用归并求解逆序对。请先掌握[前缀和](https://www.cnblogs.com/-Ackerman/p/11162651.html)。
------------
暴力枚举三个点，时间 $O(n^3)$,肯定会爆炸。
字串的每一个数之和就相当于**区间之和**，当区间之和为正数时，就符合条件。于是用前缀和建立一个数组 $b$。用这个数组跑一遍循环，因为前缀和中,$b[r]-b[l-1]$ 表示区间 $[l,r]$ 的区间和，所以时间为 $O(n^2)$。因为 $n$ 最大为 1e5,所以也会超时。
那怎样和年轻人一样快呢？？？
颓柿子吧。
当满足这个式子的时候，不能计入答案：
$$b[r]-b[l-1]<0$$
变化得：
$$b[r]<b[l-1]$$
于是题目变成了正序对。
但是蒟蒻只会逆序对，怎么办呢？？？
想到优先队列中小根堆和大根堆的转化和不等式的性质，只要将数乘上-1，再求逆序对，就不影响答案了。
------------
到此思路完结。实现我们靠归并，因为~~我发现归并的题解较少~~树状数组的代码更长一些。不过本文末尾还是会贴上树状数组求逆序对的代码的。会用归并求逆序对的读者可以自行跳过这块。
归并排序的基本思路就是分而治之。就是将一个数组先分解成一半，再分解成四分之一，一直到只剩叶节点，即每一段都只有一个数时，合并，并在合并时交换数据位置。
归并排序需要辅助数组。
图解：
由于逆序对是**大的在前，小的在后**，所以合并时，交换次数就是逆序对个数（此时归并排序是按从小到大进行排序的）。
代码：
```cpp
void msort(int l,int r){
if(l==r){
return;
//分解成一个数时返回
}
int mid=(l+r)>>1;
//取区间中点
msort(l,mid);msort(mid+1,r);//递归
int i=l,j=mid+1,k=r;//准备合并
while(i<=mid&&j<=r){//这个是边界条件
//a为原数组，r为辅助数组，r最后就是原数组排序后的数列
if(a[i]<=a[j]){
r[k]=a[i];k++;i++;
}else {//从小到大
r[k]=a[j];k++;j++;
ans+=mid-i+1;//统计逆序对数量
}
}
while(i<=mid){
r[k]=a[i];k++;i++;
}
while(j<=r){
r[k]=a[j];k++;j++;
}
//分别处理左右剩余的部分
//最后可以根据需要，看看要不要把r数组的值赋给a数组
}
```
题目就这样做完啦！！！
------------
福利：用树状数组求逆序对数量的代码。题目是[P1908 逆序对](https://www.luogu.com.cn/problem/P1908)，偷偷地告诉你，这是一道双倍经验的题目！
```cpp
#include<bits/stdc++.h>
using namespace std;
int lowbit(int x){return x&-x;}
#define maxn 500010
#define int long long
int a[maxn],b[maxn],tree[maxn],ans,n;
bool cmp(int x,int y){
return a[x]==a[y] ? x>y :a[x]>a[y];
}
int find_(int x){
int res=0;
for(int i=x;i>0;){
res+=tree[i];
i-=lowbit(i);
}
return res;
}
void change(int x){
for(int i=x;i<=n;){
tree[i]++;
i+=lowbit(i);
}
}
signed main(){
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
b[i]=i;
}
sort(b+1,b+n+1,cmp);
for(register int i=1;i<=n;i++){
change(b[i]);
ans+=find_(b[i]-1);
}
cout<<ans;
return 0;
}
```
可以看出，用树状数组求逆序对的思路和归并一样。
------------
谢谢阅读！！！如果本文有不足，可以再评论区指出qwq！