Ultra quicksort reverse sequence pair

The question ： The main idea of the title is to help you give some (n individual ) Disordered number , Let you find the number of times the bubble sort needs to exchange numbers （n<=500000）

Ideas ： Reverse order number , Tree array . because 0 ≤ a[i] ≤ 999,999,999, So you can't do it directly with a tree array , because n<500,000, And the property we need is the size relationship between any two numbers , So it can be discretized here . I sort the sequence of numbers , Then find the number of their array subscripts in reverse order , This inverse number is equal to the inverse number of the original sequence . Answer needs __int64, Pay attention to this .

discretization ：

Find the right words in reverse order , We just need to find out how many numbers are smaller than a certain number . So just use the tree array to query [1,x-1] It's OK how many numbers there are in this interval .
First of all, because the number is very large , Then it must be discretized . So use a structure to save val( It's worth it ),id( The original position ). Then sort , Then we can get the transformed value of each number after discretization .

First, let's look at a sequence 6 1 2 7 3 4 8 5, The reverse order number of this sequence is 5+3+1=9. Bubble method can directly enumerate the number in reverse order , But the time complexity is too high O(n^2). The principle of bubble sort is to enumerate every array , Then find out how many numbers after this number are smaller than this number , Less than its inverse ordinal number +1. Think about it , If we don't enumerate all the numbers after this number , But directly get the number less than this number , Then the efficiency will be greatly improved .
All in all N Number , How to judge the second i+1 How many numbers between the number and the last number are less than the number i How about the number ？ Suppose there is an interval [1,N], Just judge the interval [i+1,N] How many of them are less than the number of i Number . If we initialize the total interval to 0, And then put the i The number that has appeared before the number is set as... In the corresponding interval 1, So the problem turns into [i+1,N] Summation of values . Think again , Section [1,i] Value + Section [i+1,N] Value = Section [1,N] Value (i Marked as 1), So interval [i+1,N] The sum of the values equals N-[1,i] Value ！ Because there are N Number , Either smaller than it or smaller than it ( Big or equal to ).
Now the problem has been transformed into an interval problem , Enumerate each number , Then query the sum of the interval values in front of this number ,i-[1,i] Both inverse ordinal numbers .

#include <cstdio>
#include <algorithm>
#include <cstring>
typedef long long ll;
using namespace std;
const int N = 500005;
struct Node {
    
	ll val;
	int id;
	bool operator < (const Node& w) const {
    			
		return val < w.val;
	}
} no[N];
int n, c[N], w[N];
void update(int x, int d) {
    
	for (int i = x; i <= n; i += i & (-i)) c[i] += d;
} 
int query(int x) {
    
	int ans = 0;
	for (int i = x; i > 0; i -= i & (-i)) ans += c[i];	
	return ans;
}
int main() {
    
	while (scanf("%d", &n), n) {
    
		memset(c, 0, sizeof(c));
		for (int i = 1; i <= n; i++) {
    
			scanf("%d", &no[i].val);
			no[i].id = i; // The original position  
		}
		sort(no + 1, no + 1 + n);
		// Update current w Value 
		for (int i = 1; i <= n; i++) {
    
			// Values are sorted   And from 1--n
			w[no[i].id] = i; // Then it turns into 1-n Some number in  no[i].id Is the original position  
		} 
		ll ans = 0; // Save answers  
		for (int i = n; i >= 1; i--) {
    
			// Look for a smaller number   How many 
			ans += query(w[i] - 1);
			update(w[i], 1); 
		}
		printf("%lld\n", ans);
	}
	return 0;
}

Segment tree and merge