我们考虑使用莫队来解决这个问题.
我们使用一个 bitset
来表示某个数在当前区间是否出现过.记这个 bitset
为 v
.
对于询问是否存在两个差为 x x x 的数 a , b a,b a , b ,我们有 a − b = x ⟺ a = x + b a-b=x \iff a=x+b a − b = x ⟺ a = x + b ,询问就是判断 (v & (v << x)).any()
.
对于询问是否存在两个和为 x x x 的数 a , b a,b a , b ,我们考虑选取一个足够大的常数 V V V ,那么我们有 a + b = x ⟺ ( V − b ) − a = V − x a+b=x \iff (V-b)-a=V-x a + b = x ⟺ ( V − b ) − a = V − x ,这样只需要多维护一个 bitset
来表示 V V V 减去某个在区间中出现过的数是否存在,记这个 bitset
为 w
,询问就是判断 (v & (w >> (V - x))).any()
.
对于询问是否存在两个积为 x x x 的数 a , b a,b a , b ,直接枚举因数即可.
前三种询问参考 P3674 小清新人渣的本愿 .对于除法询问,我们考虑根号分治.
设定阈值 w w w ,对于 x ≥ w x \ge w x ≥ w 的所有询问,我们在莫队的过程中直接枚举 x x x 的倍数,时间复杂度 O ( V / w ) O(V/w) O ( V / w ) ,其中 V V V 是值域.
对于 x < w x<w x < w 的所有询问,我们做一个扫描线,记 p i p_i p i 代表 i i i 这个元素最后一次出现的位置,q i q_i q i 代表最大的 l l l ,满足区间中存在两数的商为 x x x .扫描线的过程中,我们需要记录当前最大满足要求的 l l l .扫描到 i i i 时,先使用 a i a_i a i 更新 p a i p_{a_i} p a i ,然后使用 p a i × x p_{a_i\times x} p a i × x 和 p a i / x p_{a_i/x} p a i / x 去更新 l l l ,最后使用 l l l 更新 q i q_i q i .对于区间 [ l , r ] [l,r] [ l , r ] 的询问的答案,判断 q r > l q_r>l q r > l 即可.
下文中用关键点来指代能源丰富的岛屿.
如果只有一次询问,我们可以使用树形 dp 来解决这个问题.设 f u f_u f u 表示使 u u u 子树内的所有关键点均不与 u u u 联通的最小代价.
记 w ( u , v ) w(u,v) w ( u , v ) 为 ( u , v ) (u,v) ( u , v ) 这一条边的边权,C u C_u C u 为 u u u 的儿子构成的集合,S S S 为关键点构成的集合,我们有如下转移:
f u ← ∑ v ∈ C u ( { w ( u , v ) if v ∈ S min { w ( u , v ) , f v } 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)
f u ← v ∈ C u ∑ ( { w ( u , v ) min { w ( u , v ) , f v } if v ∈ S otherwise )
这样做一次 dp 的时间复杂度是 O ( n ) O(n) O ( n ) 的,若对于每次询问都暴力地做一次 dp,总时间复杂度为 O ( n m ) O(nm) O ( n m ) ,显然不可接受.
发现 ∑ i = 1 m k i \displaystyle\sum_{i=1}^{m} k_i i = 1 ∑ m k i 的大小与 n n n 同级,这启发我们去思考复杂度与 k k k 相关的 dp 方式.
我们可以发现,由于每次询问的 k k k 不大,所以我们做的大多数转移都是在求某条路径上边权的最小值,只有在关键点和关键点之间的 lca 处的转移才会有变动.
我们建立原树的虚树,对于虚树中的两个节点 u , v u,v u , v ,w ( u , v ) w(u,v) w ( u , v ) 就等于原树中 u u u 到 v v v 的路径上边权的最小值.不难发现在虚树上 dp 的结果和原树一致.
实现上注意多组询问清空时按需清空,不然复杂度会退化.
不妨令 N ≤ M N\le M N ≤ M ,令 P P P 表示所有质数构成的集合.
每次询问时枚举质数,答案为:
∑ p ∈ P ∑ i = 1 N ∑ j = 1 M [ gcd ( i , j ) = p ] \sum_{p\in P}\sum_{i=1}^{N}\sum_{j=1}^{M}[\gcd(i,j)=p]
p ∈ P ∑ i = 1 ∑ N j = 1 ∑ M [ g cd( i , j ) = p ]
运用莫比乌斯反演结论,上式可化为:
∑ p ∈ P ∑ d = 1 ⌊ N p ⌋ μ ( d ) ⌊ N p d ⌋ ⌊ M p d ⌋ \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
p ∈ P ∑ d = 1 ∑ ⌊ p N ⌋ μ ( d ) ⌊ p d N ⌋ ⌊ p d M ⌋
按照上式利用数论分块计算的时间复杂度是 O ( T π ( N ) N ) O\left(T\pi(N)\sqrt{N}\right) O ( T π ( N ) N ) ,不可接受.
令 u = p d u=pd u = p d ,枚举 u u u ,上式可化为:
∑ u = 1 N ⌊ N u ⌋ ⌊ M u ⌋ ∑ k ∈ P , k ∣ u μ ( u k ) \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)
u = 1 ∑ N ⌊ u N ⌋ ⌊ u M ⌋ k ∈ P , k ∣ u ∑ μ ( k u )
令 f ( x ) = ∑ k ∈ P , k ∣ x μ ( x k ) \displaystyle f(x)=\sum_{k\in P,k|x}\mu\left(\frac{x}{k}\right) f ( x ) = k ∈ P , k ∣ x ∑ μ ( k x ) .对于所有的 p ∈ P p\in P p ∈ P ,对 f ( k p ) f(kp) f ( k p ) 的贡献是 μ ( k ) \mu(k) μ ( k ) ,然后就可以算出所有 f ( x ) f(x) f ( x ) 的值.求 f ( x ) f(x) f ( x ) 的前缀和后数论分块计算即可.时间复杂度 O ( T N ) O\left(T\sqrt{N}\right) O ( T N ) .
先对原数列做一次异或前缀和,记 s x = ⨁ i = 1 x a i \displaystyle s_x=\bigoplus_{i=1}^x a_i s x = i = 1 ⨁ x a i ,询问就是查询 ∑ l ≤ i ≤ j ≤ r [ s i − 1 ⊕ s j ] \displaystyle\sum_{l\le i\le j\le r}[s_{i-1}\oplus s_{j}] l ≤ i ≤ j ≤ r ∑ [ s i − 1 ⊕ s j ] ,询问左端点减 1 1 1 后即为查询区间内异或和等于 k k k 的数对数.
我们使用莫队来解决这个问题,令 c x c_x c x 表示当前区间内 x x x 的个数,插入 s i s_i s i 时,答案加 c s i ⊕ k c_{s_i\oplus k} c s i ⊕ k ,删除时同理.
先考虑没有区间查询时怎么做.
为了求最小的不能被表示的数,我们从小到大插入元素.设当前已经可以表示出的值域区间为 [ 1 , a ] [1,a] [ 1 , a ] ,要插入的数为 x x x ,那么插入后可以表示出的值域区间为 [ 1 , a ] ∪ { x } ∪ [ 1 + x , a + x ] [1,a]\cup\{x\}\cup[1+x,a+x] [ 1 , a ] ∪ { x } ∪ [ 1 + x , a + x ] .若 x ≤ a + 1 x\le a+1 x ≤ a + 1 ,则插入后可以表示的区间为 [ 1 , a + x ] [1,a+x] [ 1 , a + x ] ;若 x > a + 1 x>a+1 x > a + 1 ,那么 a + 1 a+1 a + 1 无法被表示出,答案即为 a + 1 a+1 a + 1 .
进行区间查询时,我们维护一个变量 x x x ,表示当前可表示出的值域区间为 [ 1 , x ] [1,x] [ 1 , x ] ,初始令 a ← 0 a\leftarrow0 a ← 0 .
每次判断 ∑ i = l r [ a i ≤ x + 1 ] a i > x \displaystyle\sum_{i=l}^r [a_i\le x+1]a_i>x i = l ∑ r [ a i ≤ x + 1 ] a i > x ,若成立则 x ← ∑ i = l r [ a i ≤ x + 1 ] a i x\leftarrow\displaystyle\sum_{i=l}^r [a_i\le x+1]a_i x ← i = l ∑ r [ a i ≤ x + 1 ] a i ,否则答案即为 x + 1 x+1 x + 1 .
不是很会分析这个时间复杂度.