TIOJ 1080 . A.逆序數對

逆序數對:離散+zkw線段樹

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cstring>
#include<vector>
#include<utility>
#include<map>
#include<set>
#include<queue>
#include<cmath>
using namespace std;
typedef long long int int64;
int tree[800000];
int base;
void init(int n){
 base =  (1<<(int)(ceil(log2(n+4)))) - 1;
 for(int lx = 1;lx <= 2*base + 1;lx++)
  tree[lx] = 0;
 return;
}
void add(int n){
 for(int prc = base + 1 +n;prc;prc>>=1)
  tree[prc]++;
 return;
}
int query(int a, int b){
 if(b < a) return 0;
 int cnt = 0;
 a++, b++;
 for(a += base-1, b+= base+1;a^b^1;a>>=1, b>>= 1){
  if(~a&1) cnt +=tree[a^1];
  if(  b&1) cnt +=tree[b^1];
 }
 return cnt;
}
int arr[500000];
int main()
{
 int n;
 int cc = 0;
 while(1){
   cc++;
  scanf("%d", &n);
  if(n == 0) break;
  set<int> jizz; map<int, int> jizzmap;
  for(int lx = 0;lx < n;lx++){
   scanf("%d", arr+lx);
   jizz.insert(arr[lx]);
  }
  int jizzcnt = 1;
  for(set<int>::iterator it = jizz.begin();it != jizz.end();it++){
   jizzmap[*it] = jizzcnt++;
  }
  for(int lx =0;lx < n;lx++)
   arr[lx] = jizzmap[arr[lx]];
  init(n);
  int64 cnt = 0;
  for(int lx = n-1;lx>=0;lx--){
   cnt += (int64)query(1,arr[lx]-1);
   add(arr[lx]);
  }
  printf("Case #%d: %lld\n", cc, cnt);
 }
 return 0;
}