为什么复杂度O（nlogn）会超时啊？

hellocccl @ 2024-01-15 19:13:49

#include <bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){//快读
    char ch=getchar();
    int x=0,f=1;
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return x*f;
}
void solve(){
    int n; cin>>n;
    vector <int> v(n);
    vector <int> x(n);
    for (int i=0; i<n; ++i){
        int a=read();
        v[i]= a;
        x[i]= a;
    }
    sort(x.begin(), x.end());
    ll ans = 0;
    for (int i=0; i<n; ++i){
        auto it = lower_bound(x.begin(), x.end(), v[i]);
        ans+= (it-x.begin());
        x.erase(it);
    }
    cout<<ans<<endl;
}
int main()
{

    int t=1;
    while(t--){
        solve();
    }
    return 0;
}

by CWzwz @ 2024-01-15 19:15:45

erase 是 O(N) 的

by elbissoPtImaerD @ 2024-01-15 19:17:20

vector.erase 是 O(n) 的。

by C6H6 @ 2024-01-15 19:45:26

@CWzwz 借这个帖子问一下，vector的erase到底是个什么神秘玩意，为什么有时候很快，大概根号的速度，有时候会变成线性。cppreference 上说实现是线性的，但为什么有时候会很快？

by timmyliao @ 2024-01-15 19:57:49

AC

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long LL;
const int MAX = 500005 ;
int n ;
LL a[MAX] ;
LL b[MAX] ;
LL ans = 0 ;
void merge_sort(int l ,int r ){
    if(l ==r )return ;
    LL mid = (l+r)/2 ;
    merge_sort(l,mid) ;
    merge_sort(mid+1,r) ;
    int i = l , k = l , j =mid +1 ;
    while(i<=mid && j<=r){
        if(a[i]<=a[j])
        b[k++] =a[i++];
        else{
            b[k++] =a[j++] ;
            ans+=mid-i+1 ;
        }
    }
    while(i<=mid){
        b[k++] =a[i++] ;
    }
    while(j<=r){
        b[k++] =a[j++];
    }
    for(int i = l; i<=r ; i++){
        a[i] = b[i] ;
    }
}
int main(){
    scanf("%d",&n);
    for(int i = 1 ; i<=n ; i++ ){
        scanf("%lld",&a[i]);
    }

    merge_sort(1,n) ;
    cout<<ans;
    return 0 ;
}

by CWzwz @ 2024-01-15 21:01:43

@C6H6 测了下，大概就是线性的吧。

by CWzwz @ 2024-01-15 21:03:37

erase 1e5 个数（从头 erase 到尾），用了 0.6s（学校老年机），可能是它在 O(n) 中常数特别小？

by C6H6 @ 2024-01-15 21:48:58

@CWzwz 所以为什么常数很小，有一些题可以n方过1e5

by C6H6 @ 2024-01-15 21:49:22

机房下课了，明天找找题