排序

[P2824 HEOI2016/TJOI2016]排序 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意

​ 给你一个长度为$n$的排列，现在于这个序列进行$m$次局部排列，排列分为两种$0lr:$将$[l,r]$的数升序排列，$1lr$将$[l,r]$的数降序排列，最后询问$q$位置上的数是多少。

思路

• 动态开点权值线段树

介绍一下权值线段树：

​ 一般来说我们可以用线段树来维护一个数组的信息，每一个结点维护的数组的某个区间的信息。现在我们不维护某个数组了，我们维护一个连续的值域也可以理解为维护数组的下标，对于插入某个数，我们只需要给对应的值域的位置加一即可。

​ 有一个问题如果我们的值域过大的话例如到$1e9$了，不离散化显然我们是开不了这么大的空间的，但是一般给你的数的个数是在$1e5$左右的，而线段树是一个满二叉树，如果我们开$1e9$这么大的线段树的话，最终肯定会有很多没有用到的点，所以启示我们假定开了个这么大的线段树，每次用到的时候再去给他分配一个结点，由于每次单点修改只会访问$logn$个结点，因此只会开$mlogn$个结点，这样空间就可以保证了，这就是动态开点了

​ 这时线段树需要记录他左右儿子的位置了，我们并不需要在结构体里记录当前维护的哪个区间，只需要在函传参的时候维护即可

以查找某个区间的逆序对为例:

struct Node {
    int son[2]; // 左儿子的位置， 右儿子的位置
    int sum; // 当前区间有多少个数
}tr[N * 20];
#define ls(x) (tr[x].son[0])
#define rs(x) (tr[x].son[1])
1
2
3
4
5
6

对于建树，我们直接对值域插入结点即可，如果没出现过就给他开点

void insert(int u, int l, int r, int x) {
    if (l == r) {
        tr[u].sum ++;
        return ;
    }

    int mid = l + r >> 1;
    if (x <= mid) insert((ls(u) ? ls(u) : ls(u) = ++idx), l, mid, x);
    else insert((rs(u) ? rs(u) : rs(u) = ++idx), mid + 1, r, x);
    pushup(u);
}
1
2
3
4
5
6
7
8
9
10
11

对于查询某个区间有多少个数

int query(int u, int l, int r, int ll, int rr) {
    if (ll <= l && r <= rr) return tr[u].sum;    
    int mid = l + r >> 1;
    int res = 0;
    if (ll <= mid && tr[ls(u)].sum) res = query(ls(u), l, mid, ll, rr);
    if (rr > mid && tr[rs(u)].sum) res += query(rs(u), mid + 1, r, ll, rr);
    return res;
}
1
2
3
4
5
6
7
8

那么权值线段树还可以干什么呢？

​ 例如求给定序列的第$k$大数是什么，我们可以在树上二分，如果左边有$\ge k$个数就从左边找，如果没有的话就递归到右边找第$k-cn{t}_{左边有多少个数}$个数。

​ 回归到这个题，我们可一个把他抽象成一个一个的连续段，每个连续段都是有序的，一开始每个位置都是一个连续段，对于一个连续段里的有哪些数我们可以开一个权值线段树来维护这个连续段，也就是一个连续的段对应了一个权值线段树。

​ 如果我们要将$[l,r]$变成升序的，显然我们要将所有和$[l,r]$有交集的段找出来然后对这些段进行操作，这里我们可以用一个$set$来维护所有的段，然后每次二分查有交集的区间即可，即

typedef tuple<int, int, int, int> tup;// 开一个四元组分别表示 r, l, 根， 升序还是降序
set<tup> se;
1
2

这样每次我们搞好一个区间以后就可以直接将他插入$set$

void add(int l, int r, int rt, int opt) {
	se.insert(make_tuple(r, l, rt, opt)); //以r为第一关键字方便后面找交集线段
}
1
2
3

​ 我们用权值线段树来维护一段不仅方便查找该段的第几个数是什么，并且将任意两个权值线段树合并也是非常方便的，因为它们的结构是一样的，假设我们要将树$b$合并到$a$上则只需

int merge(int a, int b) { // 合并两个树并返回根
	if (!a || !b) return a | b; // 某个为空的时候直接重合
	ls(a) = merge(ls(a), ls(b)), rs(a) = merge(rs(a), rs(b)); // 不空的时候，直接将左右合并
	pushup(a);
	return a;
}
1
2
3
4
5
6

