震惊，蒟蒻 Midoria7 居然在 1949 年终于写完了分块入门，活到爆！
分块是一种很暴力很优雅的数据结构。秉承散点暴力，大块整体的原则，能以根号级别复杂度优化很多的暴力。
以下由于都是隔了很长时间写的，所以码风有可能有变。
数列分块入门 1区间加法，单点查询。
小点暴力修改，大块打标记。（由于我太懒所以把区间修改区间查询复制过来了）
#include <bits/stdc++.h> using namespace std; const int maxn=5e4+10; int n,S; int a[maxn]; inline int read(){ int x=0,fopt=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')fopt=-1;ch=getchar();} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();} return x*fopt; } int sum[maxn],siz[maxn],L[maxn],R[maxn],belong[maxn],tag[maxn]; inline void Init(){ S=sqrt(n); for(int i=1;i<=n;i++){ belong[i]=(i-1)/S+1; siz[belong[i]]++; sum[belong[i]]+=a[i]; if(!L[belong[i]])L[belong[i]]=i; R[belong[i]]=i; } } inline void add(int Lu,int Ru,int v){ if(belong[Lu]==belong[Ru]){ sum[belong[Lu]]+=(Ru-Lu+1)*v; for(int i=Lu;i<=Ru;i++) a[i]+=v; }else{ add(Lu,R[belong[Lu]],v); add(L[belong[Ru]],Ru,v); for(int i=belong[Lu]+1;i<belong[Ru];i++){ tag[i]+=v; sum[i]+=siz[i]*v; } } } inline int query(int Lu,int Ru){ int ans=0; if(belong[Lu]==belong[Ru]){ ans+=(Ru-Lu+1)*tag[belong[Lu]]; for(int i=Lu;i<=Ru;i++) ans+=a[i]; }else{ ans+=query(Lu,R[belong[Lu]]); ans+=query(L[belong[Ru]],Ru); for(int i=belong[Lu]+1;i<belong[Ru];i++) ans+=sum[i]; } return ans; } int main(){ n=read(); for(int i=1;i<=n;i++) a[i]=read(); Init(); for(int i=1;i<=n;i++){ int opt=read(),l=read(),r=read(),c=read(); if(opt==0){ add(l,r,c); }else{ printf("%d\n",query(r,r)); } } return 0; } 数列分块入门 2区间加法，询问区间内小于某个值的元素个数。
用归并排序维护块内的单调性，查询直接 lower_bound。散点暴力统计即可。
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn=5e4+10; int n,S; int a[maxn],c[maxn]; inline int read(){ int x=0,fopt=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')fopt=-1;ch=getchar();} while(isdigit(ch)){x=(x<<3)+(x<<1)+ch-48;ch=getchar();} return x*fopt; } inline bool Cmp(int x,int y){ return a[x]<a[y]; } int sum[maxn],siz[maxn],L[maxn],R[maxn],belong[maxn],tag[maxn]; inline void Init(){ S=sqrt(n); for(int i=1;i<=n;i++){ belong[i]=(i-1)/S+1; siz[belong[i]]++; if(!L[belong[i]])L[belong[i]]=i; R[belong[i]]=i; c[i]=i; } for(int i=1;i<=belong[n];i++) sort(c+L[i],c+R[i]+1,Cmp); } inline void add(int Lu,int Ru,int v){ if(belong[Lu]==belong[Ru]){ for(int i=Lu;i<=Ru;i++) a[i]+=v; vector<int> A,B; for(int i=L[belong[Lu]];i<=R[belong[Lu]];i++) if(c[i]>=Lu&&c[i]<=Ru)A.push_back(c[i]); else B.push_back(c[i]); int p1=L[belong[Lu]],p2=0,p3=0; while(p2<A.size()&&p3<B.size()) a[A[p2]]<a[B[p3]]?(c[p1++]=A[p2++]):(c[p1++]=B[p3++]); while(p2<A.size())c[p1++]=A[p2++]; while(p3<B.size())c[p1++]=B[p3++]; }else{ add(Lu,R[belong[Lu]],v); add(L[belong[Ru]],Ru,v); for(int i=belong[Lu]+1;i<belong[Ru];i++){ tag[i]+=v; } } } inline int query(int Lu,int Ru,int v){ int ans=0; if(belong[Lu]==belong[Ru]){ for(int i=Lu;i<=Ru;i++) if(a[i]+tag[belong[Lu]]<v)ans++; }else{ ans+=query(Lu,R[belong[Lu]],v); ans+=query(L[belong[Ru]],Ru,v); for(int i=belong[Lu]+1;i<belong[Ru];i++){ a[0]=v-tag[i]; ans+=lower_bound(c+L[i],c+R[i]+1,0,Cmp)-c-L[i]; } } return ans; } signed main(){ n=read(); for(int i=1;i<=n;i++) a[i]=read(); Init(); for(int i=1;i<=n;i++){ int opt=read(),l=read(),r=read(),x=read(); if(opt==0){ add(l,r,x); }else{ printf("%lld\n",query(l,r,x*x)); } } return 0; } 数列分块入门 3区间加法，查找前驱。
震惊，这不是 set 吗。大块直接 lower_bound，修改就先删掉，再插入即可。散点依然暴力找。
#include <bits/stdc++.h> #define int long long using namespace std; const int maxn=1e5+10; int n,S; int a[maxn],belong[maxn],tag[maxn]; set<int> tree[1000+10]; inline int read(){ int x=0;bool fopt=1;char ch=getchar(); for(;!isdigit(ch);ch=getchar())if(ch=='-')fopt=0; for(;isdigit(ch);ch=getchar())x=(x<<3)+(x<<1)+ch-48; return fopt?x:-x; } inline void modify(int l,int r,int c){ for(int i=l;i<=min(belong[l]*S,r);i++){ tree[belong[l]].erase(a[i]); a[i]+=c; tree[belong[l]].insert(a[i]);//先删后加 } if(belong[l]!=belong[r]){ for(int i=(belong[r]-1)*S+1;i<=r;i++){ tree[belong[r]].erase(a[i]); a[i]+=c; tree[belong[r]].insert(a[i]); } } for(int i=belong[l]+1;i<belong[r];i++) tag[i]+=c; } inline int Findsucc(int l,int r,int c){ int ans=-1; for(int i=l;i<=min(belong[l]*S,r);i++){ int sum=a[i]+tag[belong[l]]; if(sum<c)ans=max(ans,sum); } if(belong[l]!=belong[r]){ for(int i=(belong[r]-1)*S+1;i<=r;i++){ int sum=a[i]+tag[belong[r]]; if(sum<c)ans=max(ans,sum); } } for(int i=belong[l]+1;i<belong[r];i++){ int temp=c-tag[i]; set<int>::iterator it=tree[i].lower_bound(temp); if(it==tree[i].begin())continue; //因为lower_bound会指向大于等于的数，所以前驱就--it即可。 it--; ans=max(ans,*it+tag[i]); } return ans; } signed main(){ n=read();S=sqrt(n); for(int i=1;i<=n;i++) a[i]=read(); for(int i=1;i<=n;i++){ belong[i]=(i-1)/S+1; tree[belong[i]].insert(a[i]); } for(int i=1;i<=n;i++){ int opt=read(),l=read(),r=read(),c=read(); if(opt==0){ modify(l,r,c); }else{ printf("%lld\n",Findsucc(l,r,c)); } } return 0; } 数列分块入门 4区间加法，区间查询。