ToB企服应用市场:ToB评测及商务社交产业平台

标题: 分块小结 [打印本页]

作者: 用多少眼泪才能让你相信 时间: 2024-5-13 11:37
标题: 分块小结
分块概念

就是把一个长序列分成 \(\sqrt{n}\) 个区间，分别维护每个区间内的信息和，然后查询时可以优化时间复杂度。
还可以完成一些线段树完成不了的神秘操作，比如这道题。
但是总体时间复杂度不如线段树，但它的扩展性比线段树还要强，因为分块中每个区间的信息和不必要具有传递性。
怎么理解？
就比如说，必要对一个序列维护区间取模，我们可以开一个数组专门存储当前区间的所有数是否都小于要取模的数，以此实现修改的加速。
线段树的做法就会难想许多，不做赘述。
代码结构

预处理

预处理出每个区块的起始点和重点，以及每个数属于哪个区块。
必要时要处理处每个区块的长度（如要区间加）。
[code]int a[100011];int bel[100010];int st[5000],ed[5000],siz[5000],sum[5000];int cnt[5001],f[5001];void init(){ int sq=sqrt(n); for(int i=1;i

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)