poj 2104 K-th Number 平方分割

缘起

日常浪费生命 poj 2104 K-th Number

分析

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
给定一个序列a1,...,an和m个三元组表示的查询. 对于每个查询(i,j,k),输出ai,...,aj升序排列中的第k个数.

【输入】
第一行是数组中元素的个数. 然后是m表示询问的个数. 然后是n个绝对值不超过10亿的整数. 
1 <= n <= 100 000, 1 <= m <= 5 000
每个询问是 (i,j,k)
1 <= i <= j <= n, 1 <= k <= j - i + 1

【输出】
回答每个询问.

【样例输入】
7 3
1 5 2 6 3 7 4
2 5 3
4 4 1
1 7 3

【样例输出】
5
6
3

【限制】
20s

此题很多种解法，主席树、可持久化线段树（后面会写文章论述,现在还不会~ QAQ）. 本文采用平方分割这种简单易懂的思路做. 所谓平方分割就是将原数组每b个放到一起. 则一共 n/b 个桶（所以平方分割也叫分桶法）.

保证每个桶内的元素是升序的. 然后，因为答案肯定在最初的序列中啊. 所以要升序排序原数组然后二分答案. 所以

  1. 平方分割, 每个桶中的元素有b个, 并且保证桶内的元素都是升序的.
  2. 原数组copy一份出来并且升序排序.

O(nlogn)+O(n/b*blogb) = O(nlogn)

然后对于测试的”答案”, 要能快速计算区间内<=它的元素个数. 如果恰好是k的话, 则它就是答案.

如何快速呢? 如果桶包含在区间内的话, 则用二分搜索. 复杂度是O(logb). 如果不是的话, 则需要遍历, 复杂度是O(b)

处理的复杂度是 O(n/b*logb)+O(b).

所以二分答案回答每个询问的复杂度是 O(logn)*(O(n/b*logb)+O(b))

所以整个问题的复杂度是

O(nlogn)+m*(O(logn)*(O(n/b*logb)+O(b)))

令 b = sqrt(n*logn)较好（《挑战程序设计竞赛》中选了这个）（比 sqrt(n)要好, 使用sqrt(n)会被T掉的!!!）

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 <math.h>
using namespace std;
//#define LOCAL

int n,m,a[100005],b[100005],c[100005],bnum; // bnum是桶的大小,a是原数组, b是用于二分答案的数组, c是分桶(桶内有序)的数组

int getstart(int i) // 获取第i个桶的左端点的索引(在b中的索引)
{
	return (i-1)*bnum+1;
}

int getend(int i) // 获取第i个桶的右端点的索引(在b中的索引)
{
	return min(i*bnum, n);
}

int getcnt(int kk[], int n, int x) // 求出a[0,...,n-1]中<=x 中的数的个数,没有现成的lower_bound可以使用, 只好自己写一个
{
	int lo = 0, hi = n-1, ans=-1, mid;
	while(lo<=hi)
	{
		mid = (lo+hi)>>1;
		if (kk[mid]<=x)
		{
			ans = mid;
			lo = mid+1;
		}
		else
		{
			hi = mid-1;
		}
	}
	if (~ans)
	{
		return ++ans;
	}
	return 0;
}

int ck(int x,int i, int j) // 快速计算a[i,j]中<=x的元素个数
{
	int ans = 0;
	int start = (i-1)/bnum+1; // 和[i,j]有交集的第一个桶
	while(1)
	{
		int startindex = getstart(start);
		int endindex = getend(start); // 得到此桶的区间为 [startindex, endindex]
		if (startindex>j)
		{
			break;
		}
		if (startindex<i) // 对于没有完全包含在[i,j]中的桶,要遍历原数组
		{
			for (int y = i; y<=j && y<=endindex; y++)
			{
				if (a[y]<=x)
				{
					ans++;
				}
			}
		}
		else if (endindex<=j) // 如果此桶完全包含在[i,j]中
		{
			ans+=getcnt(c+startindex, min(bnum, n-startindex+1), x); // 可以使用二分来计算此桶中<=x的元素的个数(因为预处理的时候已经保证了桶中的元素升序), 注意, 此桶未必一定是满的bnum个元素(例如最后那个桶)
		}
		else // 如果startindex>=i 但是 endindex>j的话, 也是需要遍历原数组的
		{
			for (int y = startindex; y<=j; y++)
			{
				if (a[y]<=x)
				{
					ans++;
				}
			}
		}
		start++; // 考察下一个桶
	}
	return ans;
}

int solve(int i, int j, int k) // 回答询问(i,j,k)
{
	int lo = 1, hi = n, ans=0, mid;
	while(lo<=hi)
	{
		mid = (lo+hi)>>1;
		int t = ck(b[mid],i,j);
		if (t>=k) // 如果区间[i,j]中<=b[mid]的元素个数>=k,说明mid给大了
		{
			ans = mid;
			hi = mid-1;
		}
		else
		{
			lo = mid+1;
		}
	}
	return b[ans];
}

void init() // 平方分割处理
{
	sort(b+1, b+n+1); // 整体排序——用于二分答案
	bnum = (int)(sqrt(1.0*n*log(1.0*n)/log(2.0))+0.5); // 桶的大小
	if (!bnum)
	{
		bnum = 1;
	}
	for(int i = 1,j=1; i<=n;i++)
	{
		if (!(i%bnum) || i==n)
		{
			sort(c+j,c+i+1);
			j = i+1;
		}
	} // 确保每个桶中的元素都是升序排序的
}

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

ac情况（水过水过~ 跑了近10秒! 真特么慢!!! 但是主席树什么的，只需要不到2s! 以后一定要学一下主席树! QAQ）

Status Accepted
Time 9985ms
Memory 1312kB
Length 2338
Lang C++
Submitted 2019-09-04 13:36:20
Shared
RemoteRunId 20831269