想不通,如果单次淀粉质复杂度为 O(nlogn)\mathcal{O}({n\log n})O(nlogn) 的话,那么进行 mmm 次询问,时间复杂度应当是 O(nmlogn)\mathcal{O}(nm\log n)O(nmlogn),事实上淀粉质模板里大多数题解都是这样分析的。
那既然如此,为什么昨晚 ABC F 题采用淀粉质做法,时间复杂度会是 O(nlogn)\mathcal{O}(n\log n)O(nlogn) 呢,其中询问跟点数都达到了 2×1052\times 10^52×105,比常见的淀粉质题目都大了特别多。
https://www.luogu.com.cn/paste/n7rh0ls4