分块（模板）

题目：数列分块入门 3 参考博客

分块也是对区间操作 虽然没有树状数组快但是什么都能维护

未闻花名，但识花香
#include<bits/stdc++.h>
using namespace std;
namespace{
	template<typename T>
	inline void read(T &s){
		T f=1;s=0;char ch=getchar();
		for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
		for(;isdigit(ch);ch=getchar()) s=(s<<1)+(s<<3)+(ch^48);
		s*=f;
	}
} 

#define ll long long
#define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
int const N=1e5+7;  //
int const M=1007;
ll INF=0x3f3f3f3f3f3f3f3f;
int n,len,cnt,bl[M];
ll a[N],ly[N];
vector<ll>v[M];
void pushup(int& z){
	v[z].clear();
	for(int i=len*(z-1)+1;i<=len*z;++i){  //i<=n&&
		v[z].push_back(a[i]);
	}
	sort(v[z].begin(),v[z].end());
}
void add(int& l,int& r,int& k){
	int z=min(bl[l]*len,r);
	for(int i=l;i<=z;++i){
		a[i]+=k;
	}
	pushup(bl[l]);
	if(bl[l]!=bl[r]){
		for(int i=len*(bl[r]-1)+1;i<=r;++i){
			a[i]+=k;
		}
		pushup(bl[r]);
	}
	for(int i=bl[l]+1;i<bl[r];++i) ly[i]+=k;
}
ll ask(int& l,int& r,int& c){
	ll ans=-INF;
	int z=min(bl[l]*len,r);
	for(int i=l;i<=z;++i){
		if(a[i]+ly[bl[i]]<c) ans=max(ans,a[i]+ly[bl[i]]);
	}
	if(bl[l]!=bl[r]){
		for(int i=(bl[r]-1)*len+1;i<=r;++i){
			if(a[i]+ly[bl[i]]<c) ans=max(ans,a[i]+ly[bl[i]]);
		}
	}
	for(int i=bl[l]+1;i<bl[r];++i){
		if(v[i][0]+ly[i]>=c) continue;
		int z=lower_bound(v[i].begin(),v[i].end(),c-ly[i])-v[i].begin();
		ans=max(ans,v[i][z-1]+ly[i]);
	}
	return ans;
}

int main(){
	//fio;
	read(n);len=sqrt(n); //每个块的个数 
	for(int i=1;i<=n;++i){
		//cin >> a[i];
		read(a[i]);
		bl[i]=ceil(1.0*i/len);
		v[bl[i]].push_back(a[i]);
		if(i%len==1) cnt++;
	}
	for(int i=1;i<=cnt;++i) sort(v[i].begin(),v[i].end());	
	int op,l,r,c;
	for(int i=1;i<=n;++i){
		//cin >> op >> l >> r >> c;
		read(op);read(l);read(r);read(c);
		if(op==0) add(l,r,c);
		else if(op==1){
			ll ans=ask(l,r,c);
			if(ans==-INF) cout << "-1\n";
			else cout << ans << "\n";
		}
	} 
	return 0;
} 
//思考：第八大区间是否也可以用分块