AcWing
1215. 小朋友排队
总共要交换的次数是数组中逆序对的数量，对于某一个小朋友来说，他要被移动的次数，就是以他为逆序对左端点或右端点的次数之和。
求逆序对，可以使用归并排序的方式。对于每次归并之前，求跨越左右区间的所有逆序对数量，并更新小朋友被移动的次数。当所有的归并结束后，每个小朋友被移动的次数就确定了。
归并排序，要注意使用pair<int, int>存储身高和序号，避免排序时打乱顺序：
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 100010;
typedef pair<int, int> PII;
#define hh first
#define id second
PII h[N], tmp[N];
int cnt[N];
typedef long long LL;
void mergesort(int l, int r){
if(l >= r) return;
int mid = l + r >> 1;
mergesort(l, mid);
mergesort(mid + 1, r);
int pl = l, pr = mid + 1, pt;
// 对于右边区间的每一个点，找到左边区间大于它的点的数量
while(pr <= r){
while(pl <= mid && h[pl].hh <= h[pr].hh) pl++;
cnt[h[pr].id] += (mid - pl + 1);
pr++;
}
pl = l, pr = mid + 1;
// 对于左边区间的每一个点，找到右边区间小于它的点的数量
while(pl <= mid){
while(pr <= r && h[pl].hh > h[pr].hh) pr++;
cnt[h[pl].id] += (pr - (mid + 1));
pl++;
}
pl = l, pr = mid + 1, pt = 1;
while(pl <= mid && pr <= r){
if(h[pl].hh <= h[pr].hh) tmp[pt++] = h[pl++];
else tmp[pt++] = h[pr++];
}
while(pl <= mid) tmp[pt++] = h[pl++];
while(pr <= r) tmp[pt++] = h[pr++];
for(int i = l, j = 1; i <= r; i++, j++) h[i] = tmp[j];
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i++){
h[i].id = i;
cin >> h[i].hh;
}
mergesort(1, n);
LL sum = 0;
for(int i = 1; i <= n; i++) sum += (LL)cnt[i] * (cnt[i] + 1) / 2;
cout << sum;
return 0;
}
树状数组用于逆序对，分别正序和逆序动态建立树状数组，存的是截至当前的一系列数值(身高)出现的次数，在建立的过程中，更新某一边的逆序对的数量(即某个小朋友被向左或向右移动的次数)，这个过程实质上是区间查询。注意边界，将a[i]全都加1：
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 100010, M = 1000010;
int a[N], tr[M], cnt[N];
typedef long long LL;
int lowbit(int x){return x & -x;}
void update(int x, int v){
for(int i = x; i <= M - 1; i += lowbit(i)) tr[i] += v;
}
int query(int x){
int res = 0;
for(int i = x; i >= 1; i -= lowbit(i)) res += tr[i];
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
a[i] ++;
}
for(int i = 1; i <= n; i ++){
cnt[i] += query(M - 1) - query(a[i]);
update(a[i], 1);
}
memset(tr, 0, sizeof tr);
for(int i = n; i >= 1; i --){
cnt[i] += query(a[i] - 1);
update(a[i], 1);
}
LL res = 0;
for(int i = 1; i <= n; i ++) res += (LL)cnt[i] * (cnt[i] + 1) / 2;
cout << res;
return 0;
}
线段树也是类似的，但是要注意边界情况：
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 100010, M = 1000010;
int a[N], sum[4 * M], cnt[N];
typedef long long LL;
void push(int u){
sum[u] = sum[2*u] + sum[2*u + 1];
}
void update(int l, int r, int u, int x, int v){
if(l == r){
sum[u] += v;
return;
}
int mid = l + r >> 1;
if(x <= mid) update(l, mid, 2*u, x, v);
else update(mid + 1, r, 2*u + 1, x, v);
push(u);
}
int query(int L, int R, int l, int r, int u){
if(L <= l && r <= R) return sum[u];
int res = 0;
int mid = l + r >> 1;
if(L <= mid) res += query(L, R, l, mid, 2*u);
if(R > mid) res += query(L, R, mid + 1, r, 2*u + 1);
return res;
}
int main(){
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for(int i = 1; i <= n; i ++){
cin >> a[i];
a[i] ++;
}
for(int i = 1; i <= n; i ++){
cnt[i] += query(a[i] + 1, M - 1, 1, M - 1, 1);
update(1, M - 1, 1, a[i], 1);
}
memset(sum, 0, sizeof sum);
for(int i = n; i >= 1; i--){
if(a[i] != 1) cnt[i] += query(1, a[i] - 1, 1, M - 1, 1);
update(1, M - 1, 1, a[i], 1);
}
LL res = 0;
for(int i = 1; i <= n; i ++) res += (LL)cnt[i] * (cnt[i] + 1) / 2;
cout << res;
return 0;
}