2021.9.15 权值线段树_区间排序后 位置的变化 权值线段树

权值线段树

例题

最少逆序对

其实这一题作为模板题不太好，还是有一点点其他的思维，不过无伤大雅

概念

权值线段树就是线段树（确信）
至于和线段树有什么区别（没有区别）
那为什么会有单独的一个名字呢？
个人认为是有两个原因：
①权值线段树在数据结构领域解决问题有着较为广泛的应用，尤其是涉及到值域问题时。
②权值线段树的值域思维是一种新的思维，通常在数据结构题中出现，如果不是事先接触或者专门训练过可能难以自己领悟，所以作为一种新概念出现了

综上所述，权值线段树就是线段树，但是在解决问题的建模时通常在值域上进行，所以在思维方式上有一点不一样

基于值域的思维与基于序列的思维

BB了这么多，那么权值线段树到底应用在哪里？
首先讲讲思维，有一个很简单的例子：排序。
我们之前学什么排序呢？
冒泡、选择、快排、归并等
但是这些排序都有一个共同的特点，基于位置比较，说得更专业一点，基于序列。
但是有一种非常特殊的排序计数排序（桶排序的退化版），这种排序是基于值去做的。即利用f[i]表示i出现了几次，然后将下标按顺序遍历，输出对应个数的i即可，如f[5]等于3，表示有3个5，就输出5、5、5即可。
这种思维就是基于值域的思维，很明显，这样的排序区别于基于序列的排序，其复杂度取决于值域大小。
在数据结构题中，这种基于值域问题会经常出现，而且当值域很大时往往还要结合离散化操作。

我们以开头那道最经典的逆序对为例，我们一般有两种做法，第一是结合归并排序（当然暴力也可以）就是典型的基于序列的做法，而很多同学肯定知道这题还可以用树状数组去维护1~i中大于a[i]的个数来统计逆序对，这就是基于值域的思想。
那权值线段树其实就是基于值域的一棵线段树，具体做法只需将线段树维护的序列换成值域即可，比如L~R不再表示序列区间[L, R]，而是数值范围[L, R]之间的个数（当然也可以是其他信息），显然这也是符合区间加法 的。所以能够利用线段树维护。

值域这道题目，只需断环为链，然后每次右端加数，将多出来的逆序对累加，左端减数，将少去的逆序对减去，寻找过程中的最小值即可。

#include<cstdio>
#include<algorithm>
#define INF 2147483647
#define maxn 10039
using namespace std;
int n, a[maxn], b[maxn], f[maxn];
struct NODE{
	int l, r, m, v, lazy;
}node[maxn<<4];
void PushUp(int u){node[u].v = node[u<<1].v + node[u<<1|1].v;}
void PushDown(int u){}
void build(int u, int L, int R){
	if(L>=R){
		node[u] = (NODE){L, R, (L+R)>>1, 0, 0};
		return;
	}
	int m = (L+R)>>1;
	node[u] = (NODE){L, R, (L+R)>>1, 0, 0};
	build(u<<1, L, m);
	build(u<<1|1, m+1, R);
	PushUp(u);
}
void Update(int u, int L, int v){
	if(node[u].l>=node[u].r){
		node[u].v+=v;
		return;
	}
	if(L<=node[u].m)Update(u<<1, L, v);
	else Update(u<<1|1, L, v);
	PushUp(u);
}
int Quary(int u, int L, int R){
	if(L<=node[u].l&&R>=node[u].r)return node[u].v;
	int sum = 0;
	if(node[u].m>=L)sum = Quary(u<<1, L, R);
	if(node[u].m<R)sum += Quary(u<<1|1, L, R);
	return sum;
}
int main(){
	freopen("1.in", "r", stdin);
	while(~scanf("%d", &n)){
		for(int i = 1; i < n+1; i++){
			scanf("%d", a+i);
			a[i+n] = a[i];
			b[i+n] = b[i] = a[i];
		}
		sort(b+1, b+1+n);
		int e = unique(b+1, b+1+n)-b-1;
		for(int i = 1; i < n<<1; i++)a[i] = lower_bound(b+1, b+1+e, a[i])-b;  //至此是离散化，顺便断环为链
		build(1, 1, n);  //建树，这里的1到n是值，表示1到n中有几个数字
		int sum = 0, ans = INF;
		for(int i = 1; i < n; i++){
			Update(1, a[i], 1);
			sum += Quary(1, a[i]+1, n);
		}
		for(int i = n; i < n<<1; i++){
			if(i!=n){
				Update(1, a[i-n], -1);  //左端减
				sum -= Quary(1, 1, a[i-n]-1);
			}
			Update(1, a[i], 1);
			sum += Quary(1, a[i]+1, n);  //右端加
			ans = min(ans, sum);
		}
		printf("%d\n", ans);
	}
	return 0;
}
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
59
60
61
62
63
64
65
66
67
68