TLE 25分求助！

卷王 @ 2022-08-18 18:56:52

#include<bits/stdc++.h> //哎，dev-c++好像不能正确排序啊！ 
using namespace std;
inline int read(); //快读 
#define maxn 500001 //定义数据范围 
int n,a[maxn],w[maxn*4]; //输入变量、输入的数组、权值线段树 
long long ans=0; //逆序对个数 
inline void init()
{
    static int tmp[maxn];
    for(int i=1;i<=n;i++) tmp[i]=a[i];
    sort(tmp+1,tmp+n+1);
    int *_end=unique(tmp+1,tmp+n+1);
    for(int i=1;i<=n;i++) a[i]=lower_bound(tmp+1,_end,a[i])-tmp;
}
inline int query(int u,int l,int r,int v)
{
    if(l>=r) return w[u];
    int mid=(l+r)>>1;
    if(mid<v) return query(u<<1|1,mid+1,r,v); //kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkssssssssssssssssssssssssssssssssssssssssssssssssssssssssssccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc000000000000000000000000000000000000000000000000000000000000000000033333333333333333333333333333333333333333333333333333666
    else return query(u<<1,l,mid,v)+query(u<<1|1,mid+1,r,v);
}
inline void update(int u,int l,int r,int v)
{
    w[u]++;
    if(l==r) return;
    int mid=(l+r)/2;
    if(mid>=v) update(u<<1,l,mid,v);
    else update(u<<1|1,mid+1,r,v);
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    init();
    for(int j=1;j<=n;j++)
    {
        ans+=query(1,1,n,a[j]+1);
        update(1,1,n,a[j]);
    }
    printf("%ld",ans);
    return 0;
}
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

by 卷王 @ 2022-08-18 18:58:11

@holdyhao_Genius 哎呀，对不起，我自己无聊打的注释您们大佬不要介意哈！

#include<bits/stdc++.h> 
using namespace std;
inline int read(); //快读 
#define maxn 500001 //定义数据范围 
int n,a[maxn],w[maxn*4]; //输入变量、输入的数组、权值线段树 
long long ans=0; //逆序对个数 
inline void init()
{
    static int tmp[maxn];
    for(int i=1;i<=n;i++) tmp[i]=a[i];
    sort(tmp+1,tmp+n+1);
    int *_end=unique(tmp+1,tmp+n+1);
    for(int i=1;i<=n;i++) a[i]=lower_bound(tmp+1,_end,a[i])-tmp;
}
inline int query(int u,int l,int r,int v)
{
    if(l>=r) return w[u];
    int mid=(l+r)>>1;
    if(mid<v) return query(u<<1|1,mid+1,r,v); 
    else return query(u<<1,l,mid,v)+query(u<<1|1,mid+1,r,v);
}
inline void update(int u,int l,int r,int v)
{
    w[u]++;
    if(l==r) return;
    int mid=(l+r)/2;
    if(mid>=v) update(u<<1,l,mid,v);
    else update(u<<1|1,mid+1,r,v);
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++) a[i]=read();
    init();
    for(int j=1;j<=n;j++)
    {
        ans+=query(1,1,n,a[j]+1);
        update(1,1,n,a[j]);
    }
    printf("%ld",ans);
    return 0;
}
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<1)+(x<<3)+(ch^48);
        ch=getchar();
    }
    return x*f;
}

by tommyfj @ 2022-08-18 19:03:08

@holdyhao_Genius 这题要用归并吧

by TianJunYuan_ @ 2022-08-18 19:11:28

还需要定义一个结构体吧…………

本蒟蒻若回答错误，望dalao们指点

by Eason2009 @ 2022-08-18 19:13:14

query那里，时间复杂度假了。

by Failure_Terminator @ 2022-08-18 19:20:33

@holdyhao_Genius tommyfj 正解

by 喵仔牛奶 @ 2022-08-18 19:20:39

您的时间复杂度是应该是 \mathcal{O}(n^2\log n)，无法通过 5\times10^5。

by 喵仔牛奶 @ 2022-08-18 19:21:22

@holdyhao_Genius 本题正解是归并/树状数组。

by 卷王 @ 2022-08-18 19:55:12

@喵仔牛奶 @Eason2009 @haimo @tommyfj

可是这是刚出来的《深入浅出-进阶篇》上的代码啊！

by Failure_Terminator @ 2022-08-18 19:57:08

@holdyhao_Genius 这……

建议归并，O(n logn)

by Failure_Terminator @ 2022-08-18 19:59:39

推荐一下这个：Link