|
|
#include <bits/stdc++.h>
|
|
|
using namespace std;
|
|
|
const int N = 100010;
|
|
|
typedef pair<int, int> PII;
|
|
|
PII a[N];
|
|
|
//三个数字取最大值
|
|
|
int max(int a, int b, int c) {
|
|
|
return max(a, max(b, c));
|
|
|
}
|
|
|
|
|
|
//线段树结构体
|
|
|
struct Node {
|
|
|
int l, r; //区间范围
|
|
|
int ls, rs; //左右孩子节点号
|
|
|
int lx, rx; //左前缀、右后缀最大值
|
|
|
int mx; //区间最大值
|
|
|
int len() { //结构体的内置函数,计算区间长
|
|
|
return r - l + 1;
|
|
|
}
|
|
|
} tr[N * 32];
|
|
|
|
|
|
//动态开点维护主席树
|
|
|
int root[N], idx;
|
|
|
int n, m;
|
|
|
|
|
|
//构建0号版本
|
|
|
//其实这个0号版本,也是一个实打实的完整线段树,而不是残疾树,都是按二分创建的每个分段信息节点
|
|
|
int build(int l, int r) {
|
|
|
int p = ++idx; //动态开点
|
|
|
tr[p] = {l, r}; //记录左右边界,主席树是不是都需要记录左右边界呢?一会再复习下区间第K小数看看
|
|
|
if (l == r) return p; //如果是叶子,返回节点号
|
|
|
int mid = (l + r) >> 1; //不是叶子节点,创建左儿子和右儿子
|
|
|
tr[p].ls = build(l, mid);
|
|
|
tr[p].rs = build(mid + 1, r);
|
|
|
return p; //返回节点号
|
|
|
}
|
|
|
|
|
|
//将两个区间合并,用途:
|
|
|
// 1、更新某个区间向上传递更新父节点信息
|
|
|
// 2、某个查询请求恰好是跨左右区间时,左一半来右一半,需要拼接结果时,也可以使用这个pushup函数
|
|
|
// 按理说,这个函数命名为pushup不尽合理,因为用途1时确实是比较达意,用途2时应该是merge的含义,
|
|
|
// 为了避免和“线段树的分裂与合并”中的merge函数重名,姑且按这个来命名吧~
|
|
|
void pushup(Node &c, Node a, Node b) {
|
|
|
c.lx = (a.len() == a.mx) ? a.mx + b.lx : a.lx;
|
|
|
c.rx = (b.len() == b.mx) ? b.mx + a.rx : b.rx;
|
|
|
c.mx = max(a.mx, b.mx, a.rx + b.lx);
|
|
|
}
|
|
|
|
|
|
//权值线段树,基于p这个旧版本,增加一个数字x,生成一个新版本q
|
|
|
int insert(int p, int x) {
|
|
|
int q = ++idx; //申请新的节点号
|
|
|
tr[q] = tr[p]; //先抄过去
|
|
|
if (tr[q].l == tr[q].r) { //叶子节点,左前缀最大=右后缀最大=整体区间最大
|
|
|
tr[q].lx = tr[q].rx = tr[q].mx = 1;
|
|
|
return q;
|
|
|
}
|
|
|
int mid = (tr[q].l + tr[q].r) >> 1;
|
|
|
if (x <= mid)
|
|
|
tr[q].ls = insert(tr[p].ls, x);
|
|
|
else
|
|
|
tr[q].rs = insert(tr[p].rs, x);
|
|
|
|
|
|
//向父节点更新统计信息
|
|
|
pushup(tr[q], tr[tr[q].ls], tr[tr[q].rs]);
|
|
|
return q;
|
|
|
}
|
|
|
//目标:在以p为根节点的第mid版本的线段树中去查询[l,r]之间的最大连续子段和mx
|
|
|
Node query(int p, int l, int r) {
|
|
|
if ((l <= tr[p].l) && (tr[p].r <= r)) return tr[p]; //因为递归函数需要拼接多个属性,需要返回值为Node
|
|
|
int mid = (tr[p].l + tr[p].r) >> 1;
|
|
|
if (r <= mid)
|
|
|
return query(tr[p].ls, l, r);
|
|
|
else if (l > mid)
|
|
|
return query(tr[p].rs, l, r);
|
|
|
else {
|
|
|
Node a, b, c;
|
|
|
a = query(tr[p].ls, l, r);
|
|
|
b = query(tr[p].rs, l, r);
|
|
|
pushup(c, a, b);
|
|
|
return c;
|
|
|
}
|
|
|
}
|
|
|
int main() {
|
|
|
cin >> n;
|
|
|
for (int i = 1; i <= n; i++) {
|
|
|
cin >> a[i].first; //这个离散化做的漂亮~~
|
|
|
a[i].second = i; //高度只起到了排序的作用,1e9也没啥了不起,真正用来建树的是序号i
|
|
|
}
|
|
|
//高度由高到低排序
|
|
|
sort(a + 1, a + 1 + n, greater<PII>());
|
|
|
|
|
|
//构建0号版本
|
|
|
root[0] = build(1, n); //创建0号版本的根节点,通过&引用,回写到root[0]
|
|
|
|
|
|
//构建主席树 (多个版本的权值线段树)
|
|
|
//基于前一个版本构建,将a[i].second这个位置变为1
|
|
|
//为了二分,也是拼了,将可能遇到的mid∈[1,n]的所有线段树全部建立出来,也就用到的主席树
|
|
|
//大于等于mid的标识为1,小于mid的标识为0
|
|
|
//我们按高度由大到小排序后再建立线段树,最大的先来,自然比它大的还没有,它自己等于自己,把自己位置置为1即可
|
|
|
//第二高的来到时,也只需把自己所在位置置为1,就可以描述现在整个线段树中存在两个大于等于自己的
|
|
|
//第三高的来到时,....
|
|
|
//看来这个由大到小也算是主席树的套路吧~
|
|
|
//求最大连续1的个数,也是线段树的常用求法吧,只不过现在是整合在主席树中应用
|
|
|
for (int i = 1; i <= n; i++) root[i] = insert(root[i - 1], a[i].second);
|
|
|
|
|
|
cin >> m;
|
|
|
for (int i = 1; i <= m; i++) {
|
|
|
int L, R, w;
|
|
|
//每个询问包括l,r,w三个数,询问我们在l到r这个区间内连续取w个数,使这w个数中的最小值尽可能的大
|
|
|
cin >> L >> R >> w;
|
|
|
//二分大法
|
|
|
int l = 1, r = n;
|
|
|
while (l < r) {
|
|
|
int mid = (l + r) >> 1; //假设最小值是mid,对应的就是在主席树中第mid个版本去查询
|
|
|
//查询[L,R]这个区间内,连续子段和mx是多大,如果大于w,说明mid太大,再小一点
|
|
|
if (query(root[mid], L, R).mx >= w)
|
|
|
r = mid;
|
|
|
else //如果小于w,说明mid太小了,再大一点
|
|
|
l = mid + 1;
|
|
|
}
|
|
|
printf("%d\n", a[l].first);
|
|
|
}
|
|
|
return 0;
|
|
|
} |