》》》算法竞赛

/**
 * @file            
 * @author          jUicE_g2R(qq:3406291309)————彬(bin-必应)
 *						一个某双流一大学通信与信息专业大二在读	
 * 
 * @brief           一直在算法竞赛学习的路上
 * 
 * @copyright       2023.9
 * @COPYRIGHT			 原创技术笔记：转载需获得博主本人同意，且需标明转载源
 *
 * @language        C++
 * @Version         1.0还在学习中  
 */

• UpData Log👆 2023.9.9 更新进行中
• Statement0🥇 一起进步
• Statement1💯 有些描述可能不够标准，但能达其意

技术提升站点

树状数组求解

• 思路

把 队列 数据看成 数组的下标 ， 即 5 4 2 6 3 1 对应 a[5] a[4] a[2] a[6] a[3] a[1] ，但这样的话会浪费很多空间，所以使用 “离散化” 将原来的数字变成他们的相对大小。

1） 逆序处理：从 a[1] 开始

现在是 a[1] a[3] a[6] a[2] a[4] a[5] ，当前数字的前一个数的前缀和 就是 该数为最大数 的逆序对数。

数字 1 ：把 a[1] + 1，计算sum[0]，逆序对数：ans += sum[0] = 0

数字 3：把 a[3] + 1，计算sum[2]，逆序对数：ans += sum[2] = 1

…

2）正序处理：从a[5] 开始

当前已经处理的数字个数 减掉 当前数字的前缀和 就是 该数为最小数 的逆序对数

数字 5 ：把a[5] + 1，当前处理了一个数，逆序对数：ans += （1 - sum[5])= 0

数字 4 ：把a[4] + 1，当前处理了两个数，ans += （2 - sum[5])= 1

…

• 代码展示

//逆序解题
#include<bits/stdc++.h>
using namespace std;
using LL=long long int;
const int MAX=5e5+5;
#define     lowbits(x)      ((x) & (-x))
vector<int> BITree(MAX,0);
vector<int> r(MAX,0);           //离散化数组
LL ans=0;                       //逆序对的个数
struct node{
    int id;                     //编号
    int val;                    //当前元素值                              
} a[MAX];                       //原始数组
bool cmp(node a,node b){
    if(a.val==b.val)    return a.id<b.id;               //如果元素值相同，让先出现的排在前面
    return a.val<b.val;                                 //不相等时，值大的在后面
}
void Update(int id,int increse){               		    //维护
    int temp=id;
    while(temp<=MAX){
        BITree[temp]+=increse;                  		//对每个父节点都要修改增量
        temp+=lowbits(temp);                    		//向前反推父节点直到根节点停止
    }
}
int GetSum(int id){                             		//前缀和
    int sum=0;      int temp_id=id;
    while(temp_id>0){
        sum+=BITree[temp_id];
        temp_id-=lowbits(temp_id);
    }
    return sum;
}
int main(void){
    int n;      scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf(" %d",&a[i].val);
        a[i].id=i;                                      //记录初始排列顺序
    }
    sort(a+1,a+1+n,cmp);                              	//升序排列
    for(int i=1;i<=n;i++)                               //离散化处理
        r[a[i].id]=i;    
    for(int i=n;i>0;i--){
        Update(r[i],1);
        ans+=GetSum(r[i]-1);
    }
    cout<<ans;
    return 0;
}

正序只需将下面

for(int i=n;i>0;i--){
    Update(r[i],1);
    ans+=GetSum(r[i]-1);
}

改为：

for(int i=1;i<=n;i++){
    Update(r[i],1);
    ans+=(i - GetSum(r[i]));
}

归并排序方法解决逆序数问题