标签 莫队 下的文章
- 首页
- 莫队
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...
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$ 。代码社交网络【模板】有向图矩阵...
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$ 表示三个区间内出现了...
洛谷5268 [SNOI2017]一个简单的询问
LuoguBZOJLOJ分析这样子就可以把每个询问拆成四个，然后莫队即可。代码//It is made by M_sea #include <algorithm> #include <iostream> #include <cstdlib> #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 #incl...
洛谷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}}\equ...
洛谷3246 [HNOI2016]序列
LuoguBZOJ分析莫队。重点是两个状态怎么 $O(1)$ 的转移。先来考虑从 $[l+1,r]$ 转移到 $[l,r]$ 的情况。这样子会多出来 $[l,l],[l,l+1],...,[l,r]$ 这些区间，我们来考虑这些区间的答案。先找到这段区间的最小值 $p$ ，那么右端点在 $[p,...
洛谷1494 [国家集训队]小Z的袜子
LuoguBZOJ分析莫队。假如第$i$种袜子有$cnt[i]$个，那么抽到一双的概率是然后总的方案数是$C_{len}^2$。概率就是：$\frac{\sum\limits_{i=1}^n\,cnt[i]\cdot(cnt[i]-1)}{len(len-1)}$莫队维护一下分子就行。考虑一下...
洛谷1903 [国家集训队]数颜色 / 维护队列
LuoguBZOJ算法带修改莫队的板子（调了半年qwq）但是我写的常数巨大，吸口氧才能过qwq然而BZOJ都A了在标准莫队的操作上加上一个延时间轴的移动就行了。代码#include <bits/stdc++.h> #define re register using namespac...