【线段树】求逆序对
2021-04-11 16:05:00 # ACM

普通线段树是预先处理出值域的范围。像二叉树一样建树，有时通过将所给序列离线离散化以减小普通线段树的值域。

当所给序列不允许离线而且值域比较大时，动态开点线段树可以 $O(nlogm)$ 维护线段树，$m$ 是值域，假象一开始有一颗 $[1,m]$的线段树，当然是不去建它的。

对于普通线段树都有修改操作，则如将 $a[x]$ 加上 $val$，$x$ 对应原数组下标，就去递归这颗 $[1,m]$ 的线段树直到下标 $x$，只有递归过程中碰到未建立的节点就新建节点。

例如求逆序对：

题链

一步步遍历所给序列 $a[x]$，将 $[1,m]$ 的线段树第 $x$ 位上加上 $1$，然后 $push_up$，每一步都求当前 $a[x]$ 前面有几个比 $a[x]$ 大的，相当于求线段树上 $[ a[x]+1,m ]$（$m$是值域）的和，递归求解就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
#include <bits/stdc++.h>
using namespace std;
#define MS 500009
#define ls rt<<1
#define rs rt<<1|1
#define LL long long 
#define MAXN 1000000009

int n,m;
int tot;
int root;
struct node{
	int l,r;
	LL sum;
}p[MS*40];
int a[MS];

void push_up(int rt){
	p[rt].sum = p[p[rt].l].sum + p[p[rt].r].sum;
}

void update(int &rt,int l,int r,int pos){
	if(!rt) rt = ++tot;
	if(l == r && l == pos){
		p[rt].sum++;
		return;
	}
	int m = l+r>>1;
	if(m >= pos) update(p[rt].l,l,m,pos);
	else update(p[rt].r,m+1,r,pos);
	push_up(rt);
}

LL get_sum(int L,int R,int l,int r,int rt){
	if(L <= l && r <= R){
		return p[rt].sum;
	}
	int m = l+r>>1;
	LL ans = 0;
	if(m >= L) ans += get_sum(L,R,l,m,p[rt].l);
	if(m <  R) ans += get_sum(L,R,m+1,r,p[rt].r);
	return ans;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n;
	LL ans = 0;
	for(int i=1;i<=n;i++){
		cin >> a[i];
		update(root,1,MAXN,a[i]);
		ans += get_sum(a[i]+1,MAXN,1,MAXN,1);
	}
	cout << ans << endl;
	

	return 0;
}
Prev
2021-04-11 16:05:00 # ACM
Next