树状数组样例输出4，为什么？？

luqyou @ 2023-01-05 13:30:39

#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
#define int long long 
using namespace std;
int n,a[100001],b[100001],c[100001],ans;
bool cmp(int x,int y){
    if(a[x]==a[y]) return x<y;
    return a[x]<a[y];
}
void add(int x){
    for(int i=x;i<=n;i+=lowbit(i)){
        c[i]++;
    }
}
int search(int x){
    int sum=0;
    for(int i=x;i;i-=lowbit(i)){
        sum+=c[i]; 
    }
    return sum;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        b[i]=i;
    }
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++){
        add(b[i]);
        ans+=search(b[i]-1);
    }
    printf("%lld",ans);
    return 0;
}

by Usada_Pekora @ 2023-01-05 13:34:31

@luqyou 因为你在统计顺序对。

by lfxxx @ 2023-01-05 14:06:23

数据范围不是 5e5 吗？

by lfxxx @ 2023-01-05 14:14:10

#include<bits/stdc++.h>
#define lowbit(x) ((x)&(-(x)))
#define int long long 
using namespace std;
int n,a[500001],b[500001],c[500001],ans;
bool cmp(int x,int y){
    if(a[x]==a[y]) return x<y;
    return a[x]<a[y];
}
void add(int x){
    for(int i=x;i<=n;i+=lowbit(i)){
        c[i]++;
    }
}
int search(int x){
    int sum=0;
    for(int i=x;i;i-=lowbit(i)){
        sum+=c[i]; 
    }
    return sum;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        b[i]=i;
    }
    sort(b+1,b+n+1,cmp);
    for(int i=1;i<=n;i++){
        add(b[i]);
        ans+=search(b[i]-1);
    }
    printf("%lld",n*(n-1)/2-ans);
    return 0;
}

可过

by lfxxx @ 2023-01-05 14:14:43

@luqyou

by Fze_8 @ 2023-02-15 16:46:41

一楼正解，把所有数对总数减去你的答案就好了