求条

xuyunlong120820 @ 2024-12-08 11:34:22

#include <bits/stdc++.h>
using namespace std;
int t[500005],a[500005],tmp[500005],n,m;
int lowbit(int x){
    return x&-x; 
}
void add(int x,int k){
    for(int i=x; i<=n; i+=lowbit(i)) t[i]+=k;
    return;
}
int sum(int x){
    int ans=0;
    for(int i=x; i>=1; i-=lowbit(i)) ans+=t[i];
    return ans;
}
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n;
    cin>>n;
    for(int i=1; i<=n; i++){
        cin>>a[i];
    }
    for (int i=1; i<=n; i++)
        tmp[i]=a[i];
    sort(tmp+1,tmp+n+1);
    int len=unique(tmp+1,tmp+n+1)-(tmp+1);
    for(int i=1; i<=n; ++i)
        a[i]=lower_bound(tmp+1,tmp+len+1,a[i])-tmp;
    int ans=0;
    for(int i=1; i<=n; i++){
        add(a[i],1);
        ans+=i-sum(a[i]);
    }
    cout<<ans<<"\n";
    return 0;
}

by ZMY_123 @ 2024-12-09 21:10:27

#include <iostream>
using namespace std;
long long sum = 0;

void merge(long long c[],long long d[],int l,int m,int r){
    int i = l,j = m+1;
    int k = l;
    while((i<=m) && (j<=r)){ //判断不为空 
        if (c[i]<=c[j]){
            d[k++] = c[i++];
        }
        else{
            d[k++] = c[j++];
            sum+=(m - i + 1);//加逆序对
        }
    }
    if (i>m){//如果左边为空 
        for (int q = j;q<=r;q++){
            d[k++] = c[q];
        }
    }
    else{ 
        for (int q = i;q<=m;q++){
            d[k++] = c[q];
        }

    }
}
void mergepass(long long x[],long long y[],int s,int n){//s步长 
    int i = 0;
    while(i<=n-2*s){
        //合并大小为S的相邻2字段数组
        merge(x,y,i,i+s-1,i+2*s-1);
        i = i+2*s; 
    }
    //剩下的元素个数少于2s 
    if (i+s<n)merge(x,y,i,i+s-1,n-1);
    else for (int j = i;j<=n-1;j++)
            y[j] = x[j];
}
//合并排序算法 
void mergesort(long long a[],int n){
    long long *b = new long long [n];
    int s = 1;
    while(s<n){
        mergepass(a,b,s,n);
        s+=s;
        mergepass(b,a,s,n);
        s+=s;
    }
}
int main(){
    long long p[500005];
    int n;
    cin >> n;
    for (int i = 0;i<n;i++){
        cin >> p[i];
    }
    mergesort(p,n);
    cout << sum;
    return 0;
}

AC代码，自习参考，看不懂可以问我。

求关