Candycar @ 2021-11-26 19:03:06
树状数组求逆序对RE了0分，烦请各路巨佬帮忙检查一下，谢谢。
#include<bits/stdc++.h>
#define int long long
#define mem(a) memset(a,0,sizeof(a))
#define set(a,b) memset(a,b,sizeof(a))
using namespace std;
inline int in() //in()
{
int x = 0, f = 1;
char c = getchar();
while (!isdigit(c))
{
if (c == '-')
f =- 1;
c = getchar();
}
while (isdigit(c))
{
x = x * 10 + c - '0';
c = getchar();
}
return x * f;
}
int n;
int c[1000005];
int lowbit(int x)
{
return x & (-x);
}
int add(int x, int val)
{
while (x <= n)
{
c[x] += val;
x += lowbit(x);
}
}
int sum(int x)
{
int res = 0;
while (x > 0)
{
res += c[x];
x -= lowbit(x);
}
return res;
}
signed main()
{
// freopen("nxd.in", "r", stdout);
// freopen("nxd.out", "w", stdout);
cin >> n;
int a[n + 1];
for (int i = 1; i <= n; i++)
cin >> a[i];
int ans = 0;
for (int i = n; i >= 1; i--)
{
int j = a[i];
add(j, 1);
j = a[i] - 1;
ans += sum(j);
}
cout << ans << endl;
return 0;
}
by ex24012940 @ 2021-11-26 19:07:33
数据范围很大，需要离散化！
by Fuyuki @ 2021-11-26 19:08:45
是宽宽诶
by Y2y7m @ 2021-11-26 19:09:04
#include <bits/stdc++.h>
using namespace std;
int a[500010],b[500010],c[500010];
int n,m;
long long ans;
int lowbit(int x)
{
return x&(x^(x-1));
}
void change(int i,int d)
{
for(i;i<=n;i+=lowbit(i))
c[i]+=d;
}
int sum(int i)
{
int ans=0;
for(i;i>0;i-=lowbit(i))
ans+=c[i];
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]),b[i]=a[i];
sort(b+1,b+1+n);
m=unique(b+1,b+1+n)-b-1;
for(int i=1;i<=n;i++)
a[i]=lower_bound(b+1,b+1+n,a[i])-b;
for(int i=1;i<=n;i++)
{
change(a[i],1);
ans+=i-sum(a[i]);
}
printf("%lld",ans);
return 0;
}自行解决吧
by NaCly_Fish @ 2021-11-26 19:35:34
是 @Fuyuki 诶
by yangzd @ 2021-11-26 19:55:50
捕捉kk!
by user470883 @ 2021-11-27 06:30:33
哇！全是巨佬唉