Sign on Fence（连续的长为W的一段中最小的数字的最大值）

题目链接：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+;

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*];

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=;

        tree[cur].right=;

        tree[cur].sum=;

        tree[cur].len=;

        return ;

    }

    int m=(l+r)>>;

    build(tree[cur].l,l,m);

    build(tree[cur].r,m+,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=;

        tree[now].right=;

        tree[now].sum=;

        tree[now].len=;

        return ;

    }

    int m=(l+r)>>;

    if(tar<=m)

        update(tree[now].l,tree[last].l,l,m,tar);

    else

        update(tree[now].r,tree[last].r,m+,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)>>;

    if(R<=m)

    return query(tree[now].l,L,R,l,m);

    if(L>m)

    return query(tree[now].r,L,R,m+,r);

    int res=;

    res=max(query(tree[now].l,L,R,l,m),query(tree[now].r,L,R,m+,r));

    int ll=min(tree[tree[now].l].right,m-L+);

    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=;

    scanf("%d",&n);

    for(int i=;i<=n;i++)

    {

        scanf("%d",&a[i].val);

        a[i].id=i;

    }

    sort(a+,a++n,cmp);

    build(root[],,n);

    for(int i=;i<=n;i++)

        update(root[i],root[i-],,n,a[i].id);

    scanf("%d",&m);

    int ans=;

    while(m--)

    {

        int l,r,w;

        scanf("%d%d%d",&l,&r,&w);

        int ll=,rr=n;

        while(ll<=rr)

        {

            int mid=(ll+rr)>>;

            int res=query(root[mid],l,r,,n);

            if(res>=w)

            {

                ans=mid;

                rr=mid-;

            }

            else ll=mid+;

        }

        printf("%d\n",a[ans].val);

    }

    return ;

}