sandwich @ 2020-07-23 18:24:28
RT 代码如下
#include<bits/stdc++.h>
using namespace std;
const int maxn=5000001;
int c[maxn],d[maxn];
int n,m,i,j,k;
struct node{
long long x,y;
}a[500005];
int lowbit(int x)
{
return x&(-x);
}
bool cmp(node b,node c)
{
if(b.x==c.x) return b.y>c.y;
return b.x>c.x;
}
int add(int x)
{
while(x<=n)
{
c[x]++;
x+=lowbit(x);
}
}
int out(int x)
{
int ans=0;
while(x>0)
{
ans+=c[x];
x-=lowbit(x);
}
return ans;
}
int main()
{
int ans=0;
cin>>n;
for(i=1;i<=n;i++)
{
cin>>a[i].x;
a[i].y=i;
}
sort(a+1,a+n+1,cmp);
for(i=1;i<=n;i++)
{
add(a[i].y);
ans+=out(a[i].y-1);
}
cout<<ans;
return 0;
}
by sandwich @ 2020-07-23 18:25:04
树状数组!
by Retired_lvmao @ 2020-07-23 18:27:39
@sandwich
ans可能会爆int
by sandwich @ 2020-07-23 18:32:21
@lv_mao_da_lao 谢谢!