洛谷3641 [APIO2016]最大差分
LuoguLOJUOJ分析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]) 来求出 $a_1...
标签 分块 下的文章
- 首页
- 分块
洛谷3700 [CQOI2017]小Q的表格
LuoguLOJ分析可以发现这两条规则长得很像更相减损术，推一推可以得到最后那一步可以考虑实际意义，证明就不写了（如果没有修改的话就可以预处理 $i^2\varphi(i)$ 的前缀和然后数论分块计算了。然而现在还有若干次对于 $f(d,d)$ 的修改，可以想到用一个数据结构来维护。思考一下，我们在数论分块时需要进行 $\mathcal{O}(Q)$ 次修改和求 $\mathcal{O}(Q...
CF573E Bear and Bowling
CodeforcesLuogu分析考虑一个贪心，即每次取贡献最大的一个，这里的贡献是 $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}(\sqrt{...
CF543E Listening to Music
CodeforcesLuogu分析我们要让小于 $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$。这样子是 $\...
CF500F New Year Shopping
CodeforcesLuogu分析一个不要脑子的做法是线段树分治，即以时间为下标将所有物品与询问挂到线段树上，在线段树上递归时维护一个长度为 $4000$ 的 0/1 背包的 DP 数组即可。标解给的是一个奇妙的分块做法，大概是分成 $p$ 块，从每个交界点往左右跑 0/1 背包，然后每个询问一定会包含一个交界点，直接将左右合并即可。代码因为我懒所以只有第一个方法的代码。// =======...
洛谷4396 [AHOI2013]作业
Luogu分析考虑莫队。则我们需要实现一个支持单点修改、区间求和和非 $0$ 数的个数的东西。考虑用值域分块实现，对于每块维护内部的和和非 $0$ 数的个数即可。总时间复杂度 $\mathcal{O}(m\sqrt{n})$。代码// =================================== // author: M_sea // website: http://m-s...
洛谷4168 [Violet]蒲公英
Luogu分析先分块。先预处理出 $s_{i,j}$ 表示前 $i$ 块中 $j$ 的数量，以及 $f_{i,j}$ 表示第 $i$ 块到第 $j$ 块的众数。算答案时，显然答案要么是整块的 $f$，要么是角块中的某个数，枚举角块中数利用 $s$ 判断是否更多即可。具体实现和细节见代码。代码// =================================== // author:...