前言
这玩意儿也太妙了！！
一、内容
对于 n 长度的数组，考虑将其平均划分为块，那么就有块数和每个块内的长度都是
的级别，所以此时就能实现遍历所有块和块内遍历一遍的复杂度都是
的了。
在维护信息时，块内就可以暴力维护，整块直接修改标签即可。那么在处理时，就只需要对左右散块暴力，中间块遍历即可。
二、适用场景
当区间信息不可合并或者很难合并时，那么就无法使用线段树了。而此时往往分块比较容易解决，因为块内信息是暴力维护的。除此之外，分块在思维上比其他正解是要好想的，在想不到正解的时候可以考虑分块暴力草（）
三、题目
1. Give Away
#include<bits/stdc++.h> using namespace std; /* /\_/\ * (= ._.) * / > \> */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl '\n' #define dbg(x) cout<<#x<<endl;cout<<x<<endl; #define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl; #define YES cout<<"YES"<<endl;return ; #define Yes cout<<"Yes"<<endl;return ; #define NO cout<<"NO"<<endl;return ; #define No cout<<"No"<<endl;return ; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int INF=1e9; const ll INFLL=1e18; const int dx[]={-1,1,0,0}; const int dy[]={0,0,-1,1}; const int ddx[]={-2,-1,1,2,2,1,-1,-2}; const int ddy[]={1,2,2,1,-1,-2,-2,-1}; void solve() { int n; cin>>n; vector<int>a(n+1); for(int i=1;i<=n;i++) { cin>>a[i]; } int blen=sqrt(n); int bnum=(n+blen-1)/blen; vector<int>bi(n+1); for(int i=1;i<=n;i++) { bi[i]=(i-1)/blen+1; } vector<int>bl(blen+1); vector<int>br(blen+1); for(int i=1;i<=bnum;i++) { bl[i]=(i-1)*blen+1; br[i]=min(i*blen,n); } vector<int>sorted(n+1); for(int i=1;i<=n;i++) { sorted[i]=a[i]; } for(int i=1;i<=bnum;i++) { sort(sorted.begin()+bl[i],sorted.begin()+br[i]+1); } auto bs=[&](int i,int v)->int { int l=bl[i]; int r=br[i]; int m; int ans=r+1; while(l<=r) { m=l+r>>1; if(sorted[m]>=v) { ans=m; r=m-1; } else { l=m+1; } } return br[i]-ans+1; }; auto query=[&](int l,int r,int v)->int { if(bi[l]==bi[r]) { int ans=0; for(int i=l;i<=r;i++) { if(a[i]>=v) { ans++; } } return ans; } int ans=0; for(int i=l;i<=br[bi[l]];i++) { if(a[i]>=v) { ans++; } } for(int i=bi[l]+1;i<=bi[r]-1;i++) { ans+=bs(i,v); } for(int i=bl[bi[r]];i<=r;i++) { if(a[i]>=v) { ans++; } } return ans; }; auto update=[&](int p,int v)->void { int l=bl[bi[p]]; int r=br[bi[p]]; a[p]=v; for(int i=l;i<=r;i++) { sorted[i]=a[i]; } sort(sorted.begin()+l,sorted.begin()+r+1); }; int m; cin>>m; int op,i,x,l,r,v; while(m--) { cin>>op; if(op==0) { cin>>l>>r>>v; cout<<query(l,r,v)<<endl; } else { cin>>i>>x; update(i,x); } } } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t=1; //cin>>t; init(); while(t--) { solve(); } return 0; }对于单点修改操作，直接去每个位置修改即可。对于区间查询大于等于 v 的个数操作，考虑每次单点修改后，对这个块排序，那么单点修改的复杂度就是的了。那么在保证每个块内有序后，对于一个区间，中间被完全包含的块就可以暴力枚举，每次通过二分查找大于等于 v 的个数。而对于这个区间左右剩下的散点，因为每个块的大小也是
的，所以可以直接去暴力计算大于等于 v 的个数。那么两个操作的复杂度，就都是
的了。
实现时，考虑定义 blen 为每个块的长度，bnum 为块数，注意要向上取整。再定义为 i 位置所在的块的编号，
和
分别为第 i 个块的左右边界。在查询时，注意若区间在同一个块里，那么就直接暴力遍历即可。
2. 教主的魔法
#include <bits/stdc++.h> using namespace std; /* /\_/\ * (= ._.) * / > \> */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl '\n' #define dbg(x) cout<<#x<<endl;cout<<x<<endl; #define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl; #define YES cout<<"YES"<<endl;return ; #define Yes cout<<"Yes"<<endl;return ; #define NO cout<<"NO"<<endl;return ; #define No cout<<"No"<<endl;return ; typedef long long ll; typedef long double ld; typedef pair<int,int> pii; typedef pair<ll,ll> pll; const int INF=1e9; const ll INFLL=1e18; const int dx[]={-1,1,0,0}; const int dy[]={0,0,-1,1}; const int ddx[]={-2,-1,1,2,2,1,-1,-2}; const int ddy[]={1,2,2,1,-1,-2,-2,-1}; void solve() { int n,q; cin>>n>>q; vector<ll>a(n+1); for(int i=1;i<=n;i++) { cin>>a[i]; } int blen=sqrt(n); int bnum=(n+blen-1)/blen; vector<int>bi(n+1); for(int i=1;i<=n;i++) { bi[i]=(i-1)/blen+1; } vector<int>bl(bnum+1); vector<int>br(bnum+1); for(int i=1;i<=bnum;i++) { bl[i]=(i-1)*blen+1; br[i]=min(n,i*blen); } vector<int>sorted(n+1); for(int i=1;i<=n;i++) { sorted[i]=a[i]; } for(int i=1;i<=bnum;i++) { sort(sorted.begin()+bl[i],sorted.begin()+br[i]+1); } vector<ll>lazy(bnum+1); auto bs=[&](int i,int v)->int { int l=bl[i]; int r=br[i]; int m; int ans=r+1; while(l<=r) { m=l+r>>1; if(sorted[m]>=v) { ans=m; r=m-1; } else { l=m+1; } } return br[i]-ans+1; }; auto add=[&](int l,int r,int v)->void { if(bi[l]==bi[r]) { for(int i=l;i<=r;i++) { a[i]+=v; } for(int i=bl[bi[l]];i<=br[bi[l]];i++) { sorted[i]=a[i]; } sort(sorted.begin()+bl[bi[l]],sorted.begin()+br[bi[l]]+1); return ; } for(int i=l;i<=br[bi[l]];i++) { a[i]+=v; } for(int i=bl[bi[l]];i<=br[bi[l]];i++) { sorted[i]=a[i]; } sort(sorted.begin()+bl[bi[l]],sorted.begin()+br[bi[l]]+1); for(int i=bi[l]+1;i<=bi[r]-1;i++) { lazy[i]+=v; } for(int i=bl[bi[r]];i<=r;i++) { a[i]+=v; } for(int i=bl[bi[r]];i<=br[bi[r]];i++) { sorted[i]=a[i]; } sort(sorted.begin()+bl[bi[r]],sorted.begin()+br[bi[r]]+1); }; auto query=[&](int l,int r,int v)->int { if(bi[l]==bi[r]) { int ans=0; for(int i=l;i<=r;i++) { if(a[i]>=v-lazy[bi[l]]) { ans++; } } return ans; } int ans=0; for(int i=l;i<=br[bi[l]];i++) { if(a[i]>=v-lazy[bi[l]]) { ans++; } } for(int i=bi[l]+1;i<=bi[r]-1;i++) { ans+=bs(i,v-lazy[i]); } for(int i=bl[bi[r]];i<=r;i++) { if(a[i]>=v-lazy[bi[r]]) { ans++; } } return ans; }; char op;int l,r,v; while(q--) { cin>>op>>l>>r>>v; if(op=='M') { add(l,r,v); } else { cout<<query(l,r,v)<<endl; } } } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t=1; //cin>>t; init(); while(t--) { solve(); } return 0; }和上个题很类似，就是单点修改改成区间增加了。那么和线段树的处理方法类似，设置一个懒信息数组 lazy，每次区间增加时，对于左右的散点暴力，中间的块直接增加懒信息。在区间查询的时候，块内查询大于等于 v-lazy 的个数即可。
3. 蒲公英
#include <bits/stdc++.h> using namespace std; /* /\_/\ * (= ._.) * / > \> */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl '\n' #define dbg(x) cout<<#x<<" "<<x<<endl; #define vdbg(a) cout<<#a<<endl;for(auto x:a)cout<<x<<" ";cout<<endl; #define YES cout<<"YES"<<endl;return ; #define Yes cout<<"Yes"<<endl;return ; #define NO cout<<"NO"<<endl;return ; #define No cout<<"No"<<endl;return ; #define popcount __builtin_popcount using ll=long long; using i128=__int128; using ld=long double; using pii=pair<int,int>; using pll=pair<ll,ll>; const int INF=1e9; const ll INFLL=1e18; const int dx[]={-1,1,0,0}; const int dy[]={0,0,-1,1}; const int ddx[]={-2,-1,1,2,2,1,-1,-2}; const int ddy[]={1,2,2,1,-1,-2,-2,-1}; void solve() { int n,q; cin>>n>>q; vector<int>a(n+1); for(int i=1;i<=n;i++) { cin>>a[i]; } vector<int>sorted=a; sort(sorted.begin()+1,sorted.end()); int len=1; for(int i=2;i<=n;i++) { if(sorted[len]!=sorted[i]) { sorted[++len]=sorted[i]; } } auto rnk=[&](int v)->int { int l=1; int r=len; int m; int ans; while(l<=r) { m=l+r>>1; if(sorted[m]>=v) { ans=m; r=m-1; } else { l=m+1; } } return ans; }; for(int i=1;i<=n;i++) { a[i]=rnk(a[i]); } int blen=sqrt(n); int bnum=(n+blen-1)/blen; vector<int>bi(n+1); for(int i=1;i<=n;i++) { bi[i]=(i-1)/blen+1; } vector<int>bl(bnum+1); vector<int>br(bnum+1); for(int i=1;i<=bnum;i++) { bl[i]=(i-1)*blen+1; br[i]=min(n,i*blen); } vector<vector<int>>freq(bnum+1,vector<int>(len+1)); for(int i=1;i<=bnum;i++) { for(int j=1;j<=len;j++) { freq[i][j]=freq[i-1][j]; } for(int j=bl[i];j<=br[i];j++) { freq[i][a[j]]++; } } vector<vector<int>>mode(bnum+1,vector<int>(bnum+1)); for(int i=1;i<=bnum;i++) { for(int j=i;j<=bnum;j++) { int most=mode[i][j-1]; int mostCnt=freq[j][most]-freq[i-1][most]; for(int k=bl[j];k<=br[j];k++) { int cur=a[k]; int curCnt=freq[j][cur]-freq[i-1][cur]; if(curCnt>mostCnt||(curCnt==mostCnt&&cur<most)) { most=cur; mostCnt=curCnt; } } mode[i][j]=most; } } vector<int>cnts(len+1); int l,r; int pre=0; while(q--) { cin>>l>>r; l=(l+pre-1)%n+1; r=(r+pre-1)%n+1; if(l>r) { swap(l,r); } if(bi[l]==bi[r]) { for(int i=l;i<=r;i++) { cnts[a[i]]++; } int most=0; for(int i=l;i<=r;i++) { if(cnts[a[i]]>cnts[most]||(cnts[a[i]]==cnts[most]&&a[i]<most)) { most=a[i]; } } pre=sorted[most]; cout<<pre<<endl; for(int i=l;i<=r;i++) { cnts[a[i]]=0; } continue; } for(int i=l;i<=br[bi[l]];i++) { cnts[a[i]]++; } for(int i=bl[bi[r]];i<=r;i++) { cnts[a[i]]++; } int most=mode[bi[l]+1][bi[r]-1]; int mostCnt=freq[bi[r]-1][most]-freq[bi[l]][most]; for(int i=l;i<=br[bi[l]];i++) { int cur=a[i]; int curCnt=cnts[cur]+freq[bi[r]-1][cur]-freq[bi[l]][cur]; if(curCnt>mostCnt||(curCnt==mostCnt&&cur<most)) { most=cur; mostCnt=curCnt; } } for(int i=bl[bi[r]];i<=r;i++) { int cur=a[i]; int curCnt=cnts[cur]+freq[bi[r]-1][cur]-freq[bi[l]][cur]; if(curCnt>mostCnt||(curCnt==mostCnt&&cur<most)) { most=cur; mostCnt=curCnt; } } pre=sorted[most]; cout<<pre<<endl; for(int i=l;i<=br[bi[l]];i++) { cnts[a[i]]=0; } for(int i=bl[bi[r]];i<=r;i++) { cnts[a[i]]=0; } } } /* 6 3 1 2 3 2 1 2 1 5 3 6 1 5 1 2 1 */ void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t=1; //cin>>t; init(); while(t--) { solve(); } return 0; }对于众数这个问题，首先可以考虑维护 freq[i][j] 表示前 i 块里 j 这个数出现的次数，即一个前缀词频。之后，再维护一个 mode[i][j] 表示第 i 块到第 j 块之间的最小众数。那么对于查询，中间的整块就可以使用这两个数组查出众数和词频。然后对于两边的散块，就可以暴力统计词频，判断是否大于中间这个众数即可。
构建时，freq 数组就是正常统计前缀词频即可。对于 mode 数组，就是每次先找出 i 到 j-1 块的众数和词频，然后在遍历当前块的时候，对于块内的每个数判断其区间词频是否可以更新众数即可。
总结
分块，暴力的神！
