25pts其余全TTTTTTT了

JiuZhE66666 @ 2023-10-18 19:12:48

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[500005]={0};
ll ans=0;
ll n;
void one(ll l,ll mid,ll r)
{
    ll i1=l,i2=mid+1;
    ll len=l;
    ll b[500005]={0};
    while(i1<=mid&&i2<=r)
    {
        if(a[i1]>a[i2])
        {
            ans+=mid-i1+1;
            b[len++]=a[i2++];
        }
        else b[len++]=a[i1++];
    }
    while(i1<=mid)b[len++]=a[i1++];
    while(i2<=r)b[len++]=a[i2++];
    for(ll i=l;i<=r;i++)a[i]=b[i];
}
void divs(ll l,ll r)
{
    if(l>=r)return ;
    ll mid=l+(r-l)/2;
    divs(l,mid);
    divs(mid+1,r);
    one(l,mid,r);
}

int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
    divs(1,n);
    printf("%lld",ans);
    return 0;
}

by N_z_ @ 2023-10-18 19:18:18

考察这个 one 函数，会被调用 O(n) 次，每次会初始化一个 O(n) 的数组。

by suyi1111 @ 2023-10-18 20:57:09

@JiuZhE66666

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll a[500005]={0},b[500005];//b不需要初始化，每次初始化会增加时间复杂度
ll ans=0;
ll n;
void one(ll l,ll mid,ll r)
{
    ll i1=l,i2=mid+1;
    ll len=l;
    while(i1<=mid&&i2<=r)
    {
        if(a[i1]>a[i2])
        {
            ans+=mid-i1+1;
            b[len++]=a[i2++];
        }
        else b[len++]=a[i1++];
    }
    while(i1<=mid)b[len++]=a[i1++];
    while(i2<=r)b[len++]=a[i2++];
    for(ll i=l;i<=r;i++)a[i]=b[i];
}
void divs(ll l,ll r)
{
    if(l>=r)return ;
    ll mid=l+(r-l)/2;
    divs(l,mid);
    divs(mid+1,r);
    one(l,mid,r);
}

int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++)scanf("%lld",&a[i]);
    divs(1,n);
    printf("%lld",ans);
    return 0;
}

by JiuZhE66666 @ 2023-10-20 14:09:41

@suyihang 非常感谢！

by JiuZhE66666 @ 2023-10-20 14:10:09

@Nz 感谢！懂了