[题解]CF484E Sign on Fence

发表于 | 评论数： | 阅读次数：
本文字数： 3.7k | 阅读时长 ≈ 3 分钟

题目描述

洛谷

CF

题解

看到题目问的是最小值的最大值，显然可以二分求解

给出的高度在$10^9$范围内，需要先对高度进行离散化

假如我们二分出了一个$mid$，怎么判断它是否合法？可以这么解决，将所有数大于等于$mid$的数赋为$1$，其余赋为$0$，那么就是判断$[l,r]$之间是否存在一个长度大于等于$k$的连续的$1$

可以对所有高度建一棵线段树，维护区间内最长$1$的长度，从左和从右开始最长$1$的长度，但是这样空间复杂度爆炸。我们可以使用主席树来维护。

可以按高度从大到小建树，保证大于等于它的数的位置都赋值了

初始时要建树计算一下区间长度，否则在pushup时判断时会出错

1
2
if(tree[ls(k)].lmax == tree[ls(k)].len) ···
if(tree[rs(k)].rmax == tree[rs(k)].len) ···

Code

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
#include <bits/stdc++.h>
#define ls(k) tree[k].ls
#define rs(k) tree[k].rs
using namespace std;

const int MAXN = 1e5 + 10;

int read()
{
	int sum = 0 , f = 1;
	char c = getchar();
	while(c < '0' or c > '9')
	{
	   if(c == '-') f = -1;
	   c = getchar();
	}
	while(c >= '0' and c <= '9')
	{
		sum = sum * 10 + c - '0';
		c = getchar();
	}
	return sum * f;
}

int n , m , cnt , len;
int a[MAXN] , b[MAXN] , root[MAXN] , numroot[MAXN];

struct hjtTree{
	int ls , rs , val , lmax , rmax , len;
}tree[MAXN * 40];

void pushup(int k)
{
	tree[k].val = max(tree[ls(k)].val , tree[rs(k)].val);
	tree[k].val = max(tree[ls(k)].rmax + tree[rs(k)].lmax , tree[k].val);
	if(tree[ls(k)].lmax == tree[ls(k)].len)
	  tree[k].lmax = tree[ls(k)].lmax + tree[rs(k)].lmax;
	else
	  tree[k].lmax = tree[ls(k)].lmax;
	if(tree[rs(k)].rmax == tree[rs(k)].len)
	  tree[k].rmax = tree[rs(k)].rmax + tree[ls(k)].rmax;
	else 
	  tree[k].rmax = tree[rs(k)].rmax;
}

void update(int l , int r , int pre , int &now , int pos)
{
	tree[++ cnt] = tree[pre];
	now = cnt;
	tree[now].len = r - l + 1;
	if(l == r)
	{
		tree[now].lmax = tree[now].rmax = tree[now].val = tree[now].len = 1;
		return;
	}
	int mid = (l + r) >> 1;
	if(pos <= mid) update(l , mid , ls(pre) , ls(now) , pos);
	else update(mid + 1 , r , rs(pre) , rs(now) , pos);
	pushup(now);
}

int query(int l , int r , int now , int sl , int sr)
{
	if(l >= sl and r <= sr) return tree[now].val;
	int mid = (l + r) >> 1 , s = 0;
	if(sl <= mid) s = max(s , query(l , mid , ls(now) , sl , sr));
	if(sr > mid) s = max(s , query(mid + 1 , r , rs(now) , sl , sr));
	if(sl <= mid and sr > mid)
	{
		int s1 = min(tree[ls(now)].rmax , mid - sl + 1);
		int s2 = min(tree[rs(now)].lmax , sr - mid);
		s = max(s , s1 + s2);
	}
	return s;
}

void build(int l , int r , int &now)
{
	now = ++ cnt;
	tree[now].len = r - l + 1;
	if(l == r) return;
	int mid = (l + r) >> 1;
	build(l , mid , ls(now));
	build(mid + 1 , r , rs(now));
}

vector<int> id[MAXN];

int solve(int l , int r , int k)
{
	int sl = 1 , sr = len , ans = 0;
	while(sl <= sr)
	{
		int mid = (sl + sr) >> 1;
		if(query(1 , n , numroot[mid] , l , r) >= k)
		  ans = mid , sl = mid + 1;
		else
		  sr = mid - 1;
	}
	return b[ans];
}

int main()
{
	n = read();
	for(int i = 1; i <= n; i ++) a[i] = b[i] = read();
	sort(b + 1 , b + n + 1);
	len = unique(b + 1 , b + n + 1) - b - 1;
	for(int i = 1; i <= n; i ++)
	{
		a[i] = lower_bound(b + 1 , b + len + 1 , a[i]) - b;
		id[a[i]].push_back(i);
	}
	build(1 , n , root[0]);
	int node = 0;
	for(int i = len; i >= 1; i --)
	{
		int siz = id[i].size();
		for(int j = 0; j < siz; j ++)
		{
			node ++;
			update(1 , n , root[node - 1] , root[node] , id[i][j]);
		}
		numroot[i] = root[node];
	}
	m = read();
	while(m --)
	{
		int l = read() , r = read() , k = read();
		printf("%d\n" , solve(l , r , k));
	}
	return 0;
}