自行对照吧...
```
//分块3 区间加法+区间前驱
//将数列分成m块 m由均值不等式求得
//STL set即红黑树 可去重+自动排序
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<set>
using namespace std;
int n,a[100001],lazy[100001];
int belong[100001],l[100001],r[100001];//belong[i]指第i个数字所属的块下标 l[i],r[i]指第i块分块的左右端点下标
set<int> b[100001];
void reset(int x,int y)
{
b[belong[x]].erase(a[x]);
a[x]+=y;
b[belong[x]].insert(a[x]);
}
void build()
{
int sqt=sqrt(n);
int num=n/sqt;
if(n%sqt)
num++;
for(int i=1;i<=num;i++)
{
l[i]=(i-1)*sqt+1;
r[i]=i*sqt;
}
r[num]=n;
for(int i=1;i<=n;i++)
belong[i]=(i-1)/sqt+1;
for(int i=1;i<=n;i++)
b[belong[i]].insert(a[i]);
}
void add_update(int x,int y,int z)
{
if(belong[x]==belong[y])
{
for(int i=x;i<=y;i++)
reset(i,z);
return;
}
for(int i=x;i<=r[belong[x]];i++)
reset(i,z);
for(int i=belong[x]+1;i<=belong[y]-1;i++)
lazy[i]+=z;
for(int i=l[belong[y]];i<=y;i++)
reset(i,z);
}
int query(int x,int y,int z)
{
int ans=-1;
if(belong[x]==belong[y])
{
for(int i=x;i<=y;i++)
{
int f=a[i]+lazy[belong[i]];
if(f<z)
ans=max(ans,f);
}
return ans;
}
for(int i=x;i<=r[belong[x]];i++)
{
int f=a[i]+lazy[belong[i]];
if(f<z)
ans=max(ans,f);
}
for(int i=belong[x]+1;i<=belong[y]-1;i++)
{
set<int>::iterator g=b[i].lower_bound(z-lazy[i]);
if(g==b[i].begin())
continue;
g--;
ans=max(ans,*g+lazy[i]);
}
for(int i=l[belong[y]];i<=y;i++)
{
int f=a[i]+lazy[belong[i]];
if(f<z)
ans=max(ans,f);
}
return ans;
}
void do_something()
{
for(int i=1;i<=n;i++)
{
int k,u,v,w;
scanf("%d%d%d%d",&k,&u,&v,&w);
if(!k)
add_update(u,v,w);
else printf("%d\n",query(u,v,w));
}
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
build();
do_something();
return 0;
}
```
by radish布団 @ 2018-05-01 16:44:16