建议撤下空间复杂度不正确的题解并增强数据
查看原帖
建议撤下空间复杂度不正确的题解并增强数据
254688
cool_milo楼主2023/12/5 11:18

JWRuixi的题解对于线段树上的每一个结点都开了一个vector保存要递归到它的子树里的询问,这个复杂度显然高达 Θ(mlog⁡n)\Theta(m \log n) ,不应该通过此题,但是此题没有造极限数据,于是把他放过去了。

我用下面的代码生成了一个 hack 数据,放在了 这里 ,可以在这里发现他MLE了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P = 998244353;
const int N = 3e5, M = 6e5;

int n, m;

int main() {
	freopen("hack.in", "w", stdout);
	printf("%d %d\n", N, M);
	for(int i = 1; i <= N; i++) {
		printf("%d ", N / 2 - i);
	} 
	puts("");
	for(int i = 1; i <= M; i++) {
		printf("%d %d %d\n", 2, N, N);
	}
}

另外似乎误伤了一些常数比较大的线性空间的做法。如 Solystic大佬 的代码也会 MLE

2023/12/5 11:18
加载中...