1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <iostream>
#include <string>
#include <stdio.h>
#include <limits.h>
#include <memory.h>
using namespace std;
#define MAXN 100010
#define MIN(a,b) ((a)<(b)?(a):(b))
long long A[MAXN];
long long B[MAXN];
long long solve(int N) {
    long long ans = 0;
    for(int l=2;l<N*2;l*=2) {
        for(int st=0;st<N;st+=l) {
            int i = st;
            int edi = MIN(st+l/2,N);
            int j = st+l/2;
            int edj = MIN(st+l,N);
            int idx = st;
            while(i<edi && j<edj) {
                if(A[i] > A[j]) {
                    ans += (edi-i);
                    B[idx++] = A[j++];
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX