TLE 25分求助!

P1908 逆序对

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

我按深进里的代码思路自己打了一遍,结果只有1~5AC?????

#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 Eason2009 @ 2022-08-18 20:02:19

@holdyhao_Genius 确实是query那里寄了,帮您改了一下query函数,自己对照一下罢

#include<bits/stdc++.h> 
#define int long long
using namespace std;
inline int read(); //快读 
#define maxn 500001 //定义数据范围 
int n,a[maxn],w[maxn*4]; //输入变量、输入的数组、权值线段树 
int 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 ql,int qr)
{
    if(r<ql||l>qr||l>r) return 0;
    if(l>=ql&&r<=qr) return w[u];
    int mid=(l+r)>>1;
    return query(u<<1,l,mid,ql,qr)+query(u<<1|1,mid+1,r,ql,qr);
}
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);
}
signed 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,n);
        update(1,1,n,a[j]);
    }
    printf("%lld",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 Eason2009 @ 2022-08-18 20:03:20

@holdyhao_Genius 线段树区间询问我的建议是不要用其他奇奇怪怪的写法,就用我的这种。


by 卷王 @ 2022-08-18 20:05:13

@Eason2009 嗯,我用了一个效率很快的方法:https://www.luogu.com.cn/record/84264506


上一页 |