社区讨论

吐槽数据

TTo_our_starry_sea
AT_arc069_d[ARC069F] Flags参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lzb6ecya
此快照首次捕获于
2024/08/01 19:11
2 年前
此快照最后确认于
2024/08/01 20:19
2 年前
查看原帖
虽然是 at 上的题，加强不了数据，但还是想吐槽一下。
我在每次确定覆盖的左右区间时，用的是双指针，然而我写成了下面的东西：
CPP
for (int i = 1; i <= 2 * n; i++) L[i] = 1, R[i] = 2 * n;
	for (int i = 1; i <= 2 * n; i++) {
		while (L[i] < i && a[i].x - a[L[i]].x >= K) L[i]++;
		if (L[i] < i) change(1, 1, 2 * n, L[i], i - 1, a[i].id);
	}
	for (int i = 2 * n; i >= 1; i--) {
		while (R[i] > i && a[R[i]].x - a[i].x >= K) R[i]--;
		if (R[i] > i) change(1, 1, 2 * n, i + 1, R[i], a[i].id);
	}
不出意料，这玩意 TLE 了
然后我调了半天，发现了傻逼问题我改成了下面的东西：
CPP
for (int i = 1; i <= 2 * n; i++) L[i] = 1, R[i] = 2 * n;
	for (int i = 1; i <= 2 * n; i++) {
		L[i] = max(L[i], L[i - 1]);
		while (L[i] < i && a[i].x - a[L[i]].x >= K) L[i]++;
		if (L[i] < i) change(1, 1, 2 * n, L[i], i - 1, a[i].id);
	}
	for (int i = 2 * n; i >= 1; i--) {
		R[i] = max(R[i], R[i + 1]);
		while (R[i] > i && a[R[i]].x - a[i].x >= K) R[i]--;
		if (R[i] > i) change(1, 1, 2 * n, i + 1, R[i], a[i].id);
	}
注意到这个东西在计算右端点时总共还是 O(n2log⁡L)O(n^2\log L) 的，然而就跑过去了，虽然是 5s，还是很离谱的
吐槽一波

回复

共 1 条回复，欢迎继续交流。

正在加载回复...