若干问题 求大佬们看一眼 给出部分的回答也可

学术版

1nes @ 2024-11-28 10:06:52

T1

给定a b 通过加1 减1 乘2 将a变成b 最小化操作数
a , b 范围10^{500}

T2

part1
给定区间[1 , S] 以及n条线段 线段i覆盖区间[l_i , r_i] 有m组询问
对于每次询问 给出opt
若opt为1 给出x 问 点x处线段覆盖数
若opt为2 给出x 问 覆盖数超过x的点有多少

part2
对于part1 线段i多一个权值w
询问中的覆盖数改为覆盖的线段的权值和

part3 对于part1 询问改为
若opt为1 给出区间l ， r 问覆盖l ， r的线段有多少条
若opt为2 给出区间l ， r 问覆盖l ， r最少需要几条线段
若opt为3 给出区间l ， r 以及x 问l ， r中有多少点被线段覆盖数多于x

part4 part3的在线版本

part5
对于part3 线段i多一个权值w
询问opt2 多一个权值w 问每个点的覆盖线段权值和不小于w的最小线段数
询问opt3 中的覆盖数改为覆盖线段的权值和

by 1nes @ 2024-11-28 10:08:11

第二题S范围1e9 , n , m 1e5

by 1nes @ 2024-11-28 10:16:20

@1nesw也是1e9

by XuYueming @ 2024-11-28 10:32:55

@1nes T1 很典啊，Naughty fairies 黑暗爆炸 2577。

by XuYueming @ 2024-11-28 10:33:36

@1nes 去，数据范围怎么一样，你想问的就是这题吗？

by Colinxu2020 @ 2024-11-28 10:33:57

T2

part1.

离线所有的计数，差分维护线段（dif_l \gets dif_l+1,dif_{r+1} \gets dif_{r+1}-1），令 w_i \gets w_{i-1}+dif_{i}，特别地 w_0=0，操作①直接输出 w_i，对 w_i 计数，令 c_i 为 w_j= 的 j 的数量，操作②输出 c_i 即可。

by XuYueming @ 2024-11-28 10:41:24

完了，T1 怎么做？

by Colinxu2020 @ 2024-11-28 10:48:59

part2. 同理，但是令 dif_l \gets dif_l+w,dif_{r+1} \gets dif_{r+1}-w 即可。

part3. 离线所有询问，线段按右端点从小到大排序，\forall 1 \leq r \leq n，基于堆维护所有包含 r 的线段，当 a_{i,l}=r（a_i 代表所有线段）时加入（\forall a_{i,l} \leq j \leq a_{i,r}, w_{j} \gets w_{j}+1），当 a_{i,r}=r-1 时弹出即可。

对于操作①输出 w_l 即可，可能需要离散化，每次询问 O(1)。

对于操作②，从 x=l 开始，每次令 x=\max r 使得存在一个线段同时包含 l,r，直接查上面的堆顶即可，直到 x=r，暴力会超时，不妨倍增，令 f_{i,j} 代表从 x=i 开始，按上面的方法跳 2^j 次跳到的下标，每次询问 \log。

对于操作③类似于操作①，再多维护一个 c_i 的前缀和即可，每次询问 O(1)。

by 1nes @ 2024-11-28 10:53:03

感谢

by Colinxu2020 @ 2024-11-28 10:53:54

part4.

操作②③不受强制在线影响，不管（操作②原题CF175E）。操作①直接用主席树维护即可（等价于求 l' \leq l, r' \geq r 的数量）。

part5.

做法没有本质区别吧

by Colinxu2020 @ 2024-11-28 10:54:26

@1nes

| 下一页