发现最近碰到好多次二分结果的题目，上次多校也是，被我很机智的快速过了，这个思想确实非常不错。在正面求比较难处理的时候，二分结果再判断是否有效往往柳暗花明。
这个题目给定n个数字的序列，可以操作m次，每次要操作w个连续的数字，每次的操作将使得该段连续数字的数都+1，最后求整个序列最小值的最大值
求最小值最大，明显的二分结果的题目，我一开始还是在ACdream那个群里看到这个题，说是二分+线段树的题目，我就来做了一下。。首先二分部分很容易，下界就是初始序列的最小值，上界就是 下界+m，至于怎么判断这个就要想一下，我一开始还觉得不用线段树，因为我每次枚举完结果，对整个序列扫一遍，对不符合要求的数+到正好符号要求不就行了。
不过这个里面因为是要+连续一段，你普通的找到一个不符合条件的数，然后对他以及他之后的w-1个数都进行一次加法，很耗时啊，所以这个就是为什么要用线段树，其实我觉得用扫描线估计也可以，对某个起始点设置+1，起始点+w-1设置为-1，然后用个东西维护，++--的，估计也可以。反正最后用的线段树，普通的区间增，单点查询。
一开始还担心复杂度，不过还行的感觉，每次二分都要重新建树，这里就是 logN*N*logN,对二分结果进行判断，需要单点查询以及区间更新，这里是2*logN*logN，所以总的就是
logN*logN*（N+2)的复杂度，N最大为10的五次方，logN不超过20
#include <iostream>
#include <cstdio>
#include <cstring>
#define lson rt<<1,l,mid
#define rson rt<<1|1,mid+1,r
#define LL __int64
using namespace std;
const int N = 100000+10;
int n,m,w;
LL d[N<<2],flag[N<<2],A[N];
LL mini;
void up(int rt)
{
d[rt]=min(d[rt<<1],d[rt<<1|1]);
}
void build(int rt,int l,int r)
{
flag[rt]=0;
if (l>=r){
d[rt]=A[l];
//cout<<l<<" "<<A[l]<<endl;
return;
}
int mid=(l+r)>>1;
build(lson);
build(rson);
up(rt);
}
void pushdown(int rt,int l,int r)
{
if (flag[rt]==0) return;
d[rt<<1]+=flag[rt];
d[rt<<1|1]+=flag[rt];
flag[rt<<1]+=flag[rt];
flag[rt<<1|1]+=flag[rt];
flag[rt]=0;
}
LL query(int loc,int rt,int l,int r)
{
if (l==r) return d[rt];
int mid=(l+r)>>1;
pushdown(rt,l,r);
if (loc<=mid) return query(loc,lson);
else return query(loc,rson);
}
void update(LL val,int L,int R,int rt,int l,int r)
{
if (L<=l && r<=R){
d[rt]+=val;
flag[rt]+=val;
return;
}
pushdown(rt,l,r);
int mid=(l+r)>>1;
if (L<=mid) update(val,L,R,lson);
if (R>mid) update(val,L,R,rson);
up(rt);
}
bool judge(LL x)
{
LL tmp=m;
for (int i=1;i<=n;i++){
LL now=query(i,1,1,n);
// cout<<"Test "<<i<<endl;
// cout<<now<<endl;
if (now<x){
if (x-now>tmp) return 0;
else {
update(x-now,i,min(i+w-1,n),1,1,n);
tmp-=x-now;
}
}
}
return 1;
}
int main()
{
while (scanf("%d%d%d",&n,&m,&w)!=EOF)
{
mini=-1;
for (int i=1;i<=n;i++){
scanf("%I64d",&A[i]);
//cout<<i<<" "<<A[i]<<endl;
if (mini==-1) mini=A[i];
else mini=min(A[i],mini);
}
LL L=mini,R=mini+(LL)m,mid;
while (L<R){
build(1,1,n);
mid=R-(R-L)/2;
// cout<<L<<" "<<mid<<" "<<R<<endl;
if (judge(mid)) {L=mid;}
else {R=mid-1;}
}
printf("%I64d
",L);
}
return 0;
}