我们也可以将一个权值线段树分裂成两个，其实就是将某个区间的信息剪切给另一个线段树，这里的裂开只需要将原来的那个区间换个父节点就相当于裂开了

void split(int &a, int &b, int l, int r, int ll, int rr) { // 将区间[l,r]裂出[ll,rr]且以b为父节点
	if (!a || ll <= l && r <= rr) { // 如果到头了，或者完全包含了就裂开
		b = a, a = 0;
		return ;
	}

	int mid = l + r >> 1, L = 0, R = 0; // 搞两个左右儿子是否可以裂开
	if (ll <= mid) split(ls(a), L, l, mid, ll, rr);
	if (rr > mid) split(rs(a), R, mid + 1, r, ll, rr);
	if (L || R) { // 当前区间裂开了某一部分我们就，新建一个结点来维护这个区间
		b = ++idx;
		ls(b) = L, rs(b) = R;
		pushup(a), pushup(b);
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

还可以求出某个权值线段树从左到右第$k$大的数是什么

int queryL(int u, int l, int r, int k) {
	if (l == r) return l;
	int mid = l + r >> 1;
	if (tr[ls(u)].sum >= k) return queryL(ls(u), l, mid, k);
	return queryL(rs(u), mid + 1, r, k - tr[ls(u)].sum);
}
1
2
3
4
5
6

也可以求出从右到左的第$k$大的数是什么

int queryR(int u, int l, int r, int k) {
	if (l == r) return l;
	int mid = l + r >> 1;
	if (tr[rs(u)].sum >= k) return queryR(rs(u), mid + 1, r, k);
	return queryR(ls(u), l, mid, k - tr[rs(u)].sum);
}
1
2
3
4
5
6

上述两个操作均模拟二分即可

有了这些操作之后，我们以让$[l,r]$有序且新建一个根为$rt$为例，一定是有一些连续的段将$[l,r]$覆盖住，因此我们写个循环，每次找到当前最靠左覆盖了$[l,r]$的段，然后将它在$set$里移除，假设这个段维护的是$[L,R]$且根为$Rt$且$Opt=1升序，Opt=2降序$ 分为以下几种情况

1. $L\le lr\le R$，即包含住了我们要排序的区间，从实际意义出发，我们需要将这个段分成三份，即$[L,l-1],[l,r],[r+1,R]$，那么如何分呢，我们的$split$是将某个树的某个区间给分出去，因此我们实际上是要将$Rt$这个树的前$l-1-L+1$个数所在的区间（这里是我们线段树所维护的值域区间）给分出去，和后$R-r-1+1$个所在的区间给分出去，这里配合以下我们的$queryL,queryR$即可。

2. $l\le LR\le r$ 这个直接和我们当前的区间合并即可

3. $L\le lR<r$，切成两部分即可

4. $l\le Lr<R$ 切成两部分即可

   我们循环结束的条件就是处理完了$r$了，也就是查到的区间$[L,R]$的$L>r$或者我们某次处理的区间$R\ge r$的时候直接结束即可

对于查$q$这个位置的数是什么我们可以找到包含$q$的段，然后查这个段对应的第几个数的值即可。

Code

#include 
#define x first
#define y second
#define debug(x) cout<<#x<<":"<<x<<endl;
using namespace std;
typedef long double ld;
typedef long long LL;
typedef pair<int, int> PII;
typedef pair<double, double> PDD;
typedef unsigned long long ULL;
const int N = 1e5 + 10, M = 2 * N, INF = 0x3f3f3f3f, mod = 1e9 + 7;
const double eps = 1e-8, pi = acos(-1), inf = 1e20;
int dx[] = {-1, 0, 1, 0}, dy[] = {0, 1, 0, -1};
int h[N], e[M], ne[M], w[M], idx;
void add(int a, int b, int v = 0) {
	e[idx] = b, w[idx] = v, ne[idx] = h[a], h[a] = idx ++;
}
int n, m, k;
struct Node {
	int l, r, sum;
}tr[N * 100];
#define ls(x) (tr[x].l)
#define rs(x) (tr[x].r)

void pushup(int u) {
	tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;
}
void split(int &a, int &b, int l, int r, int ll, int rr) { // 将区间[l,r]裂出[ll,rr]且以b为父节点
	if (!a || ll <= l && r <= rr) {
		b = a, a = 0;
		return ;
	}

	int mid = l + r >> 1, L = 0, R = 0;
	if (ll <= mid) split(ls(a), L, l, mid, ll, rr);
	if (rr > mid) split(rs(a), R, mid + 1, r, ll, rr);
	if (L || R) {
		b = ++idx;
		ls(b) = L, rs(b) = R;
		pushup(a), pushup(b);
	}
}
int merge(int a, int b) { // 合并两个树
	if (!a || !b) return a | b;
	ls(a) = merge(ls(a), ls(b)), rs(a) = merge(rs(a), rs(b));
	pushup(a);
	return a;
}
void insert(int u, int l, int r, int pos) {
	if (l == r) {
		tr[u].sum = 1;
		return ;
	}
	int mid = l + r >> 1;
	if (pos <= mid) insert(ls(u) = ++idx, l, mid, pos);
	else insert(rs(u) = ++idx, mid + 1, r, pos);
	pushup(u);
}
int queryL(int u, int l, int r, int k) {
	if (l == r) return l;
	int mid = l + r >> 1;
	if (tr[ls(u)].sum >= k) return queryL(ls(u), l, mid, k);
	return queryL(rs(u), mid + 1, r, k - tr[ls(u)].sum);
}
int queryR(int u, int l, int r, int k) {
	if (l == r) return l;
	int mid = l + r >> 1;
	if (tr[rs(u)].sum >= k) return queryR(rs(u), mid + 1, r, k);
	return queryR(ls(u), l, mid, k - tr[rs(u)].sum);
}

typedef tuple<int, int, int, int> tup;
set<tup> se;
void add(int l, int r, int rt, int opt) {
	se.insert(make_tuple(r, l, rt, opt));
}
int main() {
	ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> m;
	for (int i = 1; i <= n; i ++) {
		int x; cin >> x;
		int rt = ++idx;
		insert(rt, 1, n, x); // 开点插入
		add(i, i, rt, 1);
	}
	
	while (m --) {
		int opt, l, r;
		cin >> opt >> l >> r;
		opt ++;
		int rt = 0;
		while (1) {
			auto it = se.lower_bound(make_tuple(l, 0, 0, 0));
			if (it == se.end() || get<1>(*it) > r) break;
			tup x = *it;
			se.erase(it);
			int L = get<1>(x), R = get<0>(x), Rt = get<2>(x), Opt = get<3>(x);
			if (l <= L && R <= r) rt = merge(rt, Rt);
			else if (L < l && r < R) {
				int lrt, rrt;
				if (Opt == 1) {
					split(Rt, lrt, 1, n, 1, queryL(Rt, 1, n, l - L));
					split(Rt, rrt, 1, n, queryR(Rt, 1, n, R - r), n);
				}
				else {
					split(Rt, lrt, 1, n, queryR(Rt, 1, n, l - L), n);
					split(Rt, rrt, 1, n, 1, queryL(Rt, 1, n, R - r));
				}
				add(L, l - 1, lrt, Opt), add(r + 1, R, rrt, Opt);
				rt = Rt;
				break;
			}
			else if(R <= r) {
				int lrt;
				if (Opt == 1) split(Rt, lrt, 1, n, 1, queryL(Rt, 1, n, l - L));
				else split(Rt, lrt, 1, n, queryR(Rt, 1, n, l - L), n);
				add(L, l - 1, lrt, Opt);
				rt = merge(rt, Rt);
			}
			else if (L <= r) {
				int rrt;
				if (Opt == 1) split(Rt, rrt, 1, n, queryR(Rt, 1, n, R - r), n);
				else split(Rt, rrt, 1, n, 1, queryL(Rt, 1, n, R - r));
				add(r + 1, R, rrt, Opt);
				rt = merge(rt, Rt);
				break;
			}
		} 
		add(l, r, rt, opt);
	}

	int pos; cin >> pos;
	auto it = se.lower_bound(make_tuple(pos, 0, 0, 0));
	tup x = *it;
	int L = get<1>(x), R = get<0>(x), Rt = get<2>(x), Opt = get<3>(x);

	if (Opt == 1) cout << queryL(Rt, 1, n, pos - L + 1) << '\n';
	else cout << queryR(Rt, 1, n, pos - L + 1) << '\n'; 
	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
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140