分块是一种类似线段树的算法便于区间、单点加法区间、单点求值。比如有一组元素A :123256579。把它3个一块123 256 579。假设要将第2个数到第7个数都加2。我们发现第2块的数都要加2我们不妨建一个数组tagtag[k]表示第k块整体加的数。原数组A变成145 256 779 tag[2]2边角不成整块的直接在原数组上加成整块的在tag上标记。如果要我们求第5个数第五个数属于第二块用A[5]tag[2]即可。那么几个元素一块最好呢设n个元素B个一块每次加法要执行Bn/B次操作要使这个值最小B要等于根号n所以这段程序的时间复杂度为O(根号n*操作次数)。例题n个元素n此操作n50000每次操作输入opt,l,r,c。若 opt0表示将位于 [l,r] 的之间的数字都加 c。若 opt1表示询问第r个数的值l 和 c 忽略。#includebits/stdc.h using namespace std; typedef long long ll; const int N5000010; int n; int B;//每块里元素个数 int tot;//块数 int L[N],R[N];//第k块的左右端点 int bel[N];//第i个元素属于bel[i]块 ll a[N];//原数组不算tag ll tag[N];//第k的标记tag[k] void init(){ Bsqrt(n)1; tot(nB-1)/B;//向上取整 for(int k1;ktot;k){ //L[1]1,R[1]B //L[2]B1,R[2]2B //... L[k](k-1)*B1; R[k]min(n,k*B); for(int iL[k];iR[k];i)bel[i]k; } } void add(int l,int r,ll c){ int lbbel[l],rbbel[r]; if(lbrb){//l,r都在一整块 for(int il;ir;i)a[i]c; return; } for(int il;iR[lb];i)a[i]c;//左边角料 ,无法打标记 for(int iL[rb];ir;i)a[i]c;//右边角料 ,无法打标记 for(int klb1;krb-1;k)tag[k]c;//中间整块部分 } ll query(int r){//查询 return a[r]tag[bel[r]]; } int main(){ cinn; init(); for(int i1;in;i)cina[i]; for(int i1;in;i){ int op,l,r; ll c; cinoplrc; if(!op)add(l,r,c); else coutquery(r)endl; } return 0; }区间加法区间求和#includebits/stdc.h using namespace std; typedef long long ll; const int N5000010; int n,mod; int B;//每块里元素个数 int tot;//块数 int L[N],R[N];//第k块的左右端点 int bel[N];//第i个元素属于bel[i]块 ll a[N];//原数组不算tag ll tag[N];//第k的标记tag[k] ll sum[N];//sum[k]表示原数组第k块的和 void init(){ Bsqrt(n)1; tot(nB-1)/B; for(int k1;ktot;k){ L[k](k-1)*B1; R[k]min(n,k*B); for(int iL[k];iR[k];i)bel[i]k; } } void add(int l,int r,ll c){ int lbbel[l],rbbel[r]; if(lbrb){ for(int il;ir;i){ a[i]c; sum[lb]c; } return; } for(int il;iR[lb];i){ a[i]c; sum[lb]c; } for(int iL[rb];ir;i){ a[i]c; sum[rb]c; } for(int klb1;krb-1;k){ tag[k]c; } } __int128 query(int l,int r,int c){ int lbbel[l],rbbel[r]; __int128 ans0; if(lbrb){ for(int il;ir;i)ansansa[i]tag[lb]; return ans; } for(int il;iR[lb];i)ansansa[i]tag[lb]; for(int iL[rb];ir;i)ansansa[i]tag[rb]; for(int klb1;krb-1;k)anssum[k](__int128)tag[k]*(R[k]-L[k]1); return ans; } int main(){ cinn; init(); for(int i1;in;i){ cina[i]; sum[bel[i]]a[i]; } for(int i1;in;i){ int op,l,r; ll c; cinoplrc; modc1; if(!op)add(l,r,c); else cout(ll)(((query(l,r,c)%mod)mod)%mod)endl; } return 0; }求区间内小余c平方的个数这是分块经典例题维护数组v也是B个元素一块每块内的元素时刻与原数组对应但不同的是对于块内元素是单调递增的。在查询的时候暴力查询边角元素不成整块查询整块时用二分查询v数组对应块中小余c*c-tag[k]的元素。#includebits/stdc.h using namespace std; typedef long long ll; const int N5000010; int n,mod; int B;//每块里元素个数 int tot;//块数 int L[N],R[N];//第k块的左右端点 int bel[N];//第i个元素属于bel[i]块 ll a[N];//原数组不算tag ll tag[N];//第k的标记tag[k] ll v[N]; void resort(int k){//维护v数组 for(int iL[k];iR[k];i)v[i]a[i]; sort(vL[k],vR[k]1); } void init(){ Bsqrt(n)1; tot(nB-1)/B; for(int k1;ktot;k){ L[k](k-1)*B1; R[k]min(n,k*B); for(int iL[k];iR[k];i)bel[i]k; } } void add(int l,int r,ll c){ int lbbel[l],rbbel[r]; if(lbrb){ for(int il;ir;i)a[i]c; resort(lb); return; } for(int il;iR[lb];i)a[i]c; for(int iL[rb];ir;i)a[i]c; resort(lb); resort(rb); for(int klb1;krb-1;k)tag[k]c; } int count_less_block(int k,ll x){//二分查询v数组块内小余x-tag[k]的个数 ll needx-tag[k]; return lower_bound(vL[k],vR[k]1,need)-(vL[k]); } ll query(int l,int r,ll x){ int lbbel[l],rbbel[r]; int ans0; if(lbrb){ for(int il;ir;i){ if(a[i]tag[lb]x)ans; } return ans; } //暴力查询不成块的元素 for(int il;iR[lb];i){ if(a[i]tag[lb]x)ans; } for(int iL[rb];ir;i){ if(a[i]tag[rb]x)ans; } for(int klb1;krb-1;k)anscount_less_block(k,x); return ans; } int main(){ cinn; init(); for(int i1;in;i)cina[i]; for(int k1;ktot;k)resort(k); for(int i1;in;i){ int op,l,r; ll c; cinoplrc; if(!op)add(l,r,c); else coutquery(l,r,c*c)endl; } return 0; }谢谢观看。
企业数字化 ERP 产品动态
相关推荐
将小米设备接入 Home Assistant:ha_xiaomi_home 集成上手指南 将小米设备接入 Home Assistant:ha_xiaomi_home 集成上手指南 【免费下载链接】ha_xiaomi_home Xiaomi Home Integration for Home Assistant 项目地址: https://gitcode.com/GitHub_Trending/ha/ha_xiaomi_home
如果你希望把家里的小米智能家居设备… · 2026/11/21 3:33:07
能用的Docker镜像 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/18 23:13:19
【芳芯科技】硫化氢、氨气、一氧化碳等气体采集报警器 效果图:实现功能:面向污水处理厂的气体检测电子鼻系统硬件部分主要由以下的部分组成:硫化氢传感器、氨气传感器、甲烷传感器、一氧化碳传感器、AD转换模块、按键模块、电源供电模块、STC89C51单片机最小系统、液晶显示模块、声光报警电路。由… · 2026/11/15 18:20:14
剑川县电工证怎么考证?学历不高怕报不上名?考前押题帮你解决 剑川县电工证怎么考证?学历不高怕报不上名?考前押题帮你解决 你不是一个人,很多人学历不高,担心考不上电工证,怕报名时被拒,怕考试时挂科,甚至怕后续复审时出问题。但别担心, 剑川县电工证怎么考证… · 2026/11/21 10:05:37
初中毕业也能考低压电工证电路检测在哪考?别让学历挡住你前路 初中毕业也能考低压电工证电路检测在哪考?别让学历挡住你前路 你是不是也担心学历不够,考不了低压电工证?其实, 初中毕业也能考低压电工证电路检测 ,关键是你得知道 在哪考 ,还得选对地方、走对流程。… · 2026/11/21 10:05:37
广州南沙初级电工证通过率揭秘:外省证书能转吗?这样备考更稳 广州南沙初级电工证通过率揭秘:外省证书能转吗?这样备考更稳 之前考的证在外省能不能转过来?这几乎是每个想在广州南沙从事电工工作的朋友最关心的问题。特别是在河南等外省考取的电工证,是否能直接在广州南沙使用,是很多人在准备换证或报考前的首要疑问… · 2026/11/21 10:05:37
县里培训电工证在外省考的能转过来吗在哪考 县里培训电工证在外省考的能转过来吗在哪考 之前考的证在外省能不能转过来?这是很多准备在县里培训电工证的小伙伴最关心的问题之一。特别是从外地回来,手里拿着一个外地的电工证,担心到了县里培训电工证是否还能继续使用,或者能不能顺利转过来。其实,根… · 2026/11/21 10:05:37
电工证忘记复审怎么办 这些避坑指南帮你多久拿证不耽误事 电工证忘记复审怎么办 这些避坑指南帮你多久拿证不耽误事 不知道去哪报名怕被中介坑,尤其是电工证这种关乎生命安全的特种作业证,一旦过期没复审,不仅影响工作,还可能面临罚款甚至被清退。最近不少电工朋友私信问“电工证忘记复审怎么办”,今天就从郑州… · 2026/11/21 10:05:37
长春初级电工证怎么考?通过率揭秘全在这里 长春初级电工证怎么考?通过率揭秘全在这里 之前考的证在外省能不能转过来?这几乎是每个想从事电工工作的人都会问的问题。特别是那些在外地打拼多年、手里握着一张“外地电工证”的人,到了长春想继续干这一行,第一反应就是“我的证能用吗?”。今天我们就… · 2026/11/20 16:18:19
国内电工证报考条件与考试时间 低压电工证怎么考?学历不高也能报名,官方报名入口全在这 你是不是经常听说“电工证是入行门槛”,但又担心自己学历不够、经验不足,根本报不了名?别急,今天就带你从零了解【国内电工证】的报考流程、考试内容,还有怎么在 官方报名入口… · 2026/11/20 18:25:07
电工作业时如何断电?电子证书到底能不能全国通用? 电工作业时如何断电?电子证书到底能不能全国通用? 实操考试心里没底怕挂科,特别是电工作业时如何断电这一操作,不仅关系到你能不能拿到证书,更关系到以后能不能顺利上岗。很多人觉得这不过就是“断个电”,但其实这里面的门道可不少,稍有不慎就可能出错… · 2026/11/20 17:56:32
电工证征求意见2026河南最新政策怎么应对?学历不高也能考! 电工证征求意见2026河南最新政策怎么应对?学历不高也能考! 你是不是也担心自己学历不高, 怕报不上名 ?尤其是像焦作水利工程这样的从业者,常年在一线作业,但证书却成了晋升、转岗、接项目的关键门槛。 2026河南最新政策… · 2026/11/21 0:00:17
电工证征求意见怎么填?含金量高不高?济源电工朋友看过来 电工证征求意见怎么填?含金量高不高?济源电工朋友看过来 不知道去哪报名怕被中介坑,电工证征求意见填错了不仅白费钱,还可能影响后续考试和工作。最近很多济源的电工朋友都在问: 电工证征求意见怎么填… · 2026/11/21 0:00:17
房建企业特种工考前押题怎么找?别让培训费打了水漂 房建企业特种工考前押题怎么找?别让培训费打了水漂 怕考不过白交培训费?房建企业特种工考试难度高、题型多,很多人报名后才发现没有合适的复习资料,最终考试落榜,白白浪费了时间和金钱。别担心,掌握【考前押题】的技巧,能让你事半功倍,顺利通过考试。… · 2026/11/21 0:00:17
双极步进电机控制实战:DRV8818PWPR与PIC18F86K22驱动调试 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:25:45
STM32F207ZG + DRV8818PWPR 步进电机驱动实战解析 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:25:54
DRV8818PWPR+dsPIC30F4013工业级双极步进电机控制方案 /* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views … · 2026/11/20 10:26:03