suyi1111 @ 2022-07-31 17:37:24

#include<bits/stdc++.h>
using namespace std;
int a[100001],n,sum=0; 
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
    }
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[i]>a[j]){
                sum++;
            }
        }
    }
    cout<<sum;
    return 0;
}

by suyi1111 @ 2022-07-31 17:41:58

尽管数据已加强但为什么会出现RE呢？？？

数据已加强出现TLE我能理解但是为什么RE呢

by yanxingyu0910 @ 2022-07-31 17:42:44

re是因为数组开小了吧，tle应该是你方法不对，正确方法我也不会建议看题解

by anonymous_letter @ 2022-07-31 17:47:37

@suyihang 对于所有数据，n \leq 5 \times 10^5

by suyi1111 @ 2022-07-31 17:49:41

原来RE是因为我少打了一个“0”

by najja @ 2022-07-31 18:10:23

#include<bits/stdc++.h>
using namespace std;
const int maxn=50005;
int n;
int aa[maxn];
int c[maxn];
struct nde
{
    int v;
    int order;
 }in[maxn];
int lawbit(int x)
{
    return x&-x;
}
int update(int t,int value)
{
    int i;
    for(i=t;i<=n;i+=lawbit(i))
        c[i]+=value;
}
int getsum(int x)
{
    int i;
    int temp=0;
    for(i=x;i>=1;i-=lawbit(i))
        temp+=c[i];
    return temp;
}
bool cmp(node a,node b)
{
    // if(a.v == b.v)
    //    return a.order < b.order;
    return a.v < b.v;
}
int main()
{
    int i,j;
    scanf("%d",n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&in[i].v);
        in[i].order=i;
    }
    sort(in+1,in+1+n,cmp);
    for(int i=1;i<=n;i++) aa[in[i].order]=i;
    memset(c,0,sizeof(c));
    long long ans=0;
    for(int i=1;i<=n;i++)
    {
        update(aa[i],1);
        ans+=i-getsum(aa[i]);
    }
    cout<<ans<<endl;
    return 0;
}

自己思考