洛谷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:...
洛谷3247 [HNOI2016]最小公倍数
LuoguBZOJ分析对于每个询问 $(u,v,A,B)$，显然只能走 $a\leq A,b\leq B$ 的边。然后有一个很套路的方法 我不会。为了方便，下面设询问的 $a$ 和 $b$ 为 $A$ 和 $B$。将所有边按 $a$ 排序并分块，将所有询问按 $b$ 排序。设第 $i$ 块的左右端点为 $[l_i,r_i]$ ，找出所有 $A\in [a_{l_i},a_{r_i})$ 的询...
洛谷2801 教主的魔法
Luogu分析大力分块。对于修改，边块直接暴力，整块打标记。对于查询，边块暴力查询，整块可以块内排序+块内二分。但是每次查询都sort一遍极慢，可以先将每块排序后的数组存下来，当有一部分被修改时再重排一次。这样子就快了很多。然后，块大小取$\sqrt{\frac{n+2}{3}}$，飞快。代码//It is made by M_sea #include <algorithm> #...
洛谷3203 [HNOI2010]弹飞绵羊
LuoguBZOJ分析大力分块。设$step[i]$表示$i$弹出所在块的步数，$to[i]$表示$i$弹出所在块后落到哪。然后一开始就可以$O(n)$预处理出来。对于查询，每一块跳过去就行，$O(\sqrt{n})$。对于修改，把所在块全部修改一遍即可，也是$O(\sqrt{n})$。总时间复杂度是$O(m\sqrt{n})$，还是能氵过去的。代码#include <algorith...