分块学习笔记

引入

分块，顾名思义，把需要的维护的数据分成多个块来维护，思想为大段维护，小段朴素。

区间修改，区间求和是一道线段树的板子，其复杂度为 \(O(n\log n)\)，考虑分块如何做。

将序列分块，然后对于操作来说，中间的块直接查询和，然后将两边剩余的加起来即可。复杂度最优为 \(O(n\sqrt n)\)，不难证明。

#include<bits/stdc++.h>
inline int read(){
	int x=0,f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar())if(ch=='-')f=-1;
	for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+(ch^48);
	return x*f;
}
#define ll long long
#define int long long
const int N=5e4+10;
int mark[N],id[N],n,a[N],len,s[500];
inline void modify(int l,int r,int c){
	int be=id[l],en=id[r];
	if(be==en){
		for(int i=l;i<=r;++i)a[i]+=c,s[be]+=c;
		return;
	}
	for(int i=l;id[i]==be;++i)a[i]+=c,s[be]+=c;
	for(int i=be+1;i<en;++i)s[i]+=len*c,mark[i]+=c;
	for(int i=r;id[i]==en;--i)a[i]+=c,s[en]+=c;
}
inline ll query(int l,int r,ll p){
	ll ans=0;
	int be=id[l],en=id[r];
	if(be==en){
		for(int i=l;i<=r;++i)ans=(ans+a[i]+mark[be])%p;
		return ans;
	}
	for(int i=l;id[i]==be;++i)ans=(ans+a[i]+mark[be])%p;
	for(int i=be+1;i<en;++i)ans=(ans+s[i])%p;
	for(int i=r;id[i]==en;--i)ans=(ans+a[i]+mark[en])%p;
	return ans;
}
main(){
	// freopen("in.in","r",stdin);freopen("out.out","w",stdout);
	n=read(),len=std::sqrt(n);
	for(int i=1;i<=n;++i){
		a[i]=read();
		id[i]=(i-1)/len+1;
		s[id[i]]+=a[i];
	}
	for(int i=1,opt,l,r,c;i<=n;++i){
		opt=read(),l=read(),r=read(),c=read();
		if(opt)std::cout<<query(l,r,c+1)<<'\n';
		else modify(l,r,c);
	}
}