You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

124 lines
5.1 KiB

This file contains ambiguous Unicode characters!

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

#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;
//每个询问包括lrw三个数询问我们在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;
}