线段树计算逆序数
本题要点：
1、本题中n个数，恰好是 0 ~ n - 1，不需要离散化，而且没有任意两个数相同的。
2、 先初始化树， 所有节点的sum 赋值为0。 然后每次新加入 一个数 a[i]， 先查询 区间 [a[i] + 1, n + 1]
这些数出现的总次数。 意味着，查询比 a[i] 先加入的，并且比 a[i] 大的数的总数。 这些数与 a[i] 构成逆序数。
然后，执行更新操作， update(1, a[i])， 表示 a[i] 出现的次数加1.
3、 求出序列 a[1], a[2], …, a[n] 的逆序数后， 假设这个序列的逆序数是 ans1.
本题要求 求出以 a[k]（1 <= k <= n） 开始的连续n个数 的序列中，最小的逆序数。
现在 计算 a[2], …, a[n], a[1] 的逆序数。 这相当于， 在 a[1], a[2], …, a[n] 的基础上，把 a[1] 放到的末尾。
新增的逆序数 add1 ： a[1] 后面比 a[1] 大的数， n - a[1]
减少的逆序数 sub1 : a[1] 后面比 a[1] 小的数， n - a[1].
这样 a[2], …, a[n], a[1] 的逆序数 是 ans2 = ans1 - sub1 + add1; 以此类推，
ans3 = ans2 - sub2 + add2;
ans4 = ans3 - sub3 + add3;
…
在这些数，取最小值即可。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MaxN = 5010;
int n;
int a[MaxN];struct segTree
{
int l, r;int sum; // sum 表示当前节点 p 所代表的区间 [l, r] 范围内， l, l + 1, l + 2, ..., r 这些数，出现的总数
}tree[MaxN * 4];void build(int p, int l, int r)
{
tree[p].l = l, tree[p].r = r;if(l == r){
tree[p].sum = 0;return;}tree[p].sum = 0;int mid = (l + r) / 2;build(2 * p, l, mid);build(2 * p + 1, mid + 1, r);
}int query(int p, int l, int r)
{
if(l <= tree[p].l && r >= tree[p].r){
return tree[p].sum;}int mid = (tree[p].l + tree[p].r) / 2;int val = 0;if(l <= mid)val += query(p * 2, l, r);if(r > mid)val += query(p * 2 + 1, l, r);return val;
}void update(int p, int x)
{
if(tree[p].l == tree[p].r){
tree[p].sum++;return;}int mid = (tree[p].l + tree[p].r) / 2;if(x <= mid){
update(p * 2, x); }else{
update(p * 2 + 1, x);}tree[p].sum++;
}int main()
{
while(scanf("%d", &n) != EOF){
for(int i = 1; i <= n; ++i){
scanf("%d", &a[i]);++a[i];}build(1, 1, n + 1);int ans = 0;for(int i = 1; i <= n; ++i){
ans += query(1, a[i] + 1, n + 1);update(1, a[i]);}int res = ans;for(int i = 1; i < n; ++i){
ans = ans - (a[i] - 1) + n - a[i];res = min(res, ans);}printf("%d\n", res);}return 0;
}/* 10 1 3 6 9 0 8 5 7 4 2 *//* 16 */