2022.12 做题记录

P3674 小清新人渣的本愿

我们考虑使用莫队来解决这个问题.

我们使用一个 bitset 来表示某个数在当前区间是否出现过.记这个 bitsetv

  • 对于询问是否存在两个差为 xx 的数 a,ba,b,我们有 ab=x    a=x+ba-b=x \iff a=x+b,询问就是判断 (v & (v << x)).any()
  • 对于询问是否存在两个和为 xx 的数 a,ba,b,我们考虑选取一个足够大的常数 VV,那么我们有 a+b=x    (Vb)a=Vxa+b=x \iff (V-b)-a=V-x,这样只需要多维护一个 bitset 来表示 VV 减去某个在区间中出现过的数是否存在,记这个 bitsetw,询问就是判断 (v & (w >> (V - x))).any()
  • 对于询问是否存在两个积为 xx 的数 a,ba,b,直接枚举因数即可.

P5355 [Ynoi2017] 由乃的玉米田

前三种询问参考 P3674 小清新人渣的本愿.对于除法询问,我们考虑根号分治.

设定阈值 ww,对于 xwx \ge w 的所有询问,我们在莫队的过程中直接枚举 xx 的倍数,时间复杂度 O(V/w)O(V/w),其中 VV 是值域.

对于 x<wx<w 的所有询问,我们做一个扫描线,记 pip_i 代表 ii 这个元素最后一次出现的位置,qiq_i 代表最大的 ll,满足区间中存在两数的商为 xx.扫描线的过程中,我们需要记录当前最大满足要求的 ll.扫描到 ii 时,先使用 aia_i 更新 paip_{a_i},然后使用 pai×xp_{a_i\times x}pai/xp_{a_i/x} 去更新 ll,最后使用 ll 更新 qiq_i.对于区间 [l,r][l,r] 的询问的答案,判断 qr>lq_r>l 即可.

P2495 [SDOI2011] 消耗战

下文中用关键点来指代能源丰富的岛屿.

如果只有一次询问,我们可以使用树形 dp 来解决这个问题.设 fuf_u 表示使 uu 子树内的所有关键点均不与 uu 联通的最小代价.

w(u,v)w(u,v)(u,v)(u,v) 这一条边的边权,CuC_uuu 的儿子构成的集合,SS 为关键点构成的集合,我们有如下转移:

fuvCu({w(u,v)if vSmin{w(u,v),fv}otherwise)f_u\leftarrow\sum_{v\in C_u} \left( \begin{cases} w(u,v) & \text{if }v\in S \\ \min\{w(u,v),f_v\} & \text{otherwise} \end{cases} \right)

这样做一次 dp 的时间复杂度是 O(n)O(n) 的,若对于每次询问都暴力地做一次 dp,总时间复杂度为 O(nm)O(nm),显然不可接受.

发现 i=1mki\displaystyle\sum_{i=1}^{m} k_i 的大小与 nn 同级,这启发我们去思考复杂度与 kk 相关的 dp 方式.

我们可以发现,由于每次询问的 kk 不大,所以我们做的大多数转移都是在求某条路径上边权的最小值,只有在关键点和关键点之间的 lca 处的转移才会有变动.

我们建立原树的虚树,对于虚树中的两个节点 u,vu,vw(u,v)w(u,v) 就等于原树中 uuvv 的路径上边权的最小值.不难发现在虚树上 dp 的结果和原树一致.

实现上注意多组询问清空时按需清空,不然复杂度会退化.

P2257 YY 的 GCD

不妨令 NMN\le M,令 PP 表示所有质数构成的集合.

每次询问时枚举质数,答案为:

pPi=1Nj=1M[gcd(i,j)=p]\sum_{p\in P}\sum_{i=1}^{N}\sum_{j=1}^{M}[\gcd(i,j)=p]

运用莫比乌斯反演结论,上式可化为:

pPd=1Npμ(d)NpdMpd\sum_{p\in P}\sum_{d=1}^{\left\lfloor\frac{N}{p}\right\rfloor} \mu(d)\left\lfloor\frac{N}{pd}\right\rfloor\left\lfloor\frac{M}{pd}\right\rfloor

按照上式利用数论分块计算的时间复杂度是 O(Tπ(N)N)O\left(T\pi(N)\sqrt{N}\right),不可接受.

u=pdu=pd,枚举 uu,上式可化为:

u=1NNuMukP,kuμ(uk)\sum_{u=1}^N \left\lfloor\frac{N}{u}\right\rfloor\left\lfloor\frac{M}{u}\right\rfloor\sum_{k\in P,k|u}\mu\left(\frac{u}{k}\right)

f(x)=kP,kxμ(xk)\displaystyle f(x)=\sum_{k\in P,k|x}\mu\left(\frac{x}{k}\right).对于所有的 pPp\in P,对 f(kp)f(kp) 的贡献是 μ(k)\mu(k),然后就可以算出所有 f(x)f(x) 的值.求 f(x)f(x) 的前缀和后数论分块计算即可.时间复杂度 O(TN)O\left(T\sqrt{N}\right)

P4462 [CQOI2018] 异或序列

先对原数列做一次异或前缀和,记 sx=i=1xai\displaystyle s_x=\bigoplus_{i=1}^x a_i,询问就是查询 lijr[si1sj]\displaystyle\sum_{l\le i\le j\le r}[s_{i-1}\oplus s_{j}],询问左端点减 11 后即为查询区间内异或和等于 kk 的数对数.

我们使用莫队来解决这个问题,令 cxc_x 表示当前区间内 xx 的个数,插入 sis_i 时,答案加 csikc_{s_i\oplus k},删除时同理.

P4587 [FJOI2016] 神秘数

先考虑没有区间查询时怎么做.

为了求最小的不能被表示的数,我们从小到大插入元素.设当前已经可以表示出的值域区间为 [1,a][1,a],要插入的数为 xx,那么插入后可以表示出的值域区间为 [1,a]{x}[1+x,a+x][1,a]\cup\{x\}\cup[1+x,a+x].若 xa+1x\le a+1,则插入后可以表示的区间为 [1,a+x][1,a+x];若 x>a+1x>a+1,那么 a+1a+1 无法被表示出,答案即为 a+1a+1

进行区间查询时,我们维护一个变量 xx,表示当前可表示出的值域区间为 [1,x][1,x],初始令 a0a\leftarrow0

每次判断 i=lr[aix+1]ai>x\displaystyle\sum_{i=l}^r [a_i\le x+1]a_i>x,若成立则 xi=lr[aix+1]aix\leftarrow\displaystyle\sum_{i=l}^r [a_i\le x+1]a_i,否则答案即为 x+1x+1

不是很会分析这个时间复杂度.