链接：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+10; int sum[M*40],lsum[M*40],rsum[M*40],ls[M*40],rs[M*40],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) >> 1; if(lsum[rt] == m-l+1) 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) >> 1; if(p <= m) update(ls[old],ls[rt],p,c,l,m); else update(rs[old],rs[rt],p,c,m+1,r); pushup(l,r,rt); } int query(int L,int R,int l,int r,int rt){ if(L > R) return 0; if(L == l&&R == r) return sum[rt]; int ret = 0; int m = (l + r) >> 1; if(R <= m) ret = query(L,R,l,m,ls[rt]); else if(L > m) ret = query(L,R,m+1,r,rs[rt]); else{ ret = max(query(L,m,l,m,ls[rt]),query(m+1,R,m+1,r,rs[rt])); int lx = min(rsum[ls[rt]],m-L+1); 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 = 0; root[n+1] = 0; for(int i = 1;i <= n;i ++) scanf("%d",&a[i].x),a[i].id = i; sort(a+1,a+1+n); for(int i = n;i >= 1;i --) update(root[i+1],root[i],a[i].id,1,1,n); scanf("%d",&q); for(int i = 1;i <= q;i ++){ scanf("%d%d%d",&x,&y,&w); int l = 1,r = n,ans = n; while(l <= r){ int m = (l + r) >> 1; int num = query(x,y,1,n,root[m]); if(num >= w) l = m+1,ans = m; else r = m - 1; } printf("%d ",a[ans].x); } return 0; }