'문제 풀이' '데이터 구조' 트 리 배열 3

for (int i = 1; i <= n; i ++) {    
	cin >> a[i].val;    
	a[i].id = i;
}
sort(a + 1, a + n + 1);           //       val      
for (int i = 1; i <= n; i ++)    
	b[a[i].id] = i;                    // a[i]         ,b[i]  a[i]   rank(  ) 

for (int i = 1; i <= n; i ++) {	
	scanf("%d",&num[i]);	
	lsh[i] = num[i];	//       
}
sort(lsh + 1, lsh + n + 1); //  ，unique      ，          ，           
//cnt           
cnt = unique(lsh + 1, lsh + n + 1) - lsh - 1; //unique                -       - 1
for (int i = 1; i <= n; i++)	
      num[i] = lower_bound(lsh + 1, lsh + cnt + 1, num[i]) - lsh;

#include 
#include 
using namespace std;

const int M = 1e3 + 5;
int a[M], dis[M], bit[M];
int n;

void Read() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i ++) {
		scanf("%d", &a[i]);
	}
}

void Discretetion() {
	for (int i = 1; i <= n; i ++) {
		dis[i] = a[i];
	}
	sort(dis + 1, dis + 1 + n);
	int len = unique(dis + 1, dis + 1 + n) - dis - 1;
	for (int i = 1; i <= n; i ++) {
		a[i] = lower_bound(dis + 1, dis + 1 + n, a[i]) - dis;
	}
}

int lowbit(int x) { return x & (- x); }

void update(int k) {
	for (int i = k; i <= n; i += lowbit(i)) {
		bit[i] ++;				//       ，      
	}
}

int Sum(int k) {
	int tot = 0;
	for (int i = k; i > 0; i -= lowbit(i)) {
		tot += bit[i];
	}
	return tot;
}

void work() {
	int ans = 0;
	for (int i = 1; i <= n; i ++) {
		update(a[i]);				//              ，       ，   
		ans += i - Sum(a[i]);				//  
	}
	printf("%d", ans);
}

int main() {
	Read();				//  
	Discretetion();				//   
	work();				//  
	return 0;
}