COJ 0342 逆序对（一）

传送门：http://oj.cnuschool.org.cn/oj/home/problem.htm?problemID=312

试题描述：

给你一个大小为N的int数组A。请你统计有多少数对(Ai,Aj)满足i<j且Ai>Aj并输出。

输入：

第一行为N，表示数组A的大小。
第二行为N个数Ai，两两之间用一个空格分隔。

输出：

输出整数对的个数。

输入示例：

5
3 2 1 0 -1

输出示例：

其他说明：

1<=N<=100000
-10^9<=Ai<=10^9

题解：静态逆序对，从小到大往Fenwick里插入数，用sum统计有多少比它小的。

注意，记得去重！！！！

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 const int maxn=100000+10;
 7 int C[maxn],num[maxn],n,tmp[maxn];
 8 struct HASH{
 9     int v,id;
10     bool operator < (const HASH& ths) const{ 
11         return v>ths.v;
12     }
13 }A[maxn];
14 void update(int x,int v){
15     for(;x<=n;x+=x&-x)C[x]+=v;
16     return;
17 }
18 int sum(int x){
19     int ans=0;
20     for(;x;x-=x&-x)ans+=C[x];
21     return ans;
22 }
23 inline int read(){
24     int x=0,sig=1;char ch=getchar();
25     while(!isdigit(ch)){if(ch=='-') sig=-1;ch=getchar();}
26     while(isdigit(ch)) x=10*x+ch-'0',ch=getchar();
27     return x*=sig;
28 }
29 inline void write(long long x){
30     if(x==0){putchar('0');return;} if(x<0) putchar('-'),x=-x;
31     int len=0,buf[15]; while(x) buf[len++]=x%10,x/=10;
32     for(int i=len-1;i>=0;i--) putchar(buf[i]+'0');return;
33 }
34 void init(){
35     n=read();
36     for(int i=1;i<=n;i++)A[i].v=read(),A[i].id=i;
37     sort(A+1,A+1+n);
38     int cnt=1;
39     num[1]=1;
40     for(int i=2;i<=n;i++){
41         if(A[i-1].v!=A[i].v)num[i]=++cnt;
42         else num[i] = cnt;
43     }
44     for(int i=1;i<=n;i++) tmp[A[i].id]=num[i];
45     return;
46 }
47 long long ans;
48 void work(){
49     ans=0;
50     for(int i=1;i<=n;i++){
51         update(tmp[i],1);
52         ans+=sum(tmp[i]-1);
53     } return;
54 }
55 void print(){
56     write(ans);
57     return;
58 }
59 int main(){
60     init();work();print();return 0;
61 }