《双色球》

Li_mz__ @ 2022-11-04 21:26:43

#include <bits/stdc++.h>

using namespace std;
int main(){
    long long n,arr[214748394];
    long long ans = 0;
    scanf("%d",&n);
    for(long long i = 0;i < n;i++){
        scanf("%d",&arr[i]);
    }
    for(long long i = 0;i < n;i++){
        for(long long j = i + 1;j < n;j++){
            if(arr[i] > arr[j]){
                ans++;
            }
            else{
                ans += 0;
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

by unsigned_short_int @ 2022-11-04 21:29:00

应该不会 O(n^2) 过 50 万吧 by chen_zhe

by 淼淼 @ 2022-11-04 21:29:08

对于所有数据，n \leq 5 \times 10^5

by DJRicher @ 2022-11-04 21:29:47

请您先看下数据大小好吗？

by Li_mz__ @ 2022-11-04 21:30:12

emmm……

by Li_mz__ @ 2022-11-04 21:33:36

？？？？？？？

把long long改成int?

by DJRicher @ 2022-11-04 21:36:33

@Li_mz__ 25*10^{10}你确定能跑完？？？

by Li_mz__ @ 2022-11-04 21:37:41

@zzgwhk emmm……

这是个好问题！

所以我怎么改呢？

by 淼淼 @ 2022-11-04 21:38:48

@Li_mz__ 暴力解法过不了，必须用归并排序或树状数组等方法求

by Li_mz__ @ 2022-11-04 21:40:15

@淼淼 なるほど

我又刑了

by _Jonny_404 @ 2022-11-04 21:57:10

@Li_mz__ 这题我 O(n \log n)