hdu4417

maksyuki 发表于 oj 分类，标签: 数值-二分\三分\折半枚举, 数据结构-划分树

15 1月 2016

Super Mario

Problem Description

Mario is world-famous plumber. His “burly” figure and amazing jumping ability reminded in our memory. Now the poor princess is in trouble again and Mario needs to save his lover. We regard the road to the boss’s castle as a line (the length is n), on every integer point i there is a brick on height hi. Now the question is how many bricks in [L, R] Mario can hit if the maximal height he can jump is H.

Input

The first line follows an integer T, the number of test data.
For each test data:
The first line contains two integers n, m (1 <= n <=10^5, 1 <= m <= 10^5), n is the length of the road, m is the number of queries.
Next line contains n integers, the height of each brick, the range is [0, 1000000000].
Next m lines, each line contains three integers L, R,H.( 0 <= L <= R < n 0 <= H <= 1000000000.)

Output

For each case, output "Case X: " (X is the case number starting from 1) followed by m lines, each line contains an integer. The ith integer is the number of bricks Mario can hit for the ith query.

Sample Input

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

Sample Output

Case 1:

Source

2012 ACM/ICPC Asia Regional Hangzhou Online

题目类型：划分树+二分枚举

算法分析：二分枚举每次要查询的区间长度(即rank)，之后就是简单的判断

/*************************************************
Author        :supermaker
Created Time  :2016/1/15 0:17:04
File Location :C:\Users\abcd\Desktop\TheEternalPoet
**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")
#include <set>
#include <bitset>
#include <list>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <string>
#include <vector>
#include <ios>
#include <iostream>
#include <fstream>
#include <sstream>
#include <iomanip>
#include <algorithm>
#include <utility>
#include <complex>
#include <numeric>
#include <functional>
#include <cmath>
#include <ctime>
#include <climits>
#include <cstdarg>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cctype>
#include <cassert>
using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)
#define CPPFF ifstream cin ("aaa.txt")
#define	DB(ccc)	cout << #ccc << " = " << ccc << endl
#define PB push_back
#define MP(A, B) make_pair(A, B)

typedef long long LL;
typedef unsigned long long ULL;
typedef double DB;
typedef pair <int, int> PII;
typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;
const int MOD = 1e9 + 7;
const double EPS = 1e-10;
const double PI = 2 * acos (0.0);
const int maxn = 1e5 + 6666;

int sorted[maxn], tree[30][maxn], toleft[30][maxn];

void build (int dep, int l, int r)
{
	if (l == r) return ;
	int mid = (l + r) >> 1;
	int same = mid - l + 1;
	for (int i = l; i <= r; i++)
		if (tree[dep][i] < sorted[mid])
			same--;

	int lpos = l, rpos = mid + 1;
	for (int i = l; i <= r; i++)
	{
		if (tree[dep][i] < sorted[mid])
			tree[dep+1][lpos++] = tree[dep][i];

		else if (tree[dep][i] == sorted[mid] && same > 0)
		{
			tree[dep+1][lpos++] = tree[dep][i];
			same--;
		}

		else
			tree[dep+1][rpos++] = tree[dep][i];
		toleft[dep][i] = toleft[dep][l-1] + (lpos - l);
	}
	build (dep + 1, l, mid);
	build (dep + 1, mid + 1, r);
}

int query (int dep, int L, int R, int l, int r, int k)
{
	if (l == r) return tree[dep][l];
	int mid = (L + R) >> 1;
	int tot = toleft[dep][r] - toleft[dep][l-1];
	if (tot >= k)
	{
		int newl = L + toleft[dep][l-1] - toleft[dep][L-1];
		int newr = newl + tot - 1;
		return query (dep + 1, L, mid, newl, newr, k);
	}

	else
	{
		int newr = r + toleft[dep][R] - toleft[dep][r];
		int newl = newr - (r - l - tot);
		return query (dep + 1, mid + 1, R, newl, newr, k - tot);
	}
}

int main()
{
    //CFF;
    //CPPFF;
	int t, flag = 1;
	scanf ("%d", &t);
	while (t--)
	{
		int n, q;
		memset (tree, 0, sizeof (tree));
		memset (toleft, 0, sizeof (toleft));
		scanf ("%d%d", &n, &q);
		for (int i = 1; i <= n; i++)
		{
			scanf ("%d", &tree[0][i]);
			sorted[i] = tree[0][i];
		}
		sort (sorted + 1, sorted + 1 + n);
		build (0, 1, n);
		
		printf ("Case %d:\n", flag++);
		for (int i = 1; i <= q; i++)
		{
			int ll, rr, kk;
			scanf ("%d%d%d", &ll, &rr, &kk);
			ll++, rr++;
			int low = 1, high = rr - ll + 1, res = 0;
			while (low <= high)
			{
				int mid = (low + high) >> 1;
				int val = query (0, 1, n, ll, rr, mid);
				if (val <= kk) low = mid + 1, res = mid;
				else high = mid - 1; 
			}
			printf ("%d\n", res);
		}
	}
    return 0;
}

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

144

145

/*************************************************

Author :supermaker

Created Time :2016/1/15 0:17:04

File Location :C:\Users\abcd\Desktop\TheEternalPoet

**************************************************/

