# 11258: 【原1258】圣诞树2

### 题目描述

author: JC 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1258

## Description

Dunphy一家制作了很多圣诞树，他们把这些树排成一排。他们发现这些数的高度参差不齐，他们现在希望知道这一排树的“不和谐度”。“不和谐度”指的是一共有多少对树使排在前面的树高于排在后面的树。

## Sample Input

``````5
5 2 7 2 10
``````

## Sample Output

``````3
``````

## BugenZhao's solution

``````//
// Created by BugenZhao on 2019/5/16.
//

#ifndef SBL_BMERGESORT_H
#define SBL_BMERGESORT_H

template<typename Item>
class BMergeSort {
public:
static long long ans;

private:
static bool less(Item v, Item w) {
return v < w;
}

static void doSort(Item *a, int lo, int hi, Item *aux) {
if (hi <= lo) return;
int mid = lo + (hi - lo - 1) / 2;
doSort(a, lo, mid, aux);
doSort(a, mid + 1, hi, aux);
merge(a, lo, mid, hi, aux);
}

static void merge(Item *a, int lo, int mid, int hi, Item *aux) {
for (int i = lo; i <= hi; i++) {
aux[i] = a[i];
}
int i = lo, j = mid + 1;
for (int k = lo; k <= hi; k++) {
if (i > mid) a[k] = aux[j++];
else if (j > hi) a[k] = aux[i++];
// caution: <=
else if (!less(aux[j], aux[i])) a[k] = aux[i++];
else a[k] = aux[j++], ans += mid - i + 1;
}
}

public:
static void sort(Item *a, int n) {
sort(a, 0, n - 1);
}

static void sort(Item *a, int lo, int hi) {
Item *aux = new Item[hi - lo + 1];
doSort(a, lo, hi, aux);
delete[] aux;
}
};

template<typename Item>
long long BMergeSort<Item>::ans = 0;

#endif //SBL_BMERGESORT_H

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;

int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k;
cin >> k;
auto a = new int[k];
for (int i = 0; i < k; ++i) {
cin >> a[i];
}
BMergeSort<int>::sort(a, k);
cout << BMergeSort<int>::ans << endl;
delete[] a;
return 0;
}
``````

## ligongzzz's solution

``````#include "iostream"
#include "cstdio"
#include "cstring"
#include "cmath"
using namespace std;

class node {
public:
int val = 0;
int left = 0, right = 0;
};

int val_data[100009] = { 0 };
node smt[400009];

void build_tree(int l, int r, int root) {
smt[root].left = l;
smt[root].right = r;
if (l == r - 1) {
smt[root].val = val_data[l];
return;
}

int mid = (l + r) >> 1;
build_tree(l, mid, root * 2);
build_tree(mid, r, root * 2 + 1);

smt[root].val = smt[root * 2].val + smt[root * 2 + 1].val;
}

int query(int l, int r, int root) {
if (l <= smt[root].left && smt[root].right <= r) {
return smt[root].val;
}

auto mid = (smt[root].left + smt[root].right) >> 1;
int ans = 0;
if (l < mid) {
ans += query(l, r, root * 2);
}
if (r > mid) {
ans += query(l, r, root * 2 + 1);
}
return ans;
}

void update(int val,int pos, int root) {
if (smt[root].right - smt[root].left == 1) {
smt[root].val += val;
return;
}

auto mid = (smt[root].left + smt[root].right) >> 1;
if (pos < mid) {
update(val, pos, root * 2);
}
else {
update(val, pos, root * 2 + 1);
}
smt[root].val = smt[root * 2].val + smt[root * 2 + 1].val;
}

int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int n;
cin >> n;

build_tree(0, 100009, 1);

long long cnt = 0;
for (int i = 0; i < n; ++i) {
cin >> val_data[i];

update(1, val_data[i], 1);
cnt += (long long)query(val_data[i] + 1, 100009, 1);
}

cout << cnt;

return 0;
}
``````

## Neight99's solution

``````#include <iostream>

using namespace std;

long long sum = 0, trees[100100], newTrees[100100];
int n;

void cal(int, int);

int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);

int n;

cin >> n;
for (int i = 0; i < n; i++) {
cin >> trees[i];
}

cal(0, n - 1);

cout << sum;

return 0;
}

void cal(int l, int r) {
int mid = (l + r) / 2;
int i, j, tmp;

if (r > l) {
cal(l, mid);
cal(mid + 1, r);
tmp = l;

for (i = l, j = mid + 1; i <= mid && j <= r;) {
if (trees[i] > trees[j]) {
newTrees[tmp++] = trees[j++];
sum += mid - i + 1;
} else {
newTrees[tmp++] = trees[i++];
}
}
if (i <= mid) {
for (; i <= mid;) {
newTrees[tmp++] = trees[i++];
}
}

if (j <= r) {
for (; j <= r;) {
newTrees[tmp++] = trees[j++];
}
}

for (i = l; i <= r; i++) {
trees[i] = newTrees[i];
}
}
}
``````

## skyzh's solution

``````//
// Created by 3t on 2019/5/16.
//

#include <iostream>

using namespace std;

static int MERGE_TMP[200000];

long long ans = 0;

void merge(int *x, int mid, int N) {
int i = 0, j = mid;
int k = 0;
while (i < mid && j < N) {
int _x = x[i];
int _y = x[j];
if (_x <= _y) {
MERGE_TMP[k++] = _x;
i++;
} else {
ans += mid - i;
MERGE_TMP[k++] = _y;
j++;
}
}
while (i < mid) {
MERGE_TMP[k++] = x[i++];
}
while (j < N) {
MERGE_TMP[k++] = x[j++];
}
for (int i = 0; i < k; i++) {
x[i] = MERGE_TMP[i];
}
}

void merge_sort(int *x, int N) {
if (N == 1) return;
if (N == 2) {
if (x[0] > x[1]) {
++ans;
swap(x[0], x[1]);
}
return;
}
int mid = N / 2;
merge_sort(x, mid);
merge_sort(x + mid, N - mid);
merge(x, mid, N);
}

int X[100000];
int main() {
int N;
scanf("%d", &N);
for (int i = 0; i < N; i++) {
scanf("%d", &X[i]);
}
merge_sort(X, N);
cout << ans << endl;
return 0;
}
``````

## yyong119's solution

``````#include <cstdio>
using namespace std;
const int MAX_N = 100010;
long long ans;
int n;
int a[MAX_N];

void merge(int l, int r) {

int mid = (l + r) >> 1, i = l, j = mid + 1, k = l;
int tmp[MAX_N];
while (i <= mid && j <= r) {
if (a[i] <= a[j]) tmp[k++] = a[i++];
else {
ans += mid - i + 1;
tmp[k++] = a[j++];
}
}
while (i <= mid) tmp[k++] = a[i++];
while (j <= r) tmp[k++] = a[j++];
for (int i = l; i <= r; ++i) a[i] = tmp[i];
}

void mergesort(int l, int r) {

if (l == r) return;
int mid = (l + r) >> 1;
mergesort(l, mid);
mergesort(mid + 1, r);
merge(l, r);
}

int main() {

// ios::sync_with_stdio(false);
// cin >> n;
scanf("%d", &n);
for (int i = 1; i <= n; ++i) //cin >> a[i];
scanf("%d", &a[i]);
mergesort(1, n);
// cout << ans << endl;
printf("%lld\n", ans);
return 0;
}
``````