链接：http://codeforces.com/contest/484/problem/E
题意：
给你n个数的，每个数代表高度；
再给出m个询问，每次询问[l,r]区间内连续w个数的最大的最小值；
思路：
因为查询的到的值一定是输入的其中一个，那么我们可以二分答案，判断二分得到的答案是否符合，那么在这里我们就只需要找到某个数x，查询区间[l,r]有多少个连续的数大于x，这个操作只需要将高度从小到达排序，倒着插入主席树中，值设为1，那么只要维护有多少个连续的1（线段树区间合并的方法），就代表有多少个大于x的连续的数，如果查询到的数大于w，那么就查更大的数并更新答案，如果小于w的话，就找更小的数。
之前写过倒着插入的主席树，二分答案的线段树，这次合在一起了。。。。
实现代码：
#include<bits/stdc++.h>
using namespace std;
const int M = 1e5+;
int sum[M*],lsum[M*],rsum[M*],ls[M*],rs[M*],root[M];
int idx;
struct node{
int x,id;
bool operator < (const node k) const{
if(x == k.x) return id < k.id;
return x < k.x;
}
}a[M]; void pushup(int l,int r,int rt){
lsum[rt] = lsum[ls[rt]];
rsum[rt] = rsum[rs[rt]];
int m = (l + r) >> ;
if(lsum[rt] == m-l+) lsum[rt] += lsum[rs[rt]];
if(rsum[rt] == r - m) rsum[rt] += rsum[ls[rt]];
sum[rt] = max(lsum[rs[rt]]+rsum[ls[rt]],max(sum[ls[rt]],sum[rs[rt]]));
} void update(int old,int &rt,int p,int c,int l,int r){
rt = ++idx; ls[rt] = ls[old]; rs[rt] = rs[old];
sum[rt] = sum[old];
if(l == r) {
lsum[rt] = sum[rt] = rsum[rt] = c;
return ;
}
int m = (l + r) >> ;
if(p <= m) update(ls[old],ls[rt],p,c,l,m);
else update(rs[old],rs[rt],p,c,m+,r);
pushup(l,r,rt);
} int query(int L,int R,int l,int r,int rt){
if(L > R) return ;
if(L == l&&R == r) return sum[rt];
int ret = ;
int m = (l + r) >> ;
if(R <= m) ret = query(L,R,l,m,ls[rt]);
else if(L > m) ret = query(L,R,m+,r,rs[rt]);
else{
ret = max(query(L,m,l,m,ls[rt]),query(m+,R,m+,r,rs[rt]));
int lx = min(rsum[ls[rt]],m-L+);
int rx = min(lsum[rs[rt]],R - m);
ret = max(ret,lx+rx);
}
return ret;
} int main()
{
int n,q,x,y,w;
scanf("%d",&n);
idx = ; root[n+] = ;
for(int i = ;i <= n;i ++) scanf("%d",&a[i].x),a[i].id = i;
sort(a+,a++n);
for(int i = n;i >= ;i --) update(root[i+],root[i],a[i].id,,,n);
scanf("%d",&q);
for(int i = ;i <= q;i ++){
scanf("%d%d%d",&x,&y,&w);
int l = ,r = n,ans = n;
while(l <= r){
int m = (l + r) >> ;
int num = query(x,y,,n,root[m]);
if(num >= w) l = m+,ans = m;
else r = m - ;
}
printf("%d\n",a[ans].x);
}
return ;
}