LOJ2874 「JOISC 2014 Day1」历史研究
LOJ分析因为不强制在线，又要求一个类似于众数的东西，所以可以考虑莫队。然而似乎并不好删除，因此可以考虑回滚莫队。回滚莫队大概是这么个东西：把所有询问以左端点所属块为第一关键字、右端点为第二关键字排序。从左往右枚举所有块，每次处理所有左端点在当前块内的询问。一开始令 $l$ 为当前块右端点$+1$，$r$ 为当前块右端点。对于当前询问 $[x,y]$，如果 $x,y$ 在同一块内，直接暴力。...
标签 莫队 下的文章
- 首页
- 莫队
HDU4676 Sum Of Gcd
HDU分析令 $p_{a_i}=i$，则题目要求的是考虑莫队，加入一个数时枚举约数更新贡献即可。时间复杂度 $\mathcal{O}(\text{能过})$。当然你 $\mathcal{O}(\sqrt{n})$ 枚举约数当然是过不了的，可以开一个 vector 存下所有约数。代码// =================================== // author: M_se...
SPOJ COT2 - Count on a tree II
SPOJLuogu分析树上莫队板子题...？首先把树的欧拉序爬下来。设 $st_u$ 表示第一个 $u$ 的位置，$ed_u$ 表示最后一个 $u$ 的位置。考虑一个询问 $(u,v)$ 怎么统计。为了方便，设 $st_u<st_v$ 。如果 $lca(u,v)=u$ ，那么 $(u,v)$ 路径上的点就是欧拉序的 $[st_u,st_v]$ 中只出现过一次的点，莫队统计即可。如果 $...
CQOI2018简要题解
破解D-H协议$\begin{cases}g^a\equiv A\pmod{P}\\g^b\equiv B\pmod{P}\end{cases}$ 直接上 $\mathrm{BSGS}$ 求出 $a$ 和 $b$ ，然后答案就是 $g^{ab}\bmod P$ 。代码社交网络【模板】有向图矩阵树定理。代码交错序列首先推式子： $x^ay^b=(n-y)^ay^b=\sum\limits_{i...
CF375D Tree and Queries
CodeForcesLuogu分析如果在序列上这个问题非常的好做：设 $num[i]$ 为 $i$ 颜色的数量， $sum[i]$ 表示颜色数量 $\geq i$ 的颜色数。那么直接跑莫队即可。现在放到了树上变成了子树询问，那么直接在 dfs 序上跑就好了。当然 dsu on tree 也是可以的。具体实现及细节见代码。代码// ===============================...
洛谷4688 [Ynoi2016]掉进兔子洞
LuoguBZOJ分析莫队+ $\mathrm{bitset}$。显然一个询问 $(l_1,r_1,l_2,r_2,l_3,r_3)$ 的答案是 $(r_1-l_1+1)+(r_2-l_2+1)+(r_3-l_3+1)-3\times size$ ，这里的 $size$ 表示三个区间内出现了多少个公共的颜色。前面的非常 $\mathrm{sb}$ ，重点是怎么求 $size$ 。如果我们用...
洛谷5268 [SNOI2017]一个简单的询问
LuoguBZOJLOJ分析这样子就可以把每个询问拆成四个，然后莫队即可。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #include <cstring> #include <cstdio> #include ...
洛谷4462 [CQOI2018]异或序列
LuoguBZOJ分析记 $s[i]=a[1]\oplus a[2]\oplus ... \oplus a[i]$ 。问题变为 $[l-1,r]$ 中，有多少对 $(x,y)$ 满足 $s[x]\oplus s[y]=k$ 。莫队即可。代码//It is made by M_sea #include <algorithm> #include <iostream> #i...
洛谷3245 [HNOI2016]大数
LuoguBZOJ分析莫队 Day2两个莫队题海星。首先考虑怎么判断 $[l,r]$ 能被 $P$ 整除。设 $num[i]$ 表示 $i\sim n$ 所构成的数。如果 $[l,r]$ 能被 $P$ 整除，那么有 $\frac{num[l]-num[r+1]}{10^{r-l+1}}\equiv0\pmod P$。这里可以分类讨论一下了。当 $P\neq 2$ 且 $P\neq5$ 时此时...
洛谷3246 [HNOI2016]序列
LuoguBZOJ分析莫队。重点是两个状态怎么 $O(1)$ 的转移。先来考虑从 $[l+1,r]$ 转移到 $[l,r]$ 的情况。这样子会多出来 $[l,l],[l,l+1],...,[l,r]$ 这些区间，我们来考虑这些区间的答案。先找到这段区间的最小值 $p$ ，那么右端点在 $[p,r]$ 之间的区间的贡献都是 $a[p]$ 。还剩下右端点在 $[l,p-1]$ 的情况，把这一部分...