Codeforces 460C Present（二分+线段树）
题目大意：给你n个数，可以做出m次修改，每次修改一个长度为w的区间，给这区间每一个数字加一，问修改后数组中最小值的最大值。
思路：看到区间修改和十的五次方的数据范围，很难想不到线段树，再看到最小值的最大值，也很难不想到二分，那么就直接二分最后的答案，然后用线段树维护check即可。
AC程序：
//库省略
using namespace std;
const int maxn=100005;
const ll inf=1e13;
int w,n,m;
ll a[maxn];
ll tree[4*maxn],lazy[4*maxn];
void built(int k,int l,int r)
{
lazy[k]=0;
if(l>=r)
{
tree[k]=a[l];
return;
}
int mid=(l+r)>>1;
built(k*2,l,mid);
built(k*2+1,mid+1,r);
tree[k]=min(tree[k*2],tree[k*2+1]);
}
void pushdown(int now)
{
if(lazy[now]==0)
return;
int left=now<<1,right=now<<1|1;
tree[left]+=lazy[now];
tree[right]+=lazy[now];
lazy[left]+=lazy[now];
lazy[right]+=lazy[now];
lazy[now]=0;
}
ll ask(int tar,int now,int l,int r)
{
if(l==r)
{
return tree[now];
}
int mid=(l+r)>>1;
pushdown(now);
if(tar<=mid)
return ask(tar,now<<1,l,mid);
else
return ask(tar,now<<1|1,mid+1,r);
}
void change(ll val,int tl,int tr,int now,int l,int r)
{
if(tl<=l && r<=tr)
{
tree[now]+=val;
lazy[now]+=val;
return;
}
//cout<<"FINE11"<<endl;
pushdown(now);
//cout<<"FINE22"<<endl;
int mid=(l+r)>>1;
int left=now<<1,right=now<<1|1;
if(tl<=mid)
change(val,tl,tr,left,l,mid);
if(tr>mid)
change(val,tl,tr,right,mid+1,r);
tree[now]=min(tree[left],tree[right]);
}
bool check(ll num)
{
ll mm=m;
for(int i=1;i<=n;i++)
{
//cout<<"FINE1"<<endl;
ll now=ask(i,1,1,n);
if(now<num)
{
if(num-now>mm)
return 0;
else
{
//cout<<"FINE2"<<endl;
change(num-now,i,min(i+w-1,n),1,1,n);
mm-=num-now;
//cout<<"FINE3"<<endl;
}
}
}
return 1;
}
int main()
{
cin>>n>>m>>w;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
ll l=0,r=inf,mid;
while(l<r)
{
built(1,1,n);
//cout<<"YES"<<endl;
mid=r-(r-l)/2;
if(check(mid))
{
l=mid;
}
else
{
r=mid-1;
}
//cout<<"NO"<<endl;
}
cout<<l<<endl;
return 0;
}