rt,用分块做的。record
可以看到,我开了一个数组:int fk[KS][N<<1];
int fk[KS][N<<1];
由于 N≈105,KS≈150N\approx10^5,KS\approx150N≈105,KS≈150,所以这个数组一共包含 KS×N×2≈3×107KS\times N\times2\approx3\times10^7KS×N×2≈3×107 个整数,空间约为 4×(3×107)B=1.2×108B≈114.5MB4\times(3\times10^7)\operatorname{B}=1.2\times10^8\operatorname{B}\approx114.5\operatorname{MB}4×(3×107)B=1.2×108B≈114.5MB。
那么问题来了,光这个数组就要耗费约 115MB\mathbf{115\operatorname{MB}}115MB 空间,还不算其他零碎的空间(比如 map 的空间),那为什么提交记录上显示的空间仅为 3.47MB\mathbf{3.47\operatorname{MB}}3.47MB?
map
这是不是洛谷的 bug?