题意：求逆序数
和POJ那题求逆序数的一样，不过这题离散化之后，要去一下重，然后要开到long long
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 13 typedef long long LL; 14 const int INF = (1<<30)-1; 15 const int mod=1000000007; 16 const int maxn=80005; 17 18 int a[maxn]; 19 int c[maxn];//树状数组 20 21 struct node{ 22 int x; 23 int id; 24 } p[maxn]; 25 26 int cmp(node n1,node n2){ 27 return n1.x < n2.x; 28 } 29 30 int lowbit(int x){ return x &(-x);} 31 32 __int64 sum(int x){ 33 __int64 ret=0; 34 while(x > 0){ 35 ret+=c[x];x-=lowbit(x); 36 } 37 return ret; 38 } 39 40 void add(int x,int d){ 41 while(x < maxn){ 42 c[x]+=d;x+=lowbit(x); 43 } 44 } 45 46 int main(){ 47 int n; 48 scanf("%d",&n); 49 for(int i=1;i<=n;i++) scanf("%d",&p[i].x),p[i].id=i; 50 sort(p+1,p+n+1,cmp); 51 52 for(int i=1,j=0;i<=n;i++){ 53 if(i==1 || p[i].x != p[i-1].x) j++; 54 a[p[i].id] = j; 55 } 56 57 memset(c,0,sizeof(c)); 58 __int64 ans=0; 59 for(int i=1;i <=n;i++ ) { 60 add(a[i],1); 61 ans += i - sum(a[i]); 62 } 63 printf("%I64d ",ans); 64 return 0; 65 }