CF1375H Set Merging
Codeforces Luogu 分析 考虑对值域分块，设块长为 $B$。 对于每块，我们考虑凑出每个原序列中区间对应的集合（这样的集合实际上只有 $\mathcal{O}(B^2)$ 个）。这样子就可以通过把每一块对应的集合合并来得到每个询问的答案了，操作次数为 $\frac{nq}{B}$。 考虑每一块内对值域分治，每次将两个子区间 $\mathcal{O}(len^2)$ 地合并，这样...
标签 分块 下的文章
- 首页
- 分块
洛谷3641 [APIO2016]最大差分
Luogu LOJ UOJ 分析 Subtask1 首先调用 MinMax(0,1e18,&a[1],&a[n]) 来求出 $a_1$ 和 $a_n$。 然后不断调用 MinMax(a[i-1]+1,a[j+1]-1,&a[i],&a[j]) 即可求出整个序列。 Subtask2 首先调用 MinMax(0,1e18,&a[1],&a[n]) ...
洛谷3700 [CQOI2017]小Q的表格
Luogu LOJ 分析 可以发现这两条规则长得很像更相减损术，推一推可以得到 最后那一步可以考虑实际意义，证明就不写了（ 如果没有修改的话就可以预处理 $i^2\varphi(i)$ 的前缀和然后数论分块计算了。然而现在还有若干次对于 $f(d,d)$ 的修改，可以想到用一个数据结构来维护。 思考一下，我们在数论分块时需要进行 $\mathcal{O}(Q)$ 次修改和求 $\mathc...
CF573E Bear and Bowling
Codeforces Luogu 分析 考虑一个贪心，即每次取贡献最大的一个，这里的贡献是 $k_i\times a_i+b_i$，其中 $k_i$ 表示前面选了的数量，$b_i$ 表示后面选了的 $a_i$ 的和。 那么我们相当于要维护一些直线，支持区间斜率加、截距加和求全局最大值。 考虑分块，对每块维护一个上凸壳，散块修改后重构、整块打标记即可。注意要把当前选出来的数删掉。 代码 // ...
洛谷5047 [Ynoi2019模拟赛]Yuno loves sqrt technology II
Luogu 分析 考虑莫队，在移动过程中用树状数组维护每种值的出现次数。这样子是 $\mathcal{O}(n\sqrt{n}\log n)$ 的，由于这是 Ynoi 所以过不了。 由于转移是 $\mathcal{O}(\log n)$ 的，而逆序对数又是个可减的东西，所以可以考虑二次离线莫队。需要注意的是这里左端点的 $f$ 和右端点的 $f$ 是不一样的，一个是区间中比 $x$ 小的数的...
洛谷4119 [Ynoi2018]未来日记
Luogu 分析 先考虑没有修改怎么用分块做。 一个想法是将序列分块，然后维护 $s_{i,j}$ 表示前 $i$ 块中 $j$ 的数量，然而这样子查询是 $\mathcal{O}(n)$ 的。 因此我们再对值域分块，并再维护 $s'_{i,j}$ 表示前 $i$ 块中值在第 $j$ 块中的数的数量，询问时先把所求在值域的哪一块中求出来，再在这一块中求，复杂度 $\mathcal{O}(\s...
CF543E Listening to Music
Codeforces Luogu 分析 我们要让小于 $x$ 的数最少，即让大于等于 $x$ 的数最多。 那么我们可以对于每个大于等于 $x$ 的 $a_i$，将能覆盖到它的左端点的区间加上 $1$，这样子查询 $[l,r]$ 中的最大值就可以得到答案了。 仍然用上面的思路，但是我们考虑用分块维护这个区间加 $1$ 区间求最大值。 这个很好分块维护：对于整块，我们直接打标记即可；对于散块，我...
洛谷4117 [Ynoi2018]五彩斑斓的世界
Luogu 分析 考虑分块。 对于每一块，维护它的最大值 $mx$。可以发现 $\sum mx$ 是 $\mathcal{O}(n\sqrt{n})$ 级别的，因此每一块如果能够 $\mathcal{O}(x)$ 修改的话复杂度就是 $\mathcal{O}(n\sqrt{n})$。可以想到这样的修改方式 如果 $2x\geq mx$，则直接将所有 $>x$ 的数减去 $mx$。这样...