[Luogu] p1908 reverse sequence pair

Title address ：

https://www.luogu.com.cn/problem/P1908

Title Description ：
Cat and cat TOM And mice JERRY Recently, it's a contest again , But it's all adults, after all , They don't like to play chasing games anymore , Now they like to play Statistics . lately ,TOM Old cat looked up a human class called “ Reverse alignment ” Things that are , It's defined like this ： For a given sequence of positive integers , A reverse order pair is in a sequence $a_i>a_j$ And $i<j$ That's right . Knowing the concept , They compete who first counts the number of reverse pairs in a given sequence of positive integers . Note that there may be duplicate numbers in the sequence .

Input format ：
first line , a number $n$, It means that there is $n$ Number .
The second line $n$ Number , Represents a given sequence . Each number in the sequence does not exceed $10^9$.

Output format ：
The number of reverse pairs in the output sequence .

Data range ：
about $25\%$ The data of ,$n\le 2500$
about $50\%$ The data of ,$n\le 4\times 10^4$.
For all the data ,$n\le 5\times 10^5$

You can use tree arrays directly . Traverse from back to front , Encountered a number $x$ Go to the tree array to find the front of the array it maintains $x-1$ The number and （ That is, how many numbers are smaller than the current number ）, After that, I will $x$ Add $1$. Count the answers while traversing . The code is as follows ：

#include <iostream>
#include <algorithm>
#include <unordered_map>
#define lowbit(x) (x & -x)
using namespace std;

const int N = 5e5 + 10;
int n, m, a[N], b[N];
int tr[N];
unordered_map<int, int> mp;

void add(int k, int x) {
    
  for (; k <= n; k += lowbit(k)) tr[k] += x;
}

int sum(int k) {
    
  int res = 0;
  for (; k; k -= lowbit(k)) res += tr[k];
  return res;
}

int main() {
    
  scanf("%d", &n);
  for (int i = 0; i < n; i++) {
    
    scanf("%d", &a[i]);
    b[i] = a[i];
  }  

  //  Do orderly discretization 
  sort(b, b + n);
  m = unique(b, b + n) - b;
  for (int i = 0; i < m; i++) mp[b[i]] = i + 1;

  long res = 0;
  for (int i = n - 1; i >= 0; i--) {
    
    int x = mp[a[i]];
    res += sum(x - 1);
    add(x, 1);
  }

  printf("%ld\n", res);
}

Time complexity $O(n\log n)$, Space $O(n)$.