分块

  晚上脑子涨涨的,就总结一下最近写的分块入门9题吧。以下全是个人浅薄理解。

  分块,一般就是把一组数据分成sqrt(n)块,然后根据题目要求,对其进行维护。基本要写的就是belong[N],还可以写l[N],r[N]来保存每一块的左右边界,要注意最后一块的有边界要设置为n。

       tips:写blo=sqrt(n)后,不能把块数num直接赋值为blo然后判断余数加一,而是要赋值n/blo。因为sqrt取整,可能会造成缺块。

     写9的时候,发现用bool判断01会比int快很多,一个卡在1500ms边缘的测试用例就变得只用五六百。

未完。。。

原文地址:https://www.cnblogs.com/XXrll/p/11128507.html