题目链接：http://codeforces.com/problemset/problem/484/E
题意：给你个n，n个木板都有高度，宽度都为1 ，给你两个数[l,r]和一个w，求在[l,r]区间的木板里宽度w的最大值，也就是连续的长为W的一段中最小的数字的最大值。
思路：首先想到了二分，找高度，然后就是如果对于每个木板高度，我们把大于等于i木板高度的线段树叶子设为1，其他为0，那么就肯定对于一个高度最长连续的1的值也就是维护一个线段树的和如果大于W
那么就肯定是可行的。所以是个求线段树中最长的连续的1的长度是多少的问题，这个问题要维护线段树的左边连续和,右边连续和,连续和的最大值。对高度从大到小排序，依次分别插入到n颗线段树中形成可持久化线段树（主席树），就能节省许多空间复杂度。维护起来 比较麻烦，好繁琐。。。
#include<cstdio> #include<cstring> #include<queue> #include<cmath> #include<algorithm> #include<map> #include<vector> #include<string> #include<set> #define ll long long using namespace std; const int maxn=1e5+100; int root[maxn],cnt; struct Node{ int val; int id; }a[maxn]; struct node{ int l; int r; int len; int left; int right; int sum; }tree[maxn*40]; void pushup(int cur) { tree[cur].len=tree[tree[cur].l].len+tree[tree[cur].r].len; tree[cur].left=tree[tree[cur].l].left; if(tree[tree[cur].l].left==tree[tree[cur].l].len) tree[cur].left+=tree[tree[cur].r].left; tree[cur].right=tree[tree[cur].r].right; if(tree[tree[cur].r].right==tree[tree[cur].r].len) tree[cur].right+=tree[tree[cur].l].right; tree[cur].sum=max(tree[tree[cur].l].sum,tree[tree[cur].r].sum); tree[cur].sum=max(tree[cur].sum,tree[tree[cur].l].right+tree[tree[cur].r].left); } void build(int &cur,int l,int r) { cur=++cnt; if(l==r) { tree[cur].left=0; tree[cur].right=0; tree[cur].sum=0; tree[cur].len=1; return ; } int m=(l+r)>>1; build(tree[cur].l,l,m); build(tree[cur].r,m+1,r); pushup(cur); } void update(int &now,int last,int l,int r,int tar) { tree[++cnt]=tree[last]; now=cnt; if(l==r) { tree[now].left=1; tree[now].right=1; tree[now].sum=1; tree[now].len=1; return ; } int m=(l+r)>>1; if(tar<=m) update(tree[now].l,tree[last].l,l,m,tar); else update(tree[now].r,tree[last].r,m+1,r,tar); pushup(now); } int query(int now,int L,int R,int l,int r) { if(L<=l&&r<=R) return tree[now].sum; int m=(l+r)>>1; if(R<=m) return query(tree[now].l,L,R,l,m); if(L>m) return query(tree[now].r,L,R,m+1,r); int res=0; res=max(query(tree[now].l,L,R,l,m),query(tree[now].r,L,R,m+1,r)); int ll=min(tree[tree[now].l].right,m-L+1); int rr=min(tree[tree[now].r].left,R-m); res=max(res,ll+rr); return res; } bool cmp(Node x,Node y) { return x.val>y.val; } int main() { int n,m; cnt=0; scanf("%d",&n); for(int i=1;i<=n;i++) { scanf("%d",&a[i].val); a[i].id=i; } sort(a+1,a+1+n,cmp); build(root[0],1,n); for(int i=1;i<=n;i++) update(root[i],root[i-1],1,n,a[i].id); scanf("%d",&m); int ans=0; while(m--) { int l,r,w; scanf("%d%d%d",&l,&r,&w); int ll=1,rr=n; while(ll<=rr) { int mid=(ll+rr)>>1; int res=query(root[mid],l,r,1,n); if(res>=w) { ans=mid; rr=mid-1; } else ll=mid+1; } printf("%d ",a[ans].val); } return 0; }