rt，@XiaoQuQu 的题解中给出的代码在每次分治的时候都带了个 $T$，所以时间复杂度其实是 $O(ST+NS\log S)$。可以用如下代码生成数据将其叉掉。

#include <bits/stdc++.h>
using namespace std;

int n = 1, S = (1 << 16), T = 100000;

int main() {
	freopen("hack.in", "w", stdout);
	printf("%d %d %d\n", n, S, T);
	for (int i = 1; i <= S; i++) printf("%d%c", min(i, T), " \n"[i == S]);
	return 0;
}

实测跑了 30s 没跑出来，，，