2020-2021:teams:legal_string:jxm2001:other:错题集_2
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:legal_string:jxm2001:other:错题集_2 [2020/08/09 00:05] jxm2001 |
2020-2021:teams:legal_string:jxm2001:other:错题集_2 [2020/08/09 00:16] (当前版本) jxm2001 |
||
|---|---|---|---|
| 行 23: | 行 23: | ||
| 考虑倒序枚举每个最小距离，求出该最小距离至少需要的关键点个数，然后更新该关键点个数对应的答案。 | 考虑倒序枚举每个最小距离，求出该最小距离至少需要的关键点个数，然后更新该关键点个数对应的答案。 | ||
| - | 总操作数为 $O(\sum_{i=1}^{n-1} \frac ni)=O(n\log n)$，删除子树和查询祖先操作时间复杂度为 $O(\log n)$，于是总时间复杂度为 $O\left(n\log^2 n\right)$。 | + | 总操作数为 $O(\sum_{i=1}^{n-1} \frac ni)=O(n\log n)$，删除子树和查询祖先操作时间复杂度为 $O(\log n)$。 |
| + | |||
| + | 于是总时间复杂度为 $O\left(n\log^2 n\right)$。 | ||
| 注意每次枚举完成可以给整棵树打上子树还原标记，不能暴力重建树，否则时间复杂度过高。 | 注意每次枚举完成可以给整棵树打上子树还原标记，不能暴力重建树，否则时间复杂度过高。 | ||
| 行 743: | 行 745: | ||
| <hidden 查看代码> | <hidden 查看代码> | ||
| <code cpp> | <code cpp> | ||
| + | const int MAXN=1e5+5; | ||
| + | LL sum[MAXN]; | ||
| + | int main() | ||
| + | { | ||
| + | _for(i,1,MAXN) | ||
| + | for(int k=3;i*k<MAXN;k++){ | ||
| + | if(i*k+3<MAXN)sum[i*k+3]++; | ||
| + | if((i+1)*k+1<MAXN)sum[(i+1)*k+1]--; | ||
| + | if((i+1)*k+2<MAXN)sum[(i+1)*k+2]--; | ||
| + | if((i+2)*k<MAXN)sum[(i+2)*k]++; | ||
| + | } | ||
| + | _for(i,2,MAXN)//二阶隔项差分还原一阶差分 | ||
| + | sum[i]+=sum[i-2]; | ||
| + | _for(i,1,MAXN)//一阶差分还原原序列 | ||
| + | sum[i]+=sum[i-1]; | ||
| + | _for(i,1,MAXN)//前缀和 | ||
| + | sum[i]+=sum[i-1]; | ||
| + | int t=read_int(),kase=0; | ||
| + | while(t--){ | ||
| + | int l=read_int(),r=read_int(); | ||
| + | printf("Case #%d: %lld\n",++kase,sum[r]-sum[l-1]); | ||
| + | } | ||
| + | return 0; | ||
| + | } | ||
| </code> | </code> | ||
| </hidden> | </hidden> | ||
2020-2021/teams/legal_string/jxm2001/other/错题集_2.1596902758.txt.gz · 最后更改: 2020/08/09 00:05 由 jxm2001
