(Codeforce484E)Sign on Fence(可持久化线段树+二分)_codeforces 484 e

题目链接：Problem - E - Codeforces

题意：一开始给你n个数，然后给你m个询问，询问格式是l,r,w，代表在第l个数和r个数之间任选连续w个数中的最小值的最大值是多少

题意有点绕，因为我们每选择连续w个数都会有一个最小值，因为选择的数不同，所以最小值也会不同，我们要求的就是我们所有选择中的最小值的最大值。

分析：这道题还是有一定的思维含量的，首先我们可以发现的是答案一定是所给的n个数中的一个，于是我们就可以二分高度，但是由于我们要在区间l到r内进行二分高度，没法直接解决连续这个条件，在线段树中出现连续显然是和区间合并有关，我在这分享一道线段树区间合并的例题:LCIS（线段树+区间合并）_AC__dream的博客-CSDN博客

我们可以先将原来给的数按照高度从高到低排序，然后进行主席树的创建，那我们在二分高度的时候就相当于二分线段树版本（线段树版本越低，则里面的数值越大），先对线段树里面的数进行解释，我们第i个版本的线段树里面装有的元素都是高度大于等于h[i]（排完序后）的，如果h[i]是第j个数，我们就在第i个版本上把j位置上标记为1（相对于第i-1个版本的线段树），这样我们第i个版本的线段树中所有标记为1的位置含有的数值都是大于等于h[i]的（含有之前版本标记的数值大于h[i]的数），这样我们在二分时判断h[i]是否满足条件就相当于直接在第i个版本的线段树上查询l到r区间上连续1的个数即可，这个地方的转换还是挺妙的。

线段树中一共记录有三个与长度有关的变量：

lenl[id]表示编号为id的区间以左端点开始连续1的个数 
lenr[id]表示编号为id的区间以右端点结束连续1的个数
lenmx[id]表示编号为id的区间中连续1的最大长度

线段树区间合并的难点就在于pushup函数的书写，下面来说一下pushup函数的写法：

pushup的作用也就是相当于我们知道了区间id左右子区间内lenl，lenr，lenmx的值，我们要用左右子区间的这些值来更新当前区间的这些变量对应的值。

先来看下lenmx，这个有三种可能，一种是等于左子区间的lenmx，还有一种是等于右子区间的lenmx，最后一种可能就是跨越两个区间，也就是左子区间的lenr与右子区间的lenl之和

至于lenl，这个地方需要分类讨论，如果左子区间的lenl等于左子区间的长度，那么当前区间的lenl就等于左子区间的长度+右子区间的lenl

lenr更新方式类似，如果右子区间的lenr等于右子区间的长度，那么当前区间的lenr就等于右子区间的长度+左子区间的lenr

还有一个需要注意的地方就是在进行区间查询时：

如果遍历到的当前区间恰好在目标区间内我们直接返回当前区间的最大值就好了，但是假如目标区间横跨当前区间的左右两个子区间我们并不能直接返回lenr[ln[id]]+lenl[rn[id]]这是因为这里面包含的连续的1是可能超出目标区间的，所以我们要对这两个值进行一定的处理，假如当前区间是[l,r],那么当前区间的左子区间就是[l,mid],右子区间就是[mid+1,r],那么我们应该查询[L,mid]和[mid+1,R]的连续1的最大长度，换句话说就是我们lenr[ln[id]]的长度不能超过[L,mid]的区间长度，而同理lenl[rn[id]]的长度不能超过[mid+1,R]的区间长度，我们只需要对这两个值取一个最小值即可。

有了这些说明，代码就比较容易写了

