洛谷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的箭头