后面一半WA求条

yupeishan2012 @ 2024-10-11 19:28:47

#include <bits/stdc++.h>
using namespace std;

long long n;
long long a[100005],b[100005],c[100005];
long long ans;

inline void read(register long long &a){
    a = 0;
    char c;
    while((c = getchar()) < 48);
    do a = (a << 3) + (a << 1) + (c ^ 48);
    while((c  = getchar()) > 47);
}

void write(register long long v){
    if(v < 10) putchar(v|48);
    else write(v / 10),putchar(v % 10 | 48);
}

long long cmp(long long j,long long k){
    if(a[j] == a[k]) return j > k;
    return a[j] > a[k];
}

long long lowbit(int k){
    return k & -k;
}

void x(long long k){
    while(k <= n){
        b[k] ++;
        k += lowbit(k);
    }
    return ;
}

long long sum;

long long y(int k){
    sum = 0;
    while(k >= 1){
        sum += b[k];
        k -= lowbit(k);
    }
    return sum;
}

int main(){
    read(n);
    for(long long i = 1; i <= n; i++){
        read(a[i]);
        c[i] = i;
    }
    sort(c + 1,c + 1 + n,cmp);
    for(long long i = 1; i <= n; i++){
        x(c[i]);
        ans += y(c[i] - 1);
    }
    write(ans);
    return 0;
}

by YAOhc2012 @ 2024-10-11 19:32:44

@yupeishan2012 《c[i]=i》

by yupeishan2012 @ 2024-10-11 19:35:27

@YAOhc2012 要怎么改呀？

by ggpw_XNW @ 2024-10-11 19:38:08

@yupeishan2012

#include<bits/stdc++.h>
using namespace std;
long long a[500010] , b[500010]; 
long long ans;
void mgsort(int l,int r){
    if(l>=r) return;
    int mid = (l + r) / 2;
    mgsort(l,mid);
    mgsort(mid+1,r);
    int i = l , j = mid + 1 , k = l;
    while(i<=mid&&j<=r){
        if(a[i]<=a[j]){
            b[k] = a[i];
            k++;
            i++;
        }else{
            b[k] = a[j];
            ans += mid - i + 1;
            k++;
            j++;
        }
    }
    while(i<=mid){
        b[k]=a[i];
        i++;
        k++;
    }
    while(j<=r){
        b[k]=a[j];
        j++;
        k++;
    }
    for(int i=l;i<=r;i++) a[i]=b[i];
}
int main(){
    long long n;
    cin >> n;
    for(int i=1;i<=n;i++) cin >> a[i];
    mgsort(1,n);
    cout << ans;
    return 0;
}

by YAOhc2012 @ 2024-10-11 19:38:11

@yupeishan2012 把a[i]离散化

by yupeishan2012 @ 2024-10-11 19:39:47

@YAOhc2012 怎么弄呀 教教呗

by YAOhc2012 @ 2024-10-11 19:39:48

开结构体x[i]，记录a[i]与id（a[i]出现的位置），按a[i]排序，c[x[i].id]=i;

by yupeishan2012 @ 2024-10-11 19:40:28

@User1025109 这是归并排序吗

by YAOhc2012 @ 2024-10-11 19:40:31

意思是：将最小的编号1，次小编号2……最大编号n

by ggpw_XNW @ 2024-10-11 19:41:42

@yupeishan2012 是的（吧...

by YAOhc2012 @ 2024-10-11 19:42:06

@yupeishan2012 你只要改一下c[i]就行，没大问题