#include<cstdio>
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
#include<map>
#include<cmath>
#include<queue>
using namespace std;
const int N=1e5+10;
const int M=20; 
int ln[N*M],rn[N*M],root[N],idx;
int lenl[N*M],lenr[N*M],lenmx[N*M];
//lenl[id]表示编号为id的区间以左端点开始连续1的个数 
//lenr[id]表示编号为id的区间以右端点结束连续1的个数
//lenmx[id]表示编号为id的区间中连续1的最大长度
struct node{
	int h,id;
}p[N];
bool cmp(node a,node b)
{
	return a.h>b.h;
}
void pushup(int id,int l,int r)//区间合并 
{
	lenmx[id]=max(lenmx[ln[id]],lenmx[rn[id]]);//当前区间的最长连续1的个数分布在一个区间中 
	lenmx[id]=max(lenmx[id],lenr[ln[id]]+lenl[rn[id]]);//当前区间的最长连续1的个数分布在左右两个子区间中
	int mid=l+r>>1;
	if(lenl[ln[id]]==(mid-l+1))//当前区间左子区间以左端点开始连续1的个数等于左子区间长度，当前区间以左端点开始连续1的个数就应该计算上右子区间以左端点开始连续1的个数 
		lenl[id]=lenl[ln[id]]+lenl[rn[id]];
	else//否则当前区间以左端点开始连续1的个数就是当前区间以左子区间左端点开始连续1的个数 
		lenl[id]=lenl[ln[id]];
	if(lenr[rn[id]]==(r-mid))//当前区间右子区间以右端点结束连续1的个数等于右子区间长度，当前区间以右端点结束连续1的个数就应该计算上左子区间以右端点结束连续1的个数 
		lenr[id]=lenr[rn[id]]+lenr[ln[id]];
	else//否则当前区间以右端点结束连续1的个数就是当前区间以右子区间右端点结束连续1的个数 
		lenr[id]=lenr[rn[id]];
	return ;
}
void update_point(int pre,int id,int pos,int l,int r)
{
	ln[id]=ln[pre];rn[id]=rn[pre];lenl[id]=lenl[pre];lenr[id]=lenr[pre];lenmx[id]=lenmx[pre];
	if(l==r)
	{
		lenl[id]=lenr[id]=lenmx[id]=1;
		return ;
	}
	int mid=l+r>>1;
	if(pos<=mid) ln[id]=++idx,update_point(ln[pre],ln[id],pos,l,mid);
	else rn[id]=++idx,update_point(rn[pre],rn[id],pos,mid+1,r);
	pushup(id,l,r);
}
int query_interval(int id,int L,int R,int l,int r)
{
	if(l>=L&&r<=R) return lenmx[id];
	int mid=l+r>>1;
	int ans=0;
	if(L<=mid) ans=max(ans,query_interval(ln[id],L,R,l,mid));
	if(mid+1<=R) ans=max(ans,query_interval(rn[id],L,R,mid+1,r));
	ans=max(ans,min(lenr[ln[id]],/*左子区间长度*/mid-L+1)+min(lenl[rn[id]],/*右子区间长度*/R-mid));//把区间[L,R]分成两段，但是要保证计算连续1长度时不能包含区间[L,R]之外的部分，所以应该取最小值 
	return ans;
}
int main()
{
	int n;
	cin>>n;
	for(int i=1;i<=n;i++)
		scanf("%d",&p[i].h),p[i].id=i;
	sort(p+1,p+n+1,cmp);//按照高度进行排序 
	for(int i=1;i<=n;i++)
	{
		root[i]=++idx;
		update_point(root[i-1],root[i],p[i].id,1,n);//低版本的线段树中的高度是较高的 
	}
	int m;
	cin>>m;
	for(int i=1;i<=m;i++)
	{
		int l,r,len;
		scanf("%d%d%d",&l,&r,&len);
		int ll=1,rr=n;//二分线段树的版本 
		while(ll<rr)
		{
			int mid=ll+rr>>1;//低版本的线段树中的高度是较高的
			if(query_interval(root[mid],l,r,1,n)>=len) rr=mid;//所以当较高版本线段树中能够满足有连续len个1存在，应该降低线段树版本继续搜索 
			else ll=mid+1;
		}
		printf("%d\n",p[ll].h);//输出最终线段树版本对应插入的数 
	}
	return 0;
}