树状数组又WA又T求助

P1908 逆序对

ChthollyMeow @ 2020-05-26 22:37:15

大概就是用树状数组
关于卡常：
register和inline全加了
O2开了
快读开了
然鹅仍然有几个点TLE，有时候rp高会变成WA（
代码如下：

#include<bits/stdc++.h>
#define RE register
using namespace std;
int a[500005],b[500005],c[500005],n,anss=0;
inline void modify(RE int x){
    for(RE int i=x;i<=n;i+=i&(-i)){
        c[i]++;
    }
}
inline int find(RE int x){
    RE int ans=0;
    for(RE int i=x;i;i-=i&(-i)){
        ans+=c[i];
    }
    return ans;
}
bool cmp(int p,int q){
    return a[p]<a[q];
}
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;
}
int main(){
    n=read();
    for(RE int i=1;i<=n;i++){
        a[i]=read();
        b[i]=i;//离散化
    }
    sort(b+1,b+n+1,cmp);
    for(RE int i=1;i<=n;i++){
        modify(b[i]);
        anss+=i-find(b[i]-1);
    }
    printf("%d",anss);
    return 0;
}

by ChthollyMeow @ 2020-05-26 22:38:00

啊，这代码现在不会TLE了，不过全WA

by Acestar @ 2020-05-26 23:14:51

@_珂朵莉

1.cmp 写错了，应该是 a_p>a_q 而且数据已加强需要判重，所以这样

bool cmp(int p,int q){
    if(a[p]==a[q]) return p>q;
    return a[p]>a[q];
}

2.数据加强，要开 long\ long

by Acestar @ 2020-05-26 23:15:13

#include<bits/stdc++.h>
#define RE register
#define int long long 
using namespace std;
int a[500005],b[500005],c[500005],n,anss=0;
inline void modify(RE int x){
    for(RE int i=x;i<=n;i+=(i&(-i))){
        c[i]++;
    }
}
inline int find(RE int x){
    RE int ans=0;
    for(RE int i=x;i;i-=(i&(-i))){
        ans+=c[i];
    }
    return ans;
}
bool cmp(int p,int q){
    if(a[p]==a[q]) return p>q;
    return a[p]>a[q];
}
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;
}
signed main(){
    n=read();
    for(RE int i=1;i<=n;i++){
        a[i]=read();
        b[i]=i;//离散化
    }
    sort(b+1,b+n+1,cmp);
    for(RE int i=1;i<=n;i++){
        modify(b[i]);
        anss+=find(b[i]-1);
    }
    printf("%lld",anss);
    return 0;
}