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.
2.3 KiB
2.3 KiB
https://codeforces.com/problemset/problem/484/E?f0a28=1 https://www.luogu.com.cn/problem/CF484E
Q:本题为什么没有使用离散化？主席树到底需不需要离散化？？
一、题目描述
给我们一组数，并给出m个询问，每个询问包括l，r，w三个数，询问我们在l到r这个区间内连续取w个数，使这w个数中的最小值尽可能的大，输出这个最大的最小值。
二、解题思路
首先我们先假设在当前的询问下x这个数可以成为连续w个数中的最小值(x一定为某个数的值)，然后把数列中大于等于x的数标为1,小于x的数标为0，那么如果我们求出这个01串中最长的1串长度为s,且s>=w的话，x就可以拿去更新当前答案，然后我们就枚举比x大的值看是否符合条件，当然这个枚举过程用二分实现。
用线段树求一串数中最长的1串，应该都做过。所以问题就变成了我们如何来建立这个01串，很显然，我们不可能去构造n棵线段树。假设有两个数x,y且x>y那么很显然y的01串是x的01串的基础上多添加了几个1,所以我们可以用可持续化线段树来维护当前01串下的最长1串的长度。
二、个人感悟过程
1、主席树为什么要记录[l,r],其它题的主席树也记录了左右边界吗？
答： 区间内第k小的数，也是记录了l,r，看来记录l,r是通用办法。
2、在左前缀，右后缀，连续最大值这样的问题中，左右边界的长度都很关键，是直接记录len,还是通过记录l,r，计算出len?
答: 既然主席树中都需要记录l,r,那么
int len(){
return r-l+1;
}
就是标配了。
3、0号版本似乎就是个架子，没有真正的内容。真正的内容都是一个一个，通过insert装载进来，生成一个个版本的。
答：事实上是这样的，但这个动作是标配，不能省略。
4、 insert和query的参数
p参数都表示以此版本的线段树，是以p号节点为根节点的。
5、insert和query的返回值
insert:返回的是新增加一个数值后，新创建的版本对应的根节点编号q query:返回的是一个查询拼接后的结构体，以便读取mx,lx,rx等信息。