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
好像是因为我没有离散化。。。。