我昨天刚学 KDTree ,发现这东西似乎可以完成在二维平面内对一个矩形内的散点信息的修改和查询,然后我就在想能不能通过把每一个数看做 (i,ai) 的一个点然后采用移动右端点的离线套路,每一次修改 ([1,i−1],[ai,amax]) ,然后查询 ([l,r],[1,amax]) 来获得每一组询问的答案,即对于一个逆序对 (x,y) 在 x 处记录贡献。
听说 KDTree 的复杂度是根号的,但是我自己实现了一个但是跑的很慢,本地随机数据都要 6s 以上。
所以是 KDTree 是假的还是我实现假了。毕竟我 KDTree 完全是靠着定义自己写的。