树状数组一

sunpeilun · 2024-12-30 20:55:24 · 个人记录

T2
用树状数组做也可以,但我选择了归并排序。
这题就是求逆序对数量的题,和洛谷上的这题一样,以下是我的思路:

由于归并排序时,左右子序列都是排好序的,所以我们只要在右序列的元素元素进入序列时,统计左序列进入了多少个元素,就是逆序对的数量(因为右序列的每一个元素都能与左序列的每一个元素构成一个逆序对)。
注意事项:
1.开long long
2.记得把剩下的元素放入数组里
3.多测要清空
4.return的值和边界条件
Code:

#include<iostream>
#include<cstring>
using namespace std;
int n,arr[500001],t[500001];
long long f(int l,int mid,int r){
    int i=l,j=mid+1,k=l;
    long long ans=0;
    while(i<=mid && j<=r){
        if(arr[i]<=arr[j]){
            t[k++]=arr[i++];
        }else{
            t[k++]=arr[j++];
            ans+=j-k;
        }
    }
    while(i<=mid) t[k++]=arr[i++];
    while(j<=r) t[k++]=arr[j++];
    for(int i=l;i<=r;i++) arr[i]=t[i];
    return ans;
}
long long merge(int l,int r){
    if(l>=r) return 0;
    int mid=(l+r)/2;
    return merge(l,mid)+merge(mid+1,r)+f(l,mid,r);
}
int main(){
    cin>>n;
    while(n!=0){
        memset(t,0,sizeof(t));
        for(int i=1;i<=n;i++) cin>>arr[i];
        cout<<merge(1,n)<<endl;
        cin>>n;
    }
    return 0;
}