#pragma comment(linker, "/STACK:102400000,102400000")

#include <set>

#include <bitset>

#include <list>

#include <map>

#include <stack>

#include <queue>

#include <deque>

#include <string>

#include <vector>

#include <ios>

#include <iostream>

#include <fstream>

#include <sstream>

#include <iomanip>

#include <algorithm>

#include <utility>

#include <complex>

#include <numeric>

#include <functional>

#include <cmath>

#include <ctime>

#include <climits>

#include <cstdarg>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cctype>

#include <cassert>

using namespace std;

#define CFF freopen ("aaa.txt", "r", stdin)

#define CPPFF ifstream cin ("aaa.txt")

#define DB(ccc) cout << #ccc << " = " << ccc << endl

#define PB push_back

#define MP(A, B) make_pair(A, B)

typedef long long LL;

typedef unsigned long long ULL;

typedef double DB;

typedef pair <int, int> PII;

typedef pair <int, bool> PIB;

const int INF = 0x7F7F7F7F;

const int MOD = 1e9 + 7;

const double EPS = 1e-10;

const double PI = 2 * acos (0.0);

const int maxn = 1e5 + 6666;

int sorted[maxn], tree[30][maxn], toleft[30][maxn];

void build (int dep, int l, int r)

{

if (l == r) return ;

int mid = (l + r) >> 1;

int same = mid - l + 1;

for (int i = l; i <= r; i++)

if (tree[dep][i] < sorted[mid])

same--;

int lpos = l, rpos = mid + 1;

for (int i = l; i <= r; i++)

{

if (tree[dep][i] < sorted[mid])

tree[dep+1][lpos++] = tree[dep][i];

else if (tree[dep][i] == sorted[mid] && same > 0)

{

tree[dep+1][lpos++] = tree[dep][i];

same--;

}

else

tree[dep+1][rpos++] = tree[dep][i];

toleft[dep][i] = toleft[dep][l-1] + (lpos - l);

}

build (dep + 1, l, mid);

build (dep + 1, mid + 1, r);

}

int query (int dep, int L, int R, int l, int r, int k)

{

if (l == r) return tree[dep][l];

int mid = (L + R) >> 1;

int tot = toleft[dep][r] - toleft[dep][l-1];

if (tot >= k)

{

int newl = L + toleft[dep][l-1] - toleft[dep][L-1];

int newr = newl + tot - 1;

return query (dep + 1, L, mid, newl, newr, k);

}

else

{

int newr = r + toleft[dep][R] - toleft[dep][r];

int newl = newr - (r - l - tot);

return query (dep + 1, mid + 1, R, newl, newr, k - tot);

}

int main()

{

//CFF;

//CPPFF;

int t, flag = 1;

scanf ("%d", &t);

while (t--)

{

int n, q;

memset (tree, 0, sizeof (tree));

memset (toleft, 0, sizeof (toleft));

scanf ("%d%d", &n, &q);

for (int i = 1; i <= n; i++)

{

scanf ("%d", &tree[0][i]);

sorted[i] = tree[0][i];

}

sort (sorted + 1, sorted + 1 + n);

build (0, 1, n);

printf ("Case %d:\n", flag++);

for (int i = 1; i <= q; i++)

{

int ll, rr, kk;

scanf ("%d%d%d", &ll, &rr, &kk);

ll++, rr++;

int low = 1, high = rr - ll + 1, res = 0;

while (low <= high)

{

int mid = (low + high) >> 1;

int val = query (0, 1, n, ll, rr, mid);

if (val <= kk) low = mid + 1, res = mid;

else high = mid - 1;

}

printf ("%d\n", res);

}

return 0;

}

hdu4251

zoj1654

超客的水墨烟雨

hdu4417

Super Mario

分类目录

标签云

书签

近期评论

2025年4月
一	二	三	四	五	六	日
« 6月
	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