RT
为什么这段代码
#include<bits/stdc++.h>
using namespace std;
int n,m,c[500005],a[500005],b[500005];
long long ans;
void add(int x,int y)
{
for(;x<=n;x+=x&-x)c[x]+=y;
}
int ask(int x)
{
int ans=0;
for(;x;x-=x&-x)ans+=c[x];
return ans;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)scanf("%d",&a[i]),a[i]++;
for(int i=n;i>=1;i--)
{
ans+=ask(a[i]-1);
add(a[i],1);
}
printf("%lld\n",ans);
}
会显示运行错误,而当加了离散化后,像这样
#include<bits/stdc++.h>
using namespace std;
int n,m,c[500005],a[500005],b[500005];
long long ans;
int lsh(int x)
{
return lower_bound(b+1,b+m+1,x)-b;
}
void add(int x,int y)
{
for(;x<=n;x+=x&-x)c[x]+=y;
}
int ask(int x)
{
int ans=0;
for(;x;x-=x&-x)ans+=c[x];
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+n+1);
m=unique(b+1,b+n+1)-(b+1);
for(int i=1;i<=n;i++)a[i]=lsh(a[i]);
//system("pause");
for(int i=n;i>=1;i--)
{
ans+=ask(a[i]-1);
add(a[i],1);
}
printf("%lld\n",ans);
}
就可以AC了呢?
萌新初学,求大佬解惑。