hdu 4417 Super Mario 二分答案+划分树

缘起

区间topK问题我们已经使用了 分块（【1】）、线（归）段（并）树（【2】）、主席树（【3】）予以解决.

事实上, 区间topk问题其实还有一种专门的数据结构来对付它, 就是划分树. 遂来学习它. hdu 4417 Super Mario

分析

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
求【l，r】区间内<=h的数的个数。

【输入】
多样例
第一行是样例数. 对每个样例, 给出两个整数n和m, 1 <= n <=10^5, 1 <= m <= 10^5
n是数组的长度, m是询问的个数. 数组元素范围是[0, 1e9]
然后m行是询问三元组 l r h
0 <= L <= R < n, 0 <= H <= 1000000000

【输出】
看样例

【样例输入】
1
10 10
0 5 2 7 5 4 3 8 7 7 
2 8 6
3 5 0
1 3 1
1 9 4
0 1 0
3 5 5
5 5 1
4 6 3
1 5 7
5 7 3

【样例输出】
Case 1:
4
0
0
3
1
2
0
1
5
1

【限制】
1s 32768KB

裸的区间topK问题. 本文研究一下划分树这种数据结构

ps: 划分树貌似除了区间topK问题也没有其他用武之地了~ 囧

通过【2】的学习, 如果说归并树模拟的是归并排序的过程的话(归并树=线段树+归并排序),那么划分树就是在模拟快速排序的过程(划分树=线段树+快速排序), 即归并树每层节点其实就是归并排序的中间结果，而划分树每层节点其实就是快速排序的中间结果。

而且划分树的常数比归并树的常数小得多. 所以在区间topK问题上, 划分树的性能远优于归并树.

一图胜千言

上图是序列 a[8] = {4, 5, 2, 8, 7, 6, 1, 3} 的划分树. 首先sort(a,a+8)得到{1,2,3,4,5,6,7,8}（即上图第一行的数字）, 目的是能每次快排的时候选出刚好中间的数作为pivot, 这样每次快排都是完美快排~ 所以划分树的建树复杂度是O(nlogn)的, 而不会受快排最坏N^2复杂度的影响.

因为本题数据规模是10w, 而 2^20=1048576>10w, 所以本题的划分树不会超过20层.

划分树的一个重要特点是每一层相对于它的上一层（例如第4层相对第三层, 第三层相对第二层，第二层相对第一层）都是相对位置不变的. 例如第三层相对第二层中, 第三层的一个节点[2,1]在第二层 的节点[4,2,1,3]中的相对位置是不变的. 不变这一特性对于划分树的结构非常重要~

虽然划分树从上图来看有很多节点, 但其实我们并不会开很多节点出来. 而是将每一层的节点的数组都放在一个数组中, 即a[20][N] 这样. a[i] （0<=i<20）代表第i层的所有节点组成的数组. 当然为了解决区间topK问题, 我们还需要维护一个cnt[20][N] 数组, 其中cnt[i][j]（0<=i<20）怎么理解呢? 我们不是说了吗? 划分树中的每一层其实都是由多个节点构成的. 那么j（1<=j<=n）就在某个节点（记做P，并且假设它表示的索引范围是[begin, end], 1<=begin<end<=n）中, 而cnt[i][j] 就是P中的在j以及在j之前被归入P的左子树的元素的个数——即cnt[level][j]是a[level][begin,…,j] 中被归入左子节点（即a[level+1][begin, begin+end>>1]）中的元素的个数.

那么求区间从小到大第k小的问题就可以递归来求解了, 详见下面代码的query函数。

讲清楚了区间topK的划分树解法, 下面来考虑本题. 即如何将区间<=某个特定数的个数转换为区间topK问题. 很简单, 就是二分答案即可. [l,r]的区间有r-l+1个元素. 则lo = 0, hi = r-l+1, 然后二分答案. 检查mid=(lo+hi)>>1 是否可以. 而mid可以与否其实就是问[l,r]上从小到大排在第k=mid的元素是否<=h, 如果是的话, 则说明还可以增大ans.

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
//#include "stdafx.h"
#include <stdio.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 1e5+5;
int n,m,sorted[maxn], a[20][maxn], cnt[20][maxn];

void build(int level, int begin , int end) // 划分树第level层(level>=0)的构建, 做的事情是统计cnt[level], 以及组织a[level+1], 就这两件事情
{
	if (begin==end) // 划分树某一层的结果其实是由多个划分树子节点集体构成的
	{
		return;
	}
	int mid = begin+end>>1, ln = begin, rn = mid+1, samemid = 0; // 左右孩子的起点, samemid是x[begin,mid]中等于x[mid]的元素个数, 这些数都要进入左子树的
	for (int i = mid; i>=begin; --i)
	{
		if (sorted[i]<sorted[mid])
		{
			break;
		}
		if (sorted[i]==sorted[mid])
		{
			++samemid;
		}
	} // 统计samemid是有必要的. 因为可能a[level][mid+1,...]中也有=sorted[mid]的, 但是我们显然不能让它也进入划分树的左子树, 而要进入右子树, 例如原数组 0 5 2 7 5 4 3 8 7 7 排序之后是 0 2 3 4 5 5 7 7 7 8，x[mid=5]是5, 我们显然只能让一个5进入左子树, 而不能让两个5都进入左子树(不然, 左子树就有6个数, 而右子树只有4个数了), 我们希望进入左子树的是0 2 3 4 5,而进入右子树的是5 7 7 7 8，当然为了保证相对位置, 应该是 0 5 2 4 3, 进入右子树的是 7 5 8 7 7
	for (int i = begin;i<=end; i++)
	{
		cnt[level][i] = (i^begin)?cnt[level][i-1]:0; // cnt的初始值
		if (a[level][i] < sorted[mid] || a[level][i] == sorted[mid] && samemid) // 只有<x[mid]（排过序的x的作用就是提供完美的快排pivot）或者相等但是没有用掉samemid个额度
		{
			++cnt[level][i]; // 第一件事
			a[level+1][ln++] = a[level][i]; // 第二件事
			if (a[level][i]==sorted[mid])
			{
				--samemid;
			}
		}
		else
		{
			a[level+1][rn++] = a[level][i];
		}
	}
	build(level+1, begin, mid);
	build(level+1, mid+1, end);
}

int query(int level, int begin, int end, int l, int r, int k) // 查询[l,r]的从小到大排名第k的元素, 注意, 算法保证了 [l,r]是[begin,end]的子集
{
	if (!(begin^end))
	{
		return a[level][begin];
	}
	int mid = begin+end>>1;
	int x = (l^begin)?cnt[level][l-1]:0; // x是 a[level][begin,..., l-1]中进入左节点的元素个数
	int y = cnt[level][r]; // y是 a[level][begin, .., r]中进入左子节点的元素个数
	if (y-x>=k) // 如果 a[level][l,...,r]中进入左子节点的元素个数>=k, 则[l,r]的第k小的数一定在左子节点中, 因为左子节点都是a[level][begin,...,end]中归入左子树的元素. 而左子节点的元素的相对位置较当前节点并不会改变. 所以一定在[begin+x, begin+y-1]中, 注意, 这里所有的区间都是站在[1,n]的角度来说的, 并不是相对区间
	{
		return query(level+1, begin, mid, begin+x, begin+y-1,k); // 进入左子节点递归
	}
	else
	{
		int start = mid+1+l-begin-x; // l-begin-x是当前节点,即a[level][begin,..,end]中a[level][begin,...,l-1]中进入右子树的节点个数, 所以start是a[level][l,...,r]中第一个进入右子树中的节点的索引(注意,a[level][begin,...,l-1]中最后那个进入右子树的数组索引是mid+l-begin-x,所以a[level][l,...,r]中第一个进入右子树中的节点的数组的索引是mid+1+l-begin-x),注意, 再次强调, 所有的索引都是绝对的(即[1,..,n]中)而不是相对的
		int num = r-l+1-(y-x); // num是a[level][l,..,r]中进入右子树中的节点个数
		return query(level+1, mid+1, end, start, start+num-1, k-(y-x)); // 进入右子节点递归,这里依旧用到了右子节点中的元素相对当前节点,即a[level][begin,...,end]中的元素位置不变这一特性.
	}
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
//	freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	for (int i = 1; i<=kase; i++)
	{
		scanf("%d%d", &n,&m);
		for (int i = 1;i<=n;i++)
		{
			scanf("%d", sorted+i);
			a[0][i] = sorted[i]; // 划分树第一层就是原数组
		}
		sort(sorted+1, sorted+n+1); // 升序排序, 用于提供快排的完美pivot
		build(0, 1, n); // 递归建树
		printf("Case %d:\n", i);
		while(m--)
		{
			int l,r,h;
			scanf("%d%d%d", &l, &r, &h);
			int lo = 1, hi = r-l+1, ans = 0, mid;
			while (lo<=hi)
			{
				mid = lo+hi>>1; // 排名第mid
				int t = query(0,1,n,l+1,r+1,mid);
				if (t <= h)
				{
					ans = mid;
					lo = mid+1;
				}
				else
				{
					hi = mid-1;
				}
			} // 二分答案
			printf("%d\n", ans);
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 499ms
Memory 15840kB
Length 3104
Lang C++
Submitted 2019-10-16 18:58:40
Shared
RemoteRunId 30952414

参考

【1】https://yfsyfs.github.io/2019/09/04/poj-2104-K-th-Number-%E5%B9%B3%E6%96%B9%E5%88%86%E5%89%B2/

【2】https://yfsyfs.github.io/2019/09/04/poj-2104-K-th-Number-%E7%BA%BF%E6%AE%B5%E6%A0%91/

【3】https://yfsyfs.github.io/2019/10/15/%E6%B4%9B%E8%B0%B7-P3834-%E3%80%90%E6%A8%A1%E6%9D%BF%E3%80%91%E5%8F%AF%E6%8C%81%E4%B9%85%E5%8C%96%E7%BA%BF%E6%AE%B5%E6%A0%91-1%EF%BC%88%E4%B8%BB%E5%B8%AD%E6%A0%91%EF%BC%89/