离散化+树状数组 30分 RE,求助

P1908 逆序对

F_Q_chicken @ 2024-02-21 09:48:23


#include<bits/stdc++.h>
#define M 5000005
#define lowbit(x) x&-x
using namespace std;
long long _,ans;
int jnjx[M],c[M],hym[M],xw[M],xw_;
void create()
{
    sort(hym+1,hym+1+_);
    for(int i=1;i<=_;i++)
    {
        if(i==1||hym[i]!=hym[i-1])
        xw[++xw_]=hym[i];   
    }   
    return;
} 
int qu(int x)
{
    return lower_bound(xw+1,xw+1+xw_,x)-xw;
}
void add(int id,int k)
{
    while(id  <=  _)
    {
        c[id]+=k;
        id+=lowbit(id); 
    }
    return;
}
void sum(int x)
{
    while(1  <=  x)
    {
        ans+=c[x];
        x-=lowbit(x);   
    }
    return;
}
int main()
{
    cin>>_;
    for(int i=1;i <= _;i++)
    cin>>jnjx[i],hym[i]=jnjx[i];
    create();
    for(int i=1;i<= _ ;i++)
    {
        jnjx[i]=qu(jnjx[i]);
    }
    for(int i=_;1 <= i;i--)
    {
        sum(jnjx[i]);
        add(jnjx[i],1);
    }
    cout<<ans;
    return 0;
}

by A_chicken_boy @ 2024-02-21 09:49:16

cin 改成 scanf


by A_chicken_boy @ 2024-02-21 09:50:18

sum(jnjx[i]-1)


|