为啥只有50!!……后10个点全wa

P1908 逆序对

sandwich @ 2020-07-23 18:24:28

RT 代码如下

#include<bits/stdc++.h>
using namespace std;
const int maxn=5000001;
int c[maxn],d[maxn];
int n,m,i,j,k;
struct node{
    long long x,y;
}a[500005];
int lowbit(int x)
{
    return x&(-x);
}
bool cmp(node b,node c)
{
    if(b.x==c.x) return b.y>c.y;
    return b.x>c.x;
}
int add(int x)
{
    while(x<=n)
    {
        c[x]++;
        x+=lowbit(x);
    }
}
int out(int x)
{
    int ans=0;
    while(x>0)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}
int main()
{
    int ans=0;
    cin>>n;
    for(i=1;i<=n;i++)
    {
        cin>>a[i].x;
        a[i].y=i;
    }
    sort(a+1,a+n+1,cmp);
    for(i=1;i<=n;i++)
    {
        add(a[i].y);
        ans+=out(a[i].y-1);
    }
    cout<<ans;
    return 0;
}

by sandwich @ 2020-07-23 18:25:04

树状数组!


by Retired_lvmao @ 2020-07-23 18:27:39

@sandwich

ans可能会爆int


by sandwich @ 2020-07-23 18:32:21

@lv_mao_da_lao 谢谢!


|