分块

分块写法

#define st(i) ((i-1)*len+1)
#define ed(i) min(i*len,n)
len=...; for(int i=1;i<=n;i++) bk[i]=(i-1)/len+1;

块的编号：$1$ 到 $bk[n]$。

序列分块

1.数列分块入门1-9

4

区间加法，区间求和。

懒标记。
时间复杂度 $O(m\sqrt{n})$。

可以树状数组/线段树。

2

区间加法，询问区间 $\le x$ 的元素个数。

块内排序，查询时二分。
时间复杂度 $O(m\sqrt{n}\log n)$。
归并排序+条块长可以做到 $O(m\sqrt{n\log n})$。

6

单点插入，单点询问。

定期重构。

可以平衡树。

9

区间众数。

一段区间的众数可能是中间块内的众数或两边散块的众数。

可以回滚莫队。

code

2.[HNOI2010] 弹飞绵羊

每个块预处理每个元素走出本块需要的步数和到达的点。

3.简单的数列题

块内维护下凸壳。

4.作诗

维护前缀和，散块暴力判断。时间复杂度 $O(m\sqrt{n})$。

5.[Ynoi2019 模拟赛] Yuno loves sqrt technology III

需要判断一个数在区间中出现次数是否 $> k$，记录所有同类数的位置，判断即可。

6.[Ynoi2019 模拟赛] Yuno loves sqrt technology I

归并。

7.Chef and Churu

给你一个长为 $n$ 的序列和 $m$ 个区间，支持序列单点修改，查询范围区间和。

将区间分块，统计序列每个元素在每个块内的出现次数。块内的区间和可以简单维护。

对于散块，需要 $O(\sqrt{m})$ 次区间求和。对序列分块，维护序列前缀和。

8.带插入区间K小值

aaa！！！

树分块

随机撒点

1.Count on a tree II/【模板】树分块

王室联邦分块

1.[SCOI2005] 王室联邦

基于 top cluster 的树分块

。。。

参考

分块

树分块