数据结构与算法：分块（一）：块状数组、块状链表-北京尧图网络

前言这玩意儿也太妙了一、内容对于 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

数据结构与算法：分块（一）：块状数组、块状链表

相关推荐

第五章 TTM后备存储: 4.8.3 TTM Eviction 的定向与搬迁执行 -- BO Move 路径

Windows服务内存泄漏排查实战：系统池异常增长与句柄泄漏修复

genshin-wish-export 原神祈愿记录导出完整指南：一键把抽卡历史变成 Excel

更多资讯

UOS系统下Java版Firefox浏览器安装与配置指南

从手工到自动：做 PPT 的 2 步改造记录

WebSocket在线游戏开发：双端实时同步最小可行骨架

表格数据合成实战：从SMOTE插值到CTGAN深度生成的选型与评估

AI生成式背景技术如何提升C4D设计效率

GPS轨迹噪点剔除API：Python算法与工程实践

今日更新

学生选课系统DFD图绘制指南：边界划分与分层校验实战

JIRA敏捷落地：Scrum角色权限、Sprint与燃尽图避坑指南

SEMI S8人机工程验收实战：从条款拆解到现场实测的完整指南

本周精选

防幻觉智能体架构：电源硬件设计中的大模型编排与工具化实践

OpenGL面试核心考点：渲染管线、矩阵变换与性能排查全解析

全国计算机二级C语言真题PDF高效刷题指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？