Luogu分析考虑莫队。则我们需要实现一个支持单点修改、区间求和和非 $0$ 数的个数的东西。考虑用值域分块实现，对于每块维护内部的和和非 $0$ 数的个数即可。总时间复杂度 $\mathcal{O}(m\sqrt{n})$。代码// =================================== // author: M_sea // website: http://m-s...
Luogu分析先分块。先预处理出 $s_{i,j}$ 表示前 $i$ 块中 $j$ 的数量，以及 $f_{i,j}$ 表示第 $i$ 块到第 $j$ 块的众数。算答案时，显然答案要么是整块的 $f$，要么是角块中的某个数，枚举角块中数利用 $s$ 判断是否更多即可。具体实现和细节见代码。代码// =================================== // author:...
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})$ 的询...
Luogu分析大力分块。对于修改，边块直接暴力，整块打标记。对于查询，边块暴力查询，整块可以块内排序+块内二分。但是每次查询都sort一遍极慢，可以先将每块排序后的数组存下来，当有一部分被修改时再重排一次。这样子就快了很多。然后，块大小取$\sqrt{\frac{n+2}{3}}$，飞快。代码//It is made by M_sea #include <algorithm> #...
LuoguBZOJ分析大力分块。设$step[i]$表示$i$弹出所在块的步数，$to[i]$表示$i$弹出所在块后落到哪。然后一开始就可以$O(n)$预处理出来。对于查询，每一块跳过去就行，$O(\sqrt{n})$。对于修改，把所在块全部修改一遍即可，也是$O(\sqrt{n})$。总时间复杂度是$O(m\sqrt{n})$，还是能氵过去的。代码#include <algorith...