blackfrog @ 2019-04-09 14:07:01

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
long long  t[10000000],m[10000000],b[10000000],a[10000000];
long long  n,st;
long long ans;
long long lowbit(long long x){
    return x&-x;
}

void add(long long  x,long long  k){
    while(x<=n){
        t[x] += k;
        x+=lowbit(x);
    }   
}
long long sum(long long  x)
    {
        long long s=0;
        while(x!=0)
        {
            s+=t[x];
            x-=lowbit(x);
        }
        return s;
    }

int main(){
    cin>>n;
    for(long long i = 1;i<=n;i++){
        cin>>m[i];
        st+=m[i];
        a[m[i]] = i;
    }
    sort(m+1,m+n+1);
    for(long long i = 1;i<=n;i++){
        b[a[m[i]]] = n+1-i;

    }
    for(long long i = 1;i<=n;i++){
        add(b[i],1);
        ans+=sum(b[i]-1);
    }
    cout<<ans;
    return 0;
}

by 33028120040712wcl @ 2019-04-09 14:10:07

序列中每个数字不超过10^9

by 用户已注销 @ 2019-04-09 14:15:08

序列中每个数字不超过10^9

cin不会T飞吗??

by Kan_kiz @ 2019-04-09 14:16:34

cin>>(long long) 很危险啊QwQ

by Social_Zhao @ 2019-04-09 14:21:33

您还是写MergeSort吧

by blackfrog @ 2019-04-09 22:32:26

RE问题解决了，谢谢大家

现在又有WA问题了。。。 求助啊

#include<iostream>
#include<map>
#include<algorithm>
using namespace std;
long long  t[10000000];
long long  n,st;
long long ans;
struct str{
    long long ord,v;
}m[1000000];
long long lowbit(long long x){
    return x&-x;
}

void add(long long  x,long long  k){
    while(x<=n){
        t[x] += k;
        x+=lowbit(x);
    }   
}
long long sum(long long  x)
    {
        long long s=0;
        while(x!=0)
        {
            s+=t[x];
            x-=lowbit(x);
        }
        return s;
    }

bool cmp(struct str a, struct str b){
    return a.v>b.v;
}

int main(){
    cin>>n;
    for(long long i = 1;i<=n;i++){
        cin>>m[i].v;
        st+=m[i].v;
        m[i].ord = i;
    }
    sort(m+1,m+n+1,cmp);

    for(long long i = 1;i<=n;i++){
        add(m[i].ord,1);
        ans+=sum(m[i].ord-1);
    }
    cout<<ans;
    return 0;
}