poj 2104 K-th Number 线段树

缘起

题目已经在【1】中使用平方分割+二分答案的技巧艹了一遍, 现在使用线段树再艹一遍

分析

题目见【1】.

思想是这样的. 和【1】一样都是二分答案. 所以依旧需要将原数组排序。 然后进行二分答案. 但是和【1】不同的地方在于对于一个x, 如何快速计算<=x的数的个数（如果>=k, 则可以）.

【1】中用的是平方分割. 而这里使用（点）线段树来实现快速计算. 既然要用线段树，那肯定要建树. 建树的话毫无疑问肯定是对[1,…,n]进行建树. 每个节点代表的是一个区间. 而这里的线段树和之前的线段树不同之处在于线段树上节点的数据. 原先都是某种指标——最大、最小或者求和啥的. 但是现在不是了，现在是该节点代表的数列排序之后的数列. 举个例子吧~

1
1 5 2 6 7 3 4

这样的序列. 它建立的线段树如下图（图中节点上面画的是该节点的数据）

ps: 这里补了一个8（为了好看, 但是代码中不会）

每个节点上的数据都是一个有序数列. 而且从底部往上看，其实就是归并排序的过程. 所以这种线段树又被称为归并树. 那么我们要用这棵归并树来实现快速计算a[i,j]中<=x的元素个数. 怎么做呢? 假设我们手上已经有了一棵这样的归并树. 然后考虑我们的区间[i,j]. 如果区间和节点表示的区间[l,r]是一个区间的话，则直接用节点上的数据进行二分查找得到该节点上<=x的元素个数. 否则的话，用节点的中点对区间进行划分然后递归（这种手段对于写过线段树的童鞋再清楚不过了）. 就得到了此区间上<=x的元素个数. 所以我们再考虑建树. 回想归并排序的过程. 我们只需要在递归建树返回父节点的时候，将两棵子节点的数据（已经有序）merge成为有序序列（其实就是归并排序的过程）. 建树的复杂度是O(nlogn)（普通线段树的建树复杂度是O(n)）.

其实想想看——比平方分割好写! 平方分割虽然思想简单，但是代码实现起来比较精细, 容易出错.

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
141
142
143
//#include "stdafx.h"

#include <stdio.h>
#include <algorithm>
#include <vector>
using namespace std;
//#define LOCAL
typedef vector<int>::iterator vit;

const int maxn = 100005;

int n,m,a[maxn],b[maxn]; // a是原数组, b是a排序之后——用于二分答案

struct SegTreeNode
{
	int begin, end;
	vector<int> v;
}segTree[maxn<<2];

void merge(vector<int> &v, vector<int> &a, vector<int> &b) // a和b已然有序, 将他们归并入v
{
	vit ita = a.begin(), itb = b.begin();
	while(ita!=a.end() && itb!=b.end())
	{
		if (*ita<*itb)
		{
			v.push_back(*ita);
			ita++;
		}
		else
		{
			v.push_back(*itb);
			itb++;
		}
	}
	while(ita!=a.end())
	{
		v.push_back(*ita);
		ita++;
	}
	while(itb!=b.end())
	{
		v.push_back(*itb);
		itb++;
	}
}

void build(int begin, int end, int cur)
{
	segTree[cur].begin = begin;
	segTree[cur].end = end;
	if (begin==end)
	{
		segTree[cur].v.push_back(a[begin]);
		return;
	}
	int mid = (begin+end)>>1;
	build(begin, mid, cur<<1);
	build(mid+1, end, cur<<1|1);
	merge(segTree[cur].v, segTree[cur<<1].v,segTree[cur<<1|1].v); // 将两个孩子的数列有序归并进入父节点,这是归并树建树和普通线段树建树不同之处
}

int getcnt(vector<int> &v, int x) // v是升序向量, 计算里面<=x的元素个数
{
	int lo = 0, hi = v.size()-1, ans=-1, mid;
	while(lo<=hi)
	{
		mid = (lo+hi)>>1;
		if (v[mid]<=x)
		{
			ans = mid;
			lo = mid+1;
		}
		else
		{
			hi = mid-1;
		}
	}
	return ~ans?++ans:0;
}

int ck(int i, int j, int x, int cur) // 从归并树计算a[i,j]区间中<=x的元素个数
{
	if (i == segTree[cur].begin && j == segTree[cur].end)
	{
		return getcnt(segTree[cur].v,x);
	}
	int mid = (segTree[cur].begin+segTree[cur].end)>>1;
	if (j<=mid)
	{
		return ck(i,j, x, cur<<1);
	}
	else if (i>mid)
	{
		return ck(i,j, x, cur<<1|1);
	}
	else
	{
		return ck(i, mid, x, cur<<1)+ck(mid+1, j, x, cur<<1|1);
	}
}

int solve(int i, int j, int k) // 二分答案
{
	int lo = 1, hi = n, mid, ans = 0;
	while(lo<=hi)
	{
		mid = (lo+hi)>>1;
		if (ck(i,j,b[mid],1)>=k)
		{
			ans = mid;
			hi = mid-1;
		}
		else
		{
			lo = mid+1;
		}
	}
	return b[ans];
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	scanf("%d%d", &n, &m);
	for (int x = 1;x<=n;x++)
	{
		scanf("%d", a+x);
		b[x] = a[x];
	}
	sort(b+1, b+n+1); // 建树
	build(1, n, 1);
	while(m--)
	{
		int i,j,k;
		scanf("%d%d%d", &i, &j, &k);
		printf("%d\n", solve(i,j,k));
	}
	return 0;
}

归并树写起来很爽~ 一路思路清晰的一口气写完~ 极度爽!!!

ac情况

Status Accepted
Time 9469ms
Memory 24904kB
Length 2269
Lang C++
Submitted 2019-09-04 17:42:07
RemoteRunId 20832124

妈蛋~ 归并树和平方分割都是慢的一批!!!

参考

【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/