2020-2021:teams:legal_string:jxm2001:other:错题集_2

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2020-2021:teams:legal_string:jxm2001:other:错题集_2 [2020/08/09 00:03]
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)$。
 注意每次枚举完成可以给整棵树打上子树还原标记，不能暴力重建树，否则时间复杂度过高。
@@ 行 737: / 行 739: @@
 |一阶差分|  1  |  0  |  1  |  0  |  1  |  -1  |  0  |  -1  |  0  |  -1  |  0  |  0  |
 |二阶隔项差分|  1  |  0  |  0  |  0  |  0  |  -1  |  -1  |  0  |  0  |  0  |  0  |  1  |
-|对应位置|  a_1k+3  |  0  |  0  |  0  |  0  |  (a_1+1)k+1  |  (a_1+1)k+2  |  0  |  0  |  0  |  0  |  (a_1+2)k  |
+|对应位置|  $a_1k+3$  |  0  |  0  |  0  |  0  |  $(a_1+1)k+1$  |  $(a_1+1)k+2$  |  0  |  0  |  0  |  0  |  $(a_1+2)k$  |
+于是考虑枚举 $a_1,k$ 即可，时间复杂度 $O(n\log n)$。
+<hidden 查看代码>
+<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>
+</hidden>

2020-2021/teams/legal_string/jxm2001/other/错题集_2.1596902592.txt.gz · 最后更改: 2020/08/09 00:03 由 jxm2001