【BZOJ1878】【SDOI2009】HH的项链

这题的方法似乎非常非常多

我这种垃圾第一反应是莫队

复杂度似乎不太优秀但是还是可以过的

而且这种方法最好想

第二种方法是设\(p[i]\)为与第\(i\)个贝壳相同的上一个贝壳的编号

那么询问就是在\([l,r]\)内\(p[i]<l\)的贝壳有多少个

离线排序一下挨个加就可以了

另外之前在论文里看到kd-tree也可以做 貌似还可以在线

听说还有划分树的在线做法

说点什么

  Subscribe  
提醒