蒟蒻求助

codeducker @ 2021-07-12 23:14:23

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n,m;
int c[500005];
struct cpp{
    int w,id;
}a[500005];

inline int lowbit(int x){return x&(-x);}
inline void update(int x,int val){//x是位置val是改变量
    for( ; x<=n ; x+=lowbit(x) ) c[x]+=val;
}
inline ll query( int x ){
    ll sum=0;
    for( ; x>0 ; x-=lowbit(x) ) sum+=c[x];
    return sum;
}

bool cmp1( cpp &a,cpp &b ){
    return a.w<b.w;
}
bool cmp2( cpp &a,cpp &b ){
    return a.id<b.id;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].w;
        a[i].id=i;
    }

    sort(a+1,a+n+1,cmp1);//离散化
    for(int i=1,num=0;i<=n;i++){
        if(a[i].w>a[i-1].w){
            a[i].w=++num;
        }else{
            a[i].w=num;
        }
    }

    sort( a+1,a+n+1,cmp2 );
    ll k,ans=0;
    for(ll i=1;i<=n;i++){
        update(a[i].w,1);
        k=i-query(a[i].w);
        ans+=k;
    }

    cout<<ans;
    return 0;
}

by AlbrecRoon @ 2021-07-13 07:01:43

@codeducker 改了一下

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;

int n,m;
int c[500005];
struct cpp{
    int w,hw,id;
}a[500005];

inline int lowbit(int x){return x&(-x);}
inline void update(int x,int val){//x???val????
    for( ; x<=n ; x+=lowbit(x) ) c[x]+=val;
}
inline ll query( int x ){
    ll sum=0;
    for( ; x>0 ; x-=lowbit(x) ) sum+=c[x];
    return sum;
}

bool cmp1( cpp &a,cpp &b ){
    return a.w<b.w;
}
bool cmp2( cpp &a,cpp &b ){
    return a.id<b.id;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].w;
        a[i].id=i;
    }

    sort(a+1,a+n+1,cmp1);//???
    for(int i=1,num=0;i<=n;i++){
        if(a[i].w>a[i-1].w){
            a[i].hw=++num;
        }else{
            a[i].hw=num;
        }
    }

    sort( a+1,a+n+1,cmp2 );
    ll k,ans=0;
    for(ll i=1;i<=n;i++){
        update(a[i].hw,1);
        k=i-query(a[i].hw);
        ans+=k;
    }

    cout<<ans;
    return 0;
}

by codeducker @ 2021-07-13 09:26:29

@AlbrecRoon

感谢大佬