深圳网站建设公司平台,seo秘籍优化课程,大兴企业官网网站建设,阿里云网站开发[题目通道](教主的魔法 - 洛谷)
摘要
分块#xff0c;是一种优雅的暴力#xff0c;它通过对数列分段#xff0c;完成对数列一些区间操作和区间查询的操作#xff0c;是一种根号算法。
这篇学习笔记题解是本萌新在学习分块过程中的一些感悟#xff0c;希望能够帮助…[题目通道](教主的魔法 - 洛谷)
摘要
分块是一种优雅的暴力它通过对数列分段完成对数列一些区间操作和区间查询的操作是一种根号算法。
这篇学习笔记题解是本萌新在学习分块过程中的一些感悟希望能够帮助分块零基础的同学学会基础分块。 0 说明
本文中以下变量有特定的含义
blockblock块的大小nn被分块的数列的大小长度LxLx第 xx 号块的左边界RxRx第 xx 号块的右边界tottot块的数量belongxbelongx第 xx 号元素所属的块
在写作时由于本萌新的失误只好提前在这里令 [l,r][l,r] 与 [x,y][x,y] 等价。 1 建块
1.1 建块需要完成的任务
在读入数据后建块需要完成以下几个任务
确定块的大小确定块的数量标记每个块的左右边界标记每个元素所属的块对每个块的数据进行初始化
1.2 确定块的大小
一般来说我们习惯于令 blocknblockn。
但是由于毒瘤良心命题人泛滥blocknblockn 极其有可能被针对在这种情况下我们可以对块的大小适当作出一些调整例如 n1n1n−1n−1nlg(n)lg(n)n 等。
一般这个工作只有一句话
block (int)sqrt((double)n);1.3 确定块的数量
在确定了块的大小后块的数目就很容易确定了。
但是 nn 不一定是一个完全平方数我们需要把最后几个无法凑足 blockblock 个元素的再单独分一个块。
代码如下
tot n / block;
if(n % block) tot;1.4 标记每个块的左右边界
非常显然L11,R1block,L2block1,R22×block,⋯L11,R1block,L2block1,R22×block,⋯
从而可以得出结论
Lx(x−1)⋅block1,Rxx⋅blockLx(x−1)⋅block1,Rxx⋅block
特别地RtotnRtotn
代码
for(int i 1; i tot; i){L[i] (i - 1) * block 1;R[i] i * block;
}
R[tot] n;1.5 标记每个元素所属的块
根据 1.4我们很容易推出公式如下
belongxx−1block1belongxblockx−11
代码如下
for(int i 1; i n; i)belong[i] (i - 1) / block 1;重要在使用分块过程中一定要注意区分 tottot 和 nn。 tottot 是块的总数nn 是原来元素的总数。
1.6 对每个块的元素进行初始化
这项工作因题目不同而不同如【教主的魔法】一题就要对每个块的元素进行排序。
因为排序会对原始数列作出改变所以在本题中应当先把数列复制一遍再进行分块 2 分块题常见的操作
修改
对数列 [l,r][l,r] 内的每个数加上 kk对数列 [l,r][l,r] 内的每个数减去 kketc.
查询
求数列 [l,r][l,r] 内的所有数的和求数列 [l,r][l,r] 内的数有多少大于/小于/大于等于/小于等于 kketc. 3 修改操作
考虑两种修改操作本质相同第二种修改操作相当于第一种修改操作中 k−k′k−k′。
3.1 暴力修改
考虑枚举区间 [l,r][l,r] 之间所有数直接对其实施修改在修改的过程中维护每一个块的和/大小关系等。
但这不是我们考虑的东西
3.2 考虑线段树思想
线段树一个重要思想lazytag
考虑应用在分块中。在修改操作中如果是整块就不维护每个的具体信息而是在这个块的 lazylazy 标记上加上 kk。对于没有整块修改的部分即块 belongxbelongx 和 belongybelongy 的修改部分暴力修改。
这样的话第 ii 个数据 aiai 的真正数据值为 ailazybelongiailazybelongi。
如果询问涉及到排序块 belongxbelongx 和 belongybelongy 需要全部重新备份和排序对于块 [belongx1,belongy−1][belongx1,belongy−1] 的块数的相对大小不会改变所以可以不重新排序。
特别地需要特判 belongxbelongybelongxbelongy 的情况。
代码
void change(){if(belong[x] belong[y]){for(int i x; i y; i){a[i] k;sum[belong[x]] k;}return;}for(int i x; i R[belong[x]]; i){a[i] k;sum[belong[x]] k;}for(int i L[belong[y]]; i y; i){a[i] k; sum[belong[y]] k;}for(int i belong[x] 1; i belong[y] - 1; i){lazy[i] k;sum[i] blo * k;}
}对以下这句代码作出特别解释
sum[i] blo * k;不用特判最后一块的原因是如果操作区间覆盖到的最后一块也一定是作为 belongybelongy 处理掉了剩下来的块长一定是 blockblock。 4 查询操作
4.1 查询元素和
对于块 belongxbelongx 和 belongybelongy暴力枚举加和注意加上其元素后还要加上 lazybelongilazybelongi
对于 [belongx1,belongy−1][belongx1,belongy−1] 的块直接 ansanssum[i] 即可。
同样的需要特判 belongxbelongybelongxbelongy
代码
int query_sum(){int ans 0;if(belong[x] belong[y]){for(int i x; i y; i){ans a[i] lazy[belong[x]];}return ans;}for(int i x; i R[belong[x]]; i){ans a[i] lazy[belong[x]];}for(int i L[belong[x]]; i y; i){ans a[i] lazy[belong[y]];}for(int i belong[x] 1; i belong[y] - 1; i){ans sum[i];}return ans;
}4.2 查询关系
与4.1类似在块 belongxbelongx 和 belongybelongy暴力枚举求答案
对于 [belongx1,belongy−1][belongx1,belongy−1] 的块因为其是有序的进行二分找到端点位置然后加加减减求出块中有多少符合要求的元素即可。
本处代码见5. 5 教主的魔法
在学习完分块后我们可以发现教主的魔法就是一道裸的分块题。
因此完整代码如下
#includebits/stdc.h
#includevector
using namespace std;
int m,n,t,pos[1251000];
int s[2151000],flag[1251000];
vectorintv[550000];void reset(int x) {v[pos[x]].clear();for(int i(pos[x]-1)*m1; imin(pos[x]*m,n); i)v[pos[x]].push_back(s[i]);sort(v[pos[x]].begin(),v[pos[x]].end());
}void change(int a,int b,int c) {for(int ia; imin(pos[a]*m,b); i)s[i]c;reset(a);if(pos[a]!pos[b]) {for(int i(pos[b]-1)*m1; ib; i)s[i]c;reset(b);}for(int ipos[a]1; ipos[b]-1; i)flag[i]c;
}int query(int l,int r,int c) {int ans0;for(int il; imin(pos[l]*m,r); i)if(s[i]flag[pos[l]]c)ans;if(pos[l]!pos[r]) {for(int i(pos[r]-1)*m1; ir; i)if(s[i]flag[pos[r]]c)ans;}for(int ipos[l]1; ipos[r]-1; i) {int xc-flag[i];anslower_bound(v[i].begin(),v[i].end(),x)-v[i].begin();}return ans;
}signed main() {scanf(%d %d,n,t);msqrt(n);for (int i1; in; i) pos[i](i-1)/m1;for (int i1; in; i) scanf(%d,s[i]);for(int i1; in; i)pos[i](i-1)/m1,v[pos[i]].push_back(s[i]);for(int i1; ipos[n]; i)sort(v[i].begin(),v[i].end());for (int i1; it; i) {int a,b,c;char x;cinx;scanf(%d%d%d,a,b,c);if (xM) {change(a,b,c);} else if (xA) {coutb-a1-query(a,b,c)endl;}}return 0;
}
