我按深进里的代码思路自己打了一遍,结果只有1~5AC?????
#include<bits/stdc++.h> //哎,dev-c++好像不能正确排序啊!
using namespace std;
inline int read(); //快读
#define maxn 500001 //定义数据范围
int n,a[maxn],w[maxn*4]; //输入变量、输入的数组、权值线段树
long long ans=0; //逆序对个数
inline void init()
{
static int tmp[maxn];
for(int i=1;i<=n;i++) tmp[i]=a[i];
sort(tmp+1,tmp+n+1);
int *_end=unique(tmp+1,tmp+n+1);
for(int i=1;i<=n;i++) a[i]=lower_bound(tmp+1,_end,a[i])-tmp;
}
inline int query(int u,int l,int r,int v)
{
if(l>=r) return w[u];
int mid=(l+r)>>1;
if(mid<v) return query(u<<1|1,mid+1,r,v); //kkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkssssssssssssssssssssssssssssssssssssssssssssssssssssssssssccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccccc000000000000000000000000000000000000000000000000000000000000000000033333333333333333333333333333333333333333333333333333666
else return query(u<<1,l,mid,v)+query(u<<1|1,mid+1,r,v);
}
inline void update(int u,int l,int r,int v)
{
w[u]++;
if(l==r) return;
int mid=(l+r)/2;
if(mid>=v) update(u<<1,l,mid,v);
else update(u<<1|1,mid+1,r,v);
}
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read();
init();
for(int j=1;j<=n;j++)
{
ans+=query(1,1,n,a[j]+1);
update(1,1,n,a[j]);
}
printf("%ld",ans);
return 0;
}
inline int 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<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}