把询问 \(x,y\) 看作平面上的点
记当前时刻 \(t\)，\(l\) 是与 \(i\) 连通的最左端，\(r\) 是与 \(i+1\) 连通的最右端，可以通过 set 维护断边找到
连边 \((i,i+1)\) 时 \(x\in[l,i],y\in[i+1,r]\) 连通了，考虑贡献提前计算，矩形 \(+(q-t)\)。断边时同理 \(-(q-t)\)
剩下的问题是三维偏序。注意询问时刻若 \(x,y\) 连通那么还要 \(-(q-t)\)
[APIO2019] 路灯 题解
发布时间 2023-10-12 22:58:52作者: ft61