HDU1394：线段树优化求解逆序对问题

### 题目链接
[HDU 1394](http://acm.hdu.edu.cn/showproblem.php?pid=1394)

### 线段树的基本功能
- **update**: 单点增减
- **query**: 区间求和

### 分析
对于一个0到n-1的排列，如果将第一个数放到最后，那么对于这个数列，逆序数会减少a[i]，同时增加n-1-a[i]。因此，每次变化为res += n - a[i] - 1 - a[i]。

#### 代码实现（线段树）
```cpp
#include
#include
#include
#define LL long long
#define maxn 5555
#define lson l, m, rt <<1
#define rson m + 1, r, rt <<1 | 1
using namespace std;

int sum[maxn * 4];
int a[maxn];

void PushUp(int rt) {
sum[rt] = sum[rt <<1] + sum[rt <<1 | 1];
}

void build(int l, int r, int rt) {
sum[rt] = 0;
if (l == r)
return;
int m = (r + l) >> 1;
build(lson);
build(rson);
}

void update(int pos, int l, int r, int rt) {
if (l == r) {
sum[rt]++;
return;
}
int m = (r + l) >> 1;
if (pos <= m)
update(pos, lson);
else
update(pos, rson);
PushUp(rt);
}

int Query(int L, int R, int l, int r, int rt) {
if (L <= l && r <= R)
return sum[rt];
int m = (r + l) >> 1;
int res = 0;
if (L <= m)
res += Query(L, R, lson);
if (m res += Query(L, R, rson);
return res;
}

int main() {
int n;
while (scanf("%d", &n) > 0) {
build(0, n - 1, 1);
int sum = 0;
for (int i = 0; i scanf("%d", &a[i]);
sum += Query(a[i], n - 1, 0, n - 1, 1);
update(a[i], 0, n - 1, 1);
}
int ans = sum;
for (int i = 0; i sum += n - a[i] - a[i] - 1;
ans = min(ans, sum);
}
printf("%d\n", ans);
}
return 0;
}
```

### 树状数组求逆序对
树状数组在求解逆序对问题时更为简洁。以下是使用树状数组实现的代码示例：

```cpp
#include
#include
#include
#include
#define LL long long
#define maxn 5555
using namespace std;

int a[maxn], c[maxn];
int n;

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

int sum(int i) {
int res = 0;
while (i) {
res += c[i];
i -= lowbit(i);
}
return res;
}

void update(int i, int x) {
while (i <= n) {
c[i] += x;
i += lowbit(i);
}
}

int main() {
while (scanf("%d", &n) > 0) {
int res = 0;
memset(c, 0, sizeof(c));
for (int i = 1; i <= n; i++) {
scanf("%d", &a[i]);
a[i]++;
res += i - 1 - sum(a[i]); // 求1~a[i]区间的出现的数，再总（i-1）-sum(a[i])即可
update(a[i], 1); // 单点更新
}
int ans = res;
for (int i = 1; i <= n; i++) {
res += n - a[i] - (a[i] - 1);
ans = min(ans, res);
}
printf("%d\n", ans);
}
return 0;
}
```

### 总结
线段树和树状数组都是高效的求解逆序对问题的方法。根据具体需求选择合适的数据结构可以显著提高算法性能。