文章目录
- 题目
- 思路
-
- 法一
- 法二
- 法三
题目
Luogu
思路
法一
首先 O(nm)O(nm)O(nm) 检验 li≤kd≤ril_i\le kd\le r_ili?≤kd≤ri?
意味着检验
?lik?≤d≤?rik?\lceil\frac{l_i}{k}\rceil\le d\le \lfloor \frac{r_i}{k}\rfloor?kli???≤d≤?kri???
此时发现右边可以数论分块，对于 k∈[l,r]k\in[l,r]k∈[l,r] 一段相同的右边值显然 kkk 取 rrr 最优
for(int i=1;i<=n;i++){
int p=read(),q=read(),L,R=m+1;for(int l=1,r;l<=q;l=r+1){
r=q/(q/l);L=(p+r-1)/r,R=min(R,q/l);if(L<=R)cha[L]++,cha[R+1]--,R=L-1;}}
但是这道题目有点卡，里面进行了 444 次除法
继续变形发现
?li?1k?<d≤?rik?\lfloor \frac{l_i-1}{k}\rfloor< d\le \lfloor \frac{r_i}{k}\rfloor?kli??1??<d≤?kri???
这时候可以一起分块了，但是注意 k=lik=l_ik=li? 时候是可以的
但是还是会 T 掉
然后发现可以
?li?1d?<?rid?\lfloor \frac{l_i-1}{d}\rfloor< \lfloor \frac{r_i}{d}\rfloor?dli??1??<?dri???
就可以过了
for(int i=1;i<=n;i++){
int p=read()-1,q=read();cha[p+1]++,cha[q+1]--;for(int l=1,r;l<=p;l=r+1){
r=min(p/(p/l),q/(q/l));if(p/l<q/l)cha[l]++,cha[r+1]--;}
}
时间复杂度 O(nm)O(n\sqrt m)O(nm?)
法二
假设现在计算 ddd 的种类，对于到达时刻集合 {a1,a2,...a,t}\{a_1,a_2,...a,_t\}{
a1?,a2?,...a,t?}
我们可以统计出 fif_ifi? 不包含 aj,j∈[1,i?1]a_j,j\in[1,i-1]aj?,j∈[1,i?1] 但包含 aia_iai? 的个数
然后累加即可
发现等于每次查询 l∈[ai?1+1,ai],r∈[ai,m]l\in[a_{i-1}+1,a_i],r\in[a_i,m]l∈[ai?1?+1,ai?],r∈[ai?,m] 的区间个数，可以用主席树实现
时间复杂度 O(nlog2n)O(nlog^2n)O(nlog2n)
法三
很巧妙，我们从小到大枚举 ddd ，发现 len≥dlen\ge dlen≥d 的区间一定能统计入答案， len<dlen<dlen<d 的最多只会被一个点覆盖
那么 len≥dlen\ge dlen≥d 的区间我们可以直接统计，len<dlen<dlen<d 的插入树状数组后单点查询累加
时间复杂度 O(nlog2n)O(nlog^2n)O(nlog2n)