P7217 题解

· · 个人记录

题意

一个长为 l 的圆上有 n 个人和 m 个苹果，初始人在顺时针方向位置 a_i，苹果在位置 b_i。人会按顺时针以 1 的速度绕着圆走，走到一个苹果就会吃掉它。一个苹果被吃掉之后 C 时刻会在原位置长出一个新的。q 次询问，每次问一个人 x 在 t 时刻之前吃了几个苹果。n,m,q\le 2\times 10^5。

思路

离线询问。求出每个人收获苹果后下一个收获这个苹果的人是谁，则构成内向基环树森林，对每个连通块单独考虑。如果将苹果看做点，向第一次收获它的人连边，所有边权都是经过时间，则边相当于传送带，苹果在上面滚，它滚到一个人就会给他的答案 +1。求出所有点深度 d，对于树上的点，一次询问求的是子树内有多少节点满足 d\le d_x+v，搞出 dfs 序之后转化为二维偏序，容易计算。

下面计算环上的贡献。记环上每个点到第一个点距离为 s_i，环长为 L。下面直接把环之外的点删掉，从苹果向环点连 d 的边。考虑环上两个点 i\le j 的贡献。对于一个 i 权值为 d 的儿子，它首次到达 j 的时刻是 d+s_j-s_i，此后每过 L 时刻会再来一次。所以贡献是 \lfloor\dfrac{v-d-s_j+s_i}L\rfloor+1，扫描过程中维护已经经过的点中 f_x=d_x-s_i 的值的集合，维护这个集合的时候不维护值，而是维护除以 L 下取整的结果 p_x 以及余数 m_x（注意负数）。记 w=v-s_j，那么首先 f_x>w 的可以无视。记 P=w/L 下取整，M=w\bmod L，则贡献为 P-p_x+\lfloor\dfrac{M-m_x}L\rfloor+1。事实上这个限制可以不用收紧到 f_x\le w，只需要 p_x\le P 即可，因为如果 p_x=P,m_x>M，这个式子的值是 0，所以不影响答案。因此我们现在使用某种数据结构，需要查询 p_x\le P,m_x\le M 的值的 p_x 之和以及个数。同理需要查询 p_x\le P,m_x>M 的类似信息。也就是单点修改，矩形查询和。考虑 CDQ 分治。具体地，我们拆环成链，然后对 j 有贡献的 x 需要满足 j-m<fa_x\le j，其中 m 是环上点数，这样就转化为经典的三维偏序。为了方便起见，我们对 P 分治处理。

整个流程如下：

  1. 二分每个人与苹果，计算出 nxt，并求出基环树以及 dep,L,s 等信息。
  2. 求树上答案：对于询问 (x,t)，询问区间为 i\in [in_x,out_x],d\in [0,d_x+t]
  3. 对每个苹果以及询问计算出 p,m，并离散化
  4. 对 p 分治，每次计算 [l,mid]\to [mid+1,r] 的贡献（注意 l\to l 也有贡献）：对于询问 j,m，询问区间为 x\in[j-n+1,j],v\in [0,m]，这一段区间内的贡献是 cnt*(p+1)-sum，v\in [m+1,L] 这一段的贡献是 cnt*p-sum。用两个 BIT 分别维护个数与和。
  5. 对每个连通块重复上述步骤即可