萌新刚学树状数组，求助

L_S_ @ 2024-05-01 22:09:56

#include<bits/stdc++.h>
#define lowbit(x) x&-x
using namespace std;
const int N=500005;
int c[N],n;
struct l{
    int val,xh;
}a[N];
int ans;
void add(int x,int k)
{
    for(;x<=n;x+=lowbit(x)) c[x]+=k;
}
int query(int x)
{
    int sum=0;
    for(;x>0;x-=lowbit(x)) sum+=c[x];
    return sum;
}
bool cmp(l x,l y)
{
    return x.val>y.val;
}
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].val;
        a[i].xh=i;  
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        add(a[i].xh,1);
        ans+=query(a[i].xh-1);
    }
    cout<<ans;
    return 0;
}

by Cosine_Func @ 2024-05-01 22:15:27

@LS cmp要满足数值相等的编号小的在前

by L_S_ @ 2024-05-01 22:20:03

@XiaoJingCheng 不应该是序号大的在前面吗？

by L_S_ @ 2024-05-01 22:21:40

AC代码

#include<bits/stdc++.h>
#define lowbit(x) x&-x
#define int long long
using namespace std;
const int N=500005;
int c[N],n;
struct l{
    int val,xh;
}a[N];
int ans;
void add(int x,int k)
{
    for(;x<=n;x+=lowbit(x)) c[x]+=k;
}
int query(int x)
{
    int sum=0;
    for(;x>0;x-=lowbit(x)) sum+=c[x];
    return sum;
}
bool cmp(l x,l y)
{
    if(x.val==y.val) return x.xh>y.xh;
    return x.val>y.val;
}
signed main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i].val;
        a[i].xh=i;  
    }
    sort(a+1,a+n+1,cmp);
    for(int i=1;i<=n;i++)
    {
        add(a[i].xh,1);
        ans+=query(a[i].xh-1);
    }
    cout<<ans;
    return 0;
}

by L_S_ @ 2024-05-01 22:22:11

@XiaoJingCheng 但是过了，谢谢！

by Cosine_Func @ 2024-05-01 22:32:19

@LS 笔误

by L_S_ @ 2024-05-01 22:51:22

@XiaoJingCheng ok

by _H17_ @ 2024-05-02 08:51:57

@LS 我虽然会树状数组，但是不会树状数组求逆序对（）（）（），但是会二维super BIT