_Aurore_ @ 2022-05-23 17:40:42
#include<bits/stdc++.h>
using namespace std;
long long n,tree[500010];
struct input{
long long val,num;
}a[500010];
bool cmp1(input x,input y){return x.val<y.val;}
bool cmp2(input x,input y){return x.num<y.num;}
long long lowbit(long long x){return x&(-x);}
inline long long read()
{
int x=0,f=1;char ch=getchar();
while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}
while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}
return x*f;
}
void discrete(){
sort(a+1,a+n+1,cmp1);
for(long long i=1;i<=n;i++) a[i].val=i;
sort(a+1,a+n+1,cmp2);
}
void add(long long x){
for(long long i=x;i<=n;i+=lowbit(i)) tree[i]++;
}
long long query(long long x){
long long ans=0;
for(long long i=x;i>0;i-=lowbit(i)) ans+=tree[i];
return ans;
}
int main(){
n=read();
for(long long i=1;i<=n;i++){
a[i].val=read();
a[i].num=i;
}
discrete();//离散化
long long ans=0;
for(long long i=1;i<=n;i++){
ans=ans+(i-query(a[i].val)-1);
add(a[i].val);
}
cout<<ans;
return 0;
}by ivyjiao @ 2022-05-23 17:44:46
@Eddy48 你快读挂了。
int x=0,f=1;char ch=getchar();by ivyjiao @ 2022-05-23 17:45:13
改成
long long x=0,f=1;char ch=getchar();by _Aurore_ @ 2022-05-23 18:03:49
谢谢
by tin_ingot @ 2022-05-23 18:09:19
@Eddy48 不用这么麻烦，快排就对了。
#include<bits/stdc++.h>
using namespace std;
long long a[500005],b[500005],ans;
void fun(int lf,int rt)
{
if(lf>=rt) return ;
int mid=(lf+rt)>>1;
fun(lf,mid);
fun(mid+1,rt);
int l=lf,r=mid+1,cnt=0;
while(l<=mid&&r<=rt)
{
if(a[l]<=a[r]) b[++cnt]=a[l++];
else ans+=mid-l+1,b[++cnt]=a[r++];
}
while(l<=mid) b[++cnt]=a[l++];
while(r<=rt) b[++cnt]=a[r++];
for(int i=lf;i<=rt;i++) a[i]=b[i-lf+1];
}
int main(){
long long n;
scanf("%lld",&n);
for(int i=1;i<=n;i++) scanf("%lld",a+i);
fun(1,n);
printf("%lld",ans);
return 0;
}by YBH2179 @ 2022-06-25 11:45:55
‘注意序列中可能有重复数字’ 这个位置会让你离散化出问题