http://codeforces.com/problemset/problem/484/E
题意：
给定一个长度为n的数列，有m次询问，询问形如l r k
要你在区间[l,r]内选一个长度为k的区间，求区间最小数的最大值
整体二分啊。。。。O((n+m)log(n)log(值域))
对于一个询问，可以二分答案后（设二分出的答案为ans），将>=ans的数标记为1，<ans的数标记为0，然后求该询问区间内最长的连续且全为1的一段的长度x，如果x>=该询问要求的k则合法，否则不合法；
多次询问，发现可以整体二分
（如果带修改，貌似要可持久化一下整体二分中用的线段树？log^3？？）
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
struct Q
{
int type;
int l,r,x,num;
int pos,d;
}q[],qt1[],qt2[];
int n,m,ans[],len;
//二分答案后，将>=mid+1的数改为1，<mid+1的数改为0，判定区间最长连续1的长度是否>=k
namespace SegT
{
struct Info
{
int ld,rd,xd,sz;
bool a1;
}dat[];
Info operator+(const Info &a,const Info &b)
{
Info c;
c.a1=a.a1&&b.a1;c.sz=a.sz+b.sz;
c.ld=a.a1?a.sz+b.ld:a.ld;c.rd=b.a1?b.sz+a.rd:b.rd;
c.xd=max(a.rd+b.ld,max(a.xd,b.xd));
return c;
}
Info nn[]={{,,,,},{,,,,}};
int L,R,x;
#define mid (l+((r-l)>>1))
#define lc (num<<1)
#define rc (num<<1|1)
void build(int l,int r,int num)
{
if(l==r) {dat[num]=nn[];return;}
build(l,mid,lc);build(mid+,r,rc);
dat[num]=dat[lc]+dat[rc];
}
void _setx(int l,int r,int num)
{
if(l==r) {dat[num]=nn[x];return;}
if(L<=mid) _setx(l,mid,lc);
else _setx(mid+,r,rc);
dat[num]=dat[lc]+dat[rc];
}
Info _query(int l,int r,int num)
{
if(L<=l&&r<=R) return dat[num];
if(L<=mid&&mid<R) return _query(l,mid,lc)+_query(mid+,r,rc);
if(L<=mid) return _query(l,mid,lc);
if(mid<R) return _query(mid+,r,rc);
exit(-);
}
void setx(int l,int d)
{
L=l;x=d;_setx(,n,);
}
int query(int l,int r)
{
L=l;R=r;return _query(,n,).xd;
}
#undef mid
#undef lc
#undef rc
}
void solve(int lp,int rp,int l,int r)
{
if(lp>rp) return;
int i;
if(l==r)
{
for(i=lp;i<=rp;i++)
if(q[i].type==)
ans[q[i].num]=l;
return;
}
int mid=l+((r-l)>>),tlen1=,tlen2=;//qt1-->l,mid;qt2-->mid+1,r
for(i=lp;i<=rp;i++)
{
if(q[i].type==)
{
if(q[i].d>mid)
SegT::setx(q[i].pos,),qt2[++tlen2]=q[i];
else
qt1[++tlen1]=q[i];
}
else
{
if(SegT::query(q[i].l,q[i].r)>=q[i].x) qt2[++tlen2]=q[i];
else qt1[++tlen1]=q[i];
}
}
memcpy(q+lp,qt1+,sizeof(Q)*tlen1);
memcpy(q+lp+tlen1,qt2+,sizeof(Q)*tlen2);
solve(lp,lp+tlen1-,l,mid);
for(i=lp+tlen1;i<=rp;i++)
if(q[i].type==)
SegT::setx(q[i].pos,);
solve(lp+tlen1,rp,mid+,r);
}
int main()
{
int i,t;
scanf("%d",&n);
for(i=;i<=n;i++) scanf("%d",&t),q[++len].type=,q[len].pos=i,q[len].d=t;
scanf("%d",&m);
for(i=;i<=m;i++) q[++len].type=,scanf("%d%d%d",&q[len].l,&q[len].r,&q[len].x),q[len].num=i;
SegT::build(,n,);
solve(,len,,1e9);
for(i=;i<=m;i++) printf("%d\n",ans[i]);
return ;
}
貌似由于此题没有修改，可持久化线段树就是一个log了23333还是两个log，询问还是要二分答案的；可持久化线段树的做法大概是先离散化，然后将所有位置的值从小到大排序，建n棵线段树（当然共用了很多节点），第i棵线段树的第j位表示a[j]是(1)否(0)大于等于（所有n个数中）第i小的数（建法...应该是好建的，先不管了）；查询就二分答案（设二分出的答案为ans，注意离散化），在第ans棵线段树上对应区间查询最长连续全为1段的长度，判合法；