前言这玩意儿也太妙了一、内容对于 n 长度的数组考虑将其平均划分为块那么就有块数和每个块内的长度都是的级别所以此时就能实现遍历所有块和块内遍历一遍的复杂度都是的了。在维护信息时块内就可以暴力维护整块直接修改标签即可。那么在处理时就只需要对左右散块暴力中间块遍历即可。二、适用场景当区间信息不可合并或者很难合并时那么就无法使用线段树了。而此时往往分块比较容易解决因为块内信息是暴力维护的。除此之外分块在思维上比其他正解是要好想的在想不到正解的时候可以考虑分块暴力草三、题目1. Give Away#includebits/stdc.h using namespace std; /* /\_/\ * ( ._.) * / \ */ /* *想好再写 *注意审题 注意特判 *不要红温 不要急躁 耐心一点 *WA了不要立马觉得是思路不对 先耐心找反例 */ #define endl \n #define dbg(x) cout#xendl;coutxendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; typedef long long ll; typedef long double ld; typedef pairint,int pii; typedef pairll,ll pll; const int INF1e9; const ll INFLL1e18; 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; cinn; vectorinta(n1); for(int i1;in;i) { cina[i]; } int blensqrt(n); int bnum(nblen-1)/blen; vectorintbi(n1); for(int i1;in;i) { bi[i](i-1)/blen1; } vectorintbl(blen1); vectorintbr(blen1); for(int i1;ibnum;i) { bl[i](i-1)*blen1; br[i]min(i*blen,n); } vectorintsorted(n1); for(int i1;in;i) { sorted[i]a[i]; } for(int i1;ibnum;i) { sort(sorted.begin()bl[i],sorted.begin()br[i]1); } auto bs[](int i,int v)-int { int lbl[i]; int rbr[i]; int m; int ansr1; while(lr) { mlr1; if(sorted[m]v) { ansm; rm-1; } else { lm1; } } return br[i]-ans1; }; auto query[](int l,int r,int v)-int { if(bi[l]bi[r]) { int ans0; for(int il;ir;i) { if(a[i]v) { ans; } } return ans; } int ans0; for(int il;ibr[bi[l]];i) { if(a[i]v) { ans; } } for(int ibi[l]1;ibi[r]-1;i) { ansbs(i,v); } for(int ibl[bi[r]];ir;i) { if(a[i]v) { ans; } } return ans; }; auto update[](int p,int v)-void { int lbl[bi[p]]; int rbr[bi[p]]; a[p]v; for(int il;ir;i) { sorted[i]a[i]; } sort(sorted.begin()l,sorted.begin()r1); }; int m; cinm; int op,i,x,l,r,v; while(m--) { cinop; if(op0) { cinlrv; coutquery(l,r,v)endl; } else { cinix; update(i,x); } } } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; 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#xendl;coutxendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; typedef long long ll; typedef long double ld; typedef pairint,int pii; typedef pairll,ll pll; const int INF1e9; const ll INFLL1e18; 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; cinnq; vectorlla(n1); for(int i1;in;i) { cina[i]; } int blensqrt(n); int bnum(nblen-1)/blen; vectorintbi(n1); for(int i1;in;i) { bi[i](i-1)/blen1; } vectorintbl(bnum1); vectorintbr(bnum1); for(int i1;ibnum;i) { bl[i](i-1)*blen1; br[i]min(n,i*blen); } vectorintsorted(n1); for(int i1;in;i) { sorted[i]a[i]; } for(int i1;ibnum;i) { sort(sorted.begin()bl[i],sorted.begin()br[i]1); } vectorlllazy(bnum1); auto bs[](int i,int v)-int { int lbl[i]; int rbr[i]; int m; int ansr1; while(lr) { mlr1; if(sorted[m]v) { ansm; rm-1; } else { lm1; } } return br[i]-ans1; }; auto add[](int l,int r,int v)-void { if(bi[l]bi[r]) { for(int il;ir;i) { a[i]v; } for(int ibl[bi[l]];ibr[bi[l]];i) { sorted[i]a[i]; } sort(sorted.begin()bl[bi[l]],sorted.begin()br[bi[l]]1); return ; } for(int il;ibr[bi[l]];i) { a[i]v; } for(int ibl[bi[l]];ibr[bi[l]];i) { sorted[i]a[i]; } sort(sorted.begin()bl[bi[l]],sorted.begin()br[bi[l]]1); for(int ibi[l]1;ibi[r]-1;i) { lazy[i]v; } for(int ibl[bi[r]];ir;i) { a[i]v; } for(int ibl[bi[r]];ibr[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 ans0; for(int il;ir;i) { if(a[i]v-lazy[bi[l]]) { ans; } } return ans; } int ans0; for(int il;ibr[bi[l]];i) { if(a[i]v-lazy[bi[l]]) { ans; } } for(int ibi[l]1;ibi[r]-1;i) { ansbs(i,v-lazy[i]); } for(int ibl[bi[r]];ir;i) { if(a[i]v-lazy[bi[r]]) { ans; } } return ans; }; char op;int l,r,v; while(q--) { cinoplrv; if(opM) { add(l,r,v); } else { coutquery(l,r,v)endl; } } } void init() { } signed main() { ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); int t1; //cint; 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 xendl; #define vdbg(a) cout#aendl;for(auto x:a)coutx ;coutendl; #define YES coutYESendl;return ; #define Yes coutYesendl;return ; #define NO coutNOendl;return ; #define No coutNoendl;return ; #define popcount __builtin_popcount using lllong long; using i128__int128; using ldlong double; using piipairint,int; using pllpairll,ll; const int INF1e9; const ll INFLL1e18; 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; cinnq; vectorinta(n1); for(int i1;in;i) { cina[i]; } vectorintsorteda; sort(sorted.begin()1,sorted.end()); int len1; for(int i2;in;i) { if(sorted[len]!sorted[i]) { sorted[len]sorted[i]; } } auto rnk[](int v)-int { int l1; int rlen; int m; int ans; while(lr) { mlr1; if(sorted[m]v) { ansm; rm-1; } else { lm1; } } return ans; }; for(int i1;in;i) { a[i]rnk(a[i]); } int blensqrt(n); int bnum(nblen-1)/blen; vectorintbi(n1); for(int i1;in;i) { bi[i](i-1)/blen1; } vectorintbl(bnum1); vectorintbr(bnum1); for(int i1;ibnum;i) { bl[i](i-1)*blen1; br[i]min(n,i*blen); } vectorvectorintfreq(bnum1,vectorint(len1)); for(int i1;ibnum;i) { for(int j1;jlen;j) { freq[i][j]freq[i-1][j]; } for(int jbl[i];jbr[i];j) { freq[i][a[j]]; } } vectorvectorintmode(bnum1,vectorint(bnum1)); for(int i1;ibnum;i) { for(int ji;jbnum;j) { int mostmode[i][j-1]; int mostCntfreq[j][most]-freq[i-1][most]; for(int kbl[j];kbr[j];k) { int cura[k]; int curCntfreq[j][cur]-freq[i-1][cur]; if(curCntmostCnt||(curCntmostCntcurmost)) { mostcur; mostCntcurCnt; } } mode[i][j]most; } } vectorintcnts(len1); int l,r; int pre0; while(q--) { cinlr; l(lpre-1)%n1; r(rpre-1)%n1; if(lr) { swap(l,r); } if(bi[l]bi[r]) { for(int il;ir;i) { cnts[a[i]]; } int most0; for(int il;ir;i) { if(cnts[a[i]]cnts[most]||(cnts[a[i]]cnts[most]a[i]most)) { mosta[i]; } } presorted[most]; coutpreendl; for(int il;ir;i) { cnts[a[i]]0; } continue; } for(int il;ibr[bi[l]];i) { cnts[a[i]]; } for(int ibl[bi[r]];ir;i) { cnts[a[i]]; } int mostmode[bi[l]1][bi[r]-1]; int mostCntfreq[bi[r]-1][most]-freq[bi[l]][most]; for(int il;ibr[bi[l]];i) { int cura[i]; int curCntcnts[cur]freq[bi[r]-1][cur]-freq[bi[l]][cur]; if(curCntmostCnt||(curCntmostCntcurmost)) { mostcur; mostCntcurCnt; } } for(int ibl[bi[r]];ir;i) { int cura[i]; int curCntcnts[cur]freq[bi[r]-1][cur]-freq[bi[l]][cur]; if(curCntmostCnt||(curCntmostCntcurmost)) { mostcur; mostCntcurCnt; } } presorted[most]; coutpreendl; for(int il;ibr[bi[l]];i) { cnts[a[i]]0; } for(int ibl[bi[r]];ir;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 t1; //cint; init(); while(t--) { solve(); } return 0; }对于众数这个问题首先可以考虑维护 freq[i][j] 表示前 i 块里 j 这个数出现的次数即一个前缀词频。之后再维护一个 mode[i][j] 表示第 i 块到第 j 块之间的最小众数。那么对于查询中间的整块就可以使用这两个数组查出众数和词频。然后对于两边的散块就可以暴力统计词频判断是否大于中间这个众数即可。构建时freq 数组就是正常统计前缀词频即可。对于 mode 数组就是每次先找出 i 到 j-1 块的众数和词频然后在遍历当前块的时候对于块内的每个数判断其区间词频是否可以更新众数即可。总结分块暴力的神END