BZOJ2141排队：分块与树状数组详解

### 描述
孩子们围坐在一起，分享水果，场面温馨。然而，由于孩子们身高不同，排队时显得高低不齐。给定孩子们的身高序列，通过交换某些孩子的顺序，计算每次交换后的序列混乱度。

#### 输入
- 第一行是一个正整数n，表示孩子们的数量。
- 第二行包含n个由空格分隔的正整数h1, h2, ..., hn，依次表示初始队列中孩子们的身高。
- 第三行是一个正整数m，表示交换操作的次数。
- 以下m行每行包含两个正整数ai和bi，表示交换位置ai与位置bi的孩子。

#### 输出
- 输出文件共m行，第i行一个正整数表示交换操作i结束后，序列的混乱度。

#### 示例
**输入：**
```
3
130 150 140
2
2 3
1 3
```
**输出：**
```
1
0
3
```

**解释：**
- 初始时，(2,3)满足条件。
- 第一次交换后，序列为130 140 150，没有满足条件的对。
- 第二次交换后，序列为150 140 130，有(1,2)，(1,3)，(2,3)三对满足条件。

#### 数据范围
- 对于100%的数据，1≤m≤2*10^3，1≤n≤2*10^4，1≤hi≤10^9，ai≠bi，1≤ai, bi≤n。

### 解法
#### 逆序数
逆序数是指满足i a[j]的数对数量。直接暴力求解的时间复杂度为O(n^2)，而使用树状数组可以在O(n log n)的时间内求解。

#### 算法步骤
1. **离散化**：由于数值较大，先进行离散化处理。
2. **分块**：将数组分成若干块，每块建立一个树状数组。
3. **查询与更新**：对于每次交换操作，根据块的位置分别处理。
- 如果交换的两个位置在同一个块内，直接暴力计算贡献。
- 如果不在同一个块内，中间的完整块使用树状数组快速查询，两端的不完整块则暴力计算。
4. **复杂度分析**：整体复杂度为O(√n * log n)。

#### 代码实现
```cpp
#include
using namespace std;

struct Node {
int h, id;
Node() {}
Node(int h, int id) : h(h), id(id) {}
};

Node a[20010];
int v[20010], top, tree[150][20010];
int n, m, block;

bool cmp1(Node a, Node b) { return a.h bool cmp2(Node a, Node b) { return a.id
void update(int p, int x, int a) {
for (int i = x; i <= top; i += i & -i) {
tree[p][i] += a;
}
}

int query(int p, int x) {
int ans = 0;
for (int i = x; i; i -= i & -i) {
ans += tree[p][i];
}
return ans;
}

int main() {
scanf("%d", &n);
block = sqrt(n);
for (int i = 0; i scanf("%d", &a[i].h);
a[i].id = i;
}

sort(a, a + n, cmp1);
for (int i = 0; i if (a[i].h != v[top]) v[++top] = a[i].h;
a[i].h = top;
}

sort(a, a + n, cmp2);
int ans = 0;
for (int i = 0; i for (int j = 0; j <= i / block; j++) {
ans -= query(j, a[i].h);
}
ans += i;
update(i / block, a[i].h, 1);
}

printf("%d\n", ans);
scanf("%d", &m);
while (m--) {
int x, y;
scanf("%d%d", &x, &y);
x--, y--;
if (x > y) swap(x, y);
if (x / block == y / block) {
for (int i = x + 1; i ans += (a[i].h > a[x].h) + (a[i].h a[y].h);
}
} else {
for (int i = x / block + 1; i ans += (block - query(i, a[x].h)) + query(i, a[y].h - 1) - query(i, a[x].h - 1) - (block - query(i, a[y].h));
}
for (int i = x + 1; i <(x / block + 1) * block; i++) {
ans += (a[i].h > a[x].h) + (a[i].h a[y].h);
}
for (int i = y / block * block; i ans += (a[i].h > a[x].h) + (a[i].h a[y].h);
}
}
ans += (a[x].h a[y].h);
update(x / block, a[x].h, -1);
update(y / block, a[y].h, -1);
swap(a[x].h, a[y].h);
update(x / block, a[x].h, 1);
update(y / block, a[y].h, 1);
printf("%d\n", ans);
}
return 0;
}
```