一点关于RE的疑问

microchip @ 2024-05-28 20:51:36

by littlesnake @ 2024-05-28 21:19:30

本来就是4倍吧（忘了应该是的）

by microchip @ 2024-05-29 14:40:09

@littlesnake 但是我打的是动态开点啊，堆式建树才需要开四倍吧

by sgl654321 @ 2024-05-31 12:55:57

@microchip 错误的。

你想，插入一个点，最多是不是会新开 \log n 个节点。

所以理论上，你应该开：O(q\log n) 个节点。

但是又由于线段树最多上界只有 4 \times n、

所以你要开的是 \max (q\log n, 4\times n)。

by microchip @ 2024-05-31 19:00:45

@sgl654321 抱歉没太懂，q 是什么，还有既然上界是 4*n 为什么是max

by microchip @ 2024-05-31 19:02:47

而且曾经打过一个没有用class的动态开点，开的也是200050，但是没有RE

by sgl654321 @ 2024-06-01 08:44:15

@microchip 一个动态开点线段树，每新修改一次，最多新建 \log n 个节点。同时，如果把整个线段树开满了，那要用 4\times n 个节点。

在实际使用中，你需要考虑到底会不会把线段树直接开满。

如果直接开满了，例如本题，一上来就输入了 n 个数，你需要把它全部插入线段树中，当然是开满了。这个时候，你就应该开 4\times n，不管是动态开点还是非动态开点。

否则，有些情况是值域线段树，值域非常之大，例如有 10^9。但是插入的数的个数只有 10^5 这个级别。那你就只能使用动态开点线段树，开 10^5\log10^9 的空间。

by microchip @ 2024-06-02 19:00:06

@sgl654321 啊？每新修改一次，最多新建 log n个节点？我打的不是主席树啊