|
t;>1;
28 build(ll);build(rr);
29 sum[rt]=sum[rt<<1]+sum[rt<<1|1];
30 }
31 int query(int ql,int qr,int l,int r,int rt){
32 if(ql<=l&&r<=qr)
33 return sum[rt];
34 int mid=(l+r)>>1;
35 int ans=0;
36 if(ql<=mid) ans+=query(ql,qr,ll);
37 if(mid<qr) ans+=query(ql,qr,rr);
38 return ans;
39 }
40 void update(int pos,int l,int r,int rt){
41 if(l==r){
42 sum[rt]=1;
43 return ;
44 }
45 int mid=(l+r)>>1;
46 if(pos<=mid) update(pos,ll);
47 else update(pos,rr);
48 sum[rt]=sum[rt<<1]+sum[rt<<1|1];
49 }
50 int main(){
51 int n;
52 n=read();
53 for(int i=1;i<=n;i++){
54 a[i].w=read();
55 a[i].id=i;
56 }
57 sort(a+1,a+n+1);
58 int cnt=0;
59 b[a[1].id]=++cnt;
60 for(int i=2;i<=n;i++){
61 if(a[i-1].w!=a[i].w) b[a[i].id]=++cnt;
62 else b[a[i].id]=cnt;
63 }
64 build(1,n,1);
65 int ans=0;
66 for(int i=1;i<=n;i++){
67 ans+=query(b[i],n,1,n,1);
68 update(b[i],1,n,1);
69 }
70 printf("%d",ans);
71 return 0;
72 }
|