为什么全部RE?不应该啊,求助大佬帮忙看看,谢谢!

P1908 逆序对

ljx_gkx @ 2023-03-29 14:50:20

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;
const int N = 5e5 + 100;
typedef long long LL;
int n;
LL a[N];
LL tr[N];
LL cnt;

int lowbit(int x)
{
    return x & (-x);
}

void add (int pos, int val)
{
    for (int i=pos; i <= n; i += lowbit(i))
        tr[i] += val;
}

LL sum (int pos)
{
    LL res=0;
    for (int i=pos; i > 0; i -= lowbit(i))
        res += tr[i];
    return res;
}

int main()
{
    scanf("%d", &n);
    for (int i=1; i <= n; i ++)
    {
        scanf("%d", &a[i]);
    }
    //从右往左统计:每个数右边比它小的元素的个数!
    for (int i=n; i >= 1; i --)
    {
        int y = a[i];
        cnt += sum(y-1);
        add(y, 1);
    }
    printf("%d", cnt);
    return 0;
}

by ljx_gkx @ 2023-03-29 14:55:37

好像是因为我没有离散化。。。。


|