归并$O(nlogn)$
① 因为要记录每一个身高的具体逆序数数量,所以要用结构体将信息打包
② 如果$j$先到达$r$,那么$i$和$(mid, r)$之间的数形成$r - mid$个逆序数
// 数据范围1e5
// 时间复杂度O(nlogn)
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5+10;
typedef long long ll;
int n;
struct student
{
int w, cntl, cntr;
void operator=(const struct student &another)
{
w = another.w;
cntl = another.cntl;
cntr = another.cntr;
}
}st[N], tmp[N];
void count(int l, int r)
{
if (l >= r) return;
int mid = l + r >> 1;
count(l, mid), count(mid + 1, r);
int k = 0, i = l, j = mid + 1;
while (i <= mid && j <= r)
{
if (st[i].w <= st[j].w)
{
st[i].cntr += (j - mid - 1);
tmp[k ++] = st[i ++];
}
else
{
st[j].cntl += (mid - i + 1);
tmp[k ++] = st[j ++];
}
}
while (i <= mid)
{
st[i].cntl += r - mid;
tmp[k ++] = st[i ++];
}
while (j <= r) tmp[k ++] = st[j ++];
for (int i = l, j = 0; i <= r; i ++, j ++) st[i] = tmp[j];
}
int main()
{
scanf("%d", &n);
for (int i = 1; i <= n; i ++) scanf("%d", &st[i].w);
// 计算两侧逆序对个数
count(1, n);
ll ans = 0;
for (int i = 1; i <= n; i ++) ans += (ll)(st[i].cntl + st[i].cntr) * (st[i].cntl + st[i].cntr + 1) / 2;
cout << ans;
return 0;
}
树状数组$O(nlogn)$
逐个将小朋友的身高作为序号往线段树中$+1$,每次在加入当前小朋友之前查询前面有多少个比当前小朋友大的身高,即当前小朋友前面的逆序数数量。然后再逆序来做一遍,即当前小朋友后面的逆序对数量。
线段树求逆序数思路更加清晰
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int a[N], tr[N], cntl[N], cntr[N], w[N];
int lowbit(int x)
{
return x & -x;
}
void add(int x, int t)
{
a[x] += t;
for (int i = x; i < N; i += lowbit(i)) tr[i] += t;
}
int query(int t)
{
int ans = 0;
for (int i = t; i > 0; i -= lowbit(i)) ans += tr[i];
return ans;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 1; i <= n; i ++) scanf("%d", &w[i]), w[i] ++;
for (int i = 1; i <= n; i ++)
{
cntl[i] += query(N) - query(w[i]);
add(w[i], 1);
}
memset(tr, 0, sizeof tr);
for (int i = 1; i <= n; i ++)
{
cntr[n - i + 1] += query(w[n - i + 1] - 1);
add(w[n - i + 1], 1);
}
//for (int i = 1; i <= n; i ++) printf("%d %d\n", cntl[i], cntr[i]);
long long ans = 0;
for (int i = 1; i <= n; i ++) ans += (long long)(cntl[i] + cntr[i]) * (cntl[i] + cntr[i] + 1) / 2;
printf("%lld", ans);
return 0;
}