```cpp
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
const int mm=500000;
int n;
struct SABER{
int v,i;
}a[mm];
int S1(SABER x,SABER y){
if(x.v==y.v){return x.i<y.i;}
return x.v<y.v;}
int S2(SABER x,SABER y){
return x.i<y.i;}
int LO(int j){return -j&j;}
int tr[500000],ans;
using namespace std;
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){scanf("%d",&a[i].v);a[i].i=i;}
sort(a+1,a+n+1,S1);
for(int i=1;i<=n;i++)a[i].v=i;
sort(a+1,a+1+n,S2);
for(int i=n;i>=1;i--){
for(int j=a[i].v;j<=n;j+=LO(j))tr[j]+=1;
for(int j=a[i].v-1;j>0;j-=LO(j))ans+=tr[j];
}
cout<<ans;
return 0;
}
这样是30。。。
```
by s_a_b_e_r @ 2017-05-16 22:31:11
你的离散化写错了
万一有重叠怎么办
譬如 5 8 1 6 5 4 2
by 封癫 @ 2017-05-22 18:06:00
@s\_a\_b\_e\_r
by 封癫 @ 2017-05-22 18:06:17
@[s\_a\_b\_e\_r](/space/show?uid=24570) abc
by 封癫 @ 2017-05-22 18:06:46
@Tom10
by xgl0520 @ 2017-07-18 18:28:54
正确姿势
```cpp
#include <ctype.h>
#include <cstdio>
typedef long long LL;
const int MAXN=500010;
LL n,ans;
LL a[MAXN],c[MAXN];
inline void read(LL&x) {
int f=1;register char c=getchar();
for(x=0;!isdigit(c);c=='-'&&(f=-1),c=getchar());
for(;isdigit(c);x=x*10+c-48,c=getchar());
x=x*f;
}
inline void merge(int l,int mid,int r) {
int i=l,j=mid+1,k=l-1;
while(i<=mid&&j<=r) {
if(a[i]>a[j]) c[++k]=a[j],ans+=mid-i+1,++j;
else c[++k]=a[i],++i;
}
while(i<=mid) c[++k]=a[i],++i;
while(j<=r) c[++k]=a[j],++j;
for(int i=l;i<=r;++i) a[i]=c[i];
return;
}
void gb(int l,int r) {
if(l==r) return;
int mid=(l+r)>>1;
gb(l,mid);gb(mid+1,r);
merge(l,mid,r);
}
int hh() {
read(n);
for(int i=1;i<=n;++i) read(a[i]);
gb(1,n);
printf("%lld\n",ans);
return 0;
}
int sb=hh();
int main() {;}
```
by whistle998 @ 2017-08-19 21:33:43