一种逆序对新解法
洛谷P1908 https://www.luogu.com.cn/problem/P1908
逆序对常规解法归并排序或者离散化+树状数组（线段树），网上教程很多这里暂且不表，AVL树和红黑树也可以解决，但是略麻烦（比较小众），笔者在这里提供一种新解法——跳表（暂时在网上没看到有发的）。
跳表
https://oi-wiki.org/ds/skiplist/
具体可以在这里了解，简略来讲就是可以进行二分查找插入等操作的单调链表，只不过这个链表的结点多了很多层（有点像树了，但实际不是），便于操作。
类似这种（网上随便扒的图）
思路来源
其实这种思路与树状数组解法或者AVL解法类似，倒序遍历+找比当前数字小的数字总数，问题在于如何找变得不同了。
本蒟蒻在看到题目的第一刻便想到了奶牛那道题 洛谷P2947（虽然有很多奶牛的题），题目解法是倒序遍历+单调栈，对于这道题，倒序遍历维护一个单调栈会漏很多结果，所以本蒟蒻将单调栈换成了单调数组，二分维护，想介于vector中insert的速度快的特点，强行过一下，可惜不行。
void solve() {
vector<int> b;
ans = 0;
b.push_back(a[n]);
for (int i = n - 1; i >= 1; i--) {
auto it = upper_bound(b.begin(), b.end(), a[i], greater<int>());
int pos = b.end() - it;
ans += pos;
b.insert(it, a[i]);
}
cout << ans<< endl;
}
于是，便想到维护单调链表，查了一下（），果然可以，便有了这个跳表解法。（AVL树也想到了，但是本蒟蒻实力有限，没做出来）。
本题解法
对于本道题来讲，构造一个普通的跳表并不难，难点在于如何计算到末尾的长度，即上面代码的第7 8行，本蒟蒻将此节点为开始，到指向结点为重点，这段左闭右开的长度分别记录下来，最后从最大的高度向后遍历，依旧是logn的时间复杂度。
参考此图两个结点相同高度之间的长度记录下来就好了。结点结构体如下：
typedef struct skiplist {
int size;//结点高度
int data;//结点数据
vector<skiplist *> point;//指向下一个指针
vector<int> lr;//以当前节点为起始，相同高度下一节点为结束，左闭右开长度
skiplist(int s, int d) {//初始化
size = s;
data = d;
point.resize(size + 1);
lr.resize(size + 1);
}
} SL;
常规跳表高度为随机值，为保持稳定，这里先排序，然后取中位数，其高度比左右最高高度高一，保证每步都是二分进行，避免不稳定性。
typedef struct aa {
int pos;
int data;
int size;
bool operator <(const aa &a) {
return data < a.data;
}
} A;
void setsize(int l, int r, int s) {
if (l > r)
return;
int mid = (l + r) >> 1;
b[a[mid].pos].size = s;
setsize(l, mid - 1, s - 1);
setsize(mid + 1, r, s - 1);
}
于是setsize(1, n + 1, Log[n] + 1);便能初始化所有结点高度。
那么如何更新一个结点的高度呢，新加入一个节点，我们从最高的高度开始遍历，找到结点所在的区间，使区间长度加一，这便是此高度下包含区间总长度。下面分为两种情况，第一种高度大于新加入结点的高度，继续向下进行就好了。第二种，高度小于等于新加入结点高度，那么我们就要把这个总长度分为两个部分，一个是l到当前节点，一个是当前节点到r，其中一个计算出来，另一个自然而然就出来了。那么如何计算其中一个呢，我们这里计算左边的长度，在遍历高度时，我们用ss数组和st数组储存，当前高度 i 时，左端点为 st[i] ,st[i] 在当前高度总共经过位移为 ss[i] 。
新加入结点17，从高度4开始遍历，在高度为3时，区间分成两个部分，暂时不计算长度，遍历到高度为1时，st位移了2个单位，故 ss[1]=2，然后对ss数组求其前缀和，上一层的前缀和+1代表st到当前节点这个左区间的长度，左区间长度有了，右区间自然就出来了。
最后求当前结点之后的总长度只需要从最大高度向后遍历加总（贪心），最后总结果减一（不包含当前结点）。
那么，代码便完成了，下面展示总代码（Onlogn）（二分查找加更新Ologn，寻找结果Ologn）
#include <bits/stdc++.h>
#define lowbit(x) ((x) & -(x))
#define rep(i,l,r) for(register int i=l;i<=r;i++)
using namespace std;
const int N = 5e5 + 5;
const int INF = 0x3fffffff;
const double eps = 1e-6;
typedef long long ll;
const int modp = 1e6 + 37;
typedef struct skiplist {
int size;
int data;
vector<skiplist *> point;
vector<int> lr;
skiplist(int s, int d) {
size = s;
data = d;
point.resize(size + 1);
lr.resize(size + 1);
}
} SL;
typedef struct aa {
int pos;
int data;
int size;
bool operator <(const aa &a) {
return data < a.data;
}
} A;
int n;
ll ans;//注意结果爆int
A a[N];
A b[N];
int Log[N];
void init() {//浅浅手写log2一下
Log[0] = -1;
rep(i, 1, N) Log[i] = Log[i >> 1] + 1;
}
void setsize(int l, int r, int s) {//找中位数，方便稳定二分，随机高度也可以（没有瞧不起快排）
if (l > r)
return;
int mid = (l + r) >> 1;
b[a[mid].pos].size = s;
setsize(l, mid - 1, s - 1);
setsize(mid + 1, r, s - 1);
}
void solve() {
ans = 0;
sort(a + 1, a + n + 1);
setsize(1, n + 1, Log[n] + 1);
SL *first = new SL(Log[n] + 1, INF);
rep(i, 1, first->size) first->point[i] = NULL, first->lr[i] = 1;
for (int i = n; i >= 1; i--) {//从最高高度遍历，毕竟只有向后的指针
SL *p = new SL(b[i].size, b[i].data);
rep(i, 1, p->size) p->lr[i] = 0, p->point[i] = NULL;
SL *l = first;
int ss[p->size + 1] = {0};
SL *st[p->size + 1];//两个记录位移，方便分区间长度的数组
for (int i = first->size; i >= 1; i--) {
while (l->point[i] != NULL && l->point[i]->data >= p->data) {//位移，且避免重复数字
if (p->size >= i)
ss[i] += l->lr[i];//记录位移长度
l = l->point[i];
}
l->lr[i]++;//总长度加一
if (p->size >= i)
st[i] = l;//当前左节点
if (p->size >= i) {
p->point[i] = l->point[i];
l->point[i] = p;//加入新节点
}
}
rep(i, 1, p->size) ss[i] += ss[i - 1];//计算前缀和
rep(i, 1, p->size) {
int x = ss[i - 1] + 1;//当前结点长度也占1，其实ss[0]=1也可以
p->lr[i] = st[i]->lr[i] - x;//先计算右区间长度
st[i]->lr[i] = x;//左区间长度
}
while (p != NULL) {//计算结果
ans += p->lr[p->size];
p = p->point[p->size];
}
ans--;//去除当前节点
}
cout << ans << endl;
}
int main() {
//ios::sync_with_stdio(0), cout.tie(0), cin.tie(0);
init();
if (~scanf("%d", &n)) {
rep(i, 1, n) {
scanf("%d", &a[i].data);
a[i].pos = i;
b[i].data = a[i].data;
b[i].pos = a[i].pos;
}
solve();
}
return 0;
}
总结：跳表是一个非常好用的数据结构，插入删除或者进行区间运算（RMQ之类的）都有相当高的性能，相较于二叉堆，能干的事情多了很多，加上长度之后按下标索引链表值效率也从On提高到Ologn，至于缺点包括空间复杂度高，写法麻烦，链表的惯性麻烦等等，而且只允许数据单调，在维护单调数组时AVL等算法不能进行下去的话，跳表或许能给你思路。
修正：两个图中结点9有个长度为1的箭头
