zcmimi's blog

arrow_back分块共7篇文章

avatar
zcmimi
2020-10-10 19:06:08

分块是一种非常好用的根号算法,本质上是暴力优化技巧

原理是将序列分成\sqrt n块,预处理出每个块的结果,在查询时只需要在完整块的基础上枚举散块更新答案即可

复杂度\mathcal O(n\sqrt n)

avatar
zc
2020-10-10 17:22:12

查看原题

点击跳转

预处理出

  • s[i][j]表示前i块到中j出现的次数
  • b[i][j]表示第i块到第j块的答案

统计时,在块内答案的基础上,枚举块外元素更新即可

avatar
zc
2020-10-09 18:10:52

查看原题

点击跳转

题意: 给出一个长度为n序列a,m次询问,每次询问区间[l,r]里出现次数最多的数. 若有多个,输出最小的.

如果是严格区间众数可以用主席树,这里要求找到出现次数最多的数,只能使用分块

先对序列进行离散化

预处理:

  1. s[i][j]表示前i个块中j出现了几次
  2. p[i][j]表示第i块到第j块中出现次数最多的数,P[i][j]表示次数

复杂度\mathcal O(n\log n)

对于一个询问[l,r]

l,r在同一个块或相邻块,那么暴力求解

否则枚举块外的数,每个数的出现次数为块内的+块外的,与块内已经预处理出的答案比较,更新答案

avatar
zc
2020-09-27 14:05:00

查看原题

点击跳转

统计方法类似扫描线

lp排序,按顺序枚举

l的时候更新,在r之后还原(p已经不在区间[l,r]中了,不受影响)

以时间为下标,维护某个时间段内大于等于y的数个数

需要一个数据结构维护区间中大于等于某个数的个数(带修改),可以想到分块

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

分块好题

\gcd有个性质: 一旦变动则小于原来的\frac 12(最小的质因子为2)

那么总共最多\log_2 n个不同的\gcd

每个块记录的信息:

  • 块内前缀gcd
  • 块内前缀xor和

然后对块内元素按前缀xor和排序

修改操作: 修改对应元素,并重构元素所在块

查询操作:

枚举每个块,若前缀gcd不变,则直接在排序好的元素中二分查找

否则枚举判断

复杂度O(n\sqrt n \log n)

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

题意:

  1. 区间加
  2. 求序列最大前缀和

区间加,相当于前缀和加上一个等差数列

而等差数列加上一个等差数列还是等差数列

考虑将每个位置的前缀和转化为一个一次函数kx+b

分块,对每个块维护一个上凸壳单调栈,可以二分找到最大值

avatar
zc
2020-07-25 23:00:00
查看原题

点击跳转

异或一个数两次,可以抵消

我们可以给区间中所有相同的数都赋一个新的随机数值,防止异或时出现干扰

pre_ii位置的数上一次出现的数,v_i为位置i新赋值的数,S_i为异或前缀和

若区间[l,r]中所有数出现的数出现的次数是奇数,那么S_r\oplus S_{l-1}等于\{v_i|pre_i<x,i\in [l,r]\}的异或和

枚举r,设p_x\{v_i|pre_i<x,i\in [x,r]\}异或和

那么相当于求满足S_r\oplus S_{x-1}\oplus p_x=0

r变为r+1,\{p_i|i\in [pre_{r+1}+1,r]\}异或上v_{r+1}

问题也就转化为了: 区间异或,区间查询某个数出现次数

使用分块+hash解决

1/1
Search
search