分块入门题,不错的,建议大家做一做
开始学习
先看一下
这道题想让我们求区间[l,r]>=c的个数,然后我们可以看到“数列分块入门 2”是求区间[l,r]<c(忽略平方)的个数,即求c在区间[l,r]的排名。所以我们可以每一次查询c的排名,然后用区间长度减c的排名就可以达到答案了呢QAQ。
那么题目就被转移成了求区间[l,r]中c的排名
一看题目,咦,求[l,r]区间c的排名,马上就可以想到平衡树啦,可是平衡树这么难写,而且还不支持区间加,那怎么办? 分块!
首先,我们一个一个步骤分着来看:
(1).操作 操作和普通分块的操作一模一样,类个tag,我们先不理。
(2).查询 如果一般查询排名,我们可以将这一段数截出来,排序,然后二分查找(lower_bound操作)就ok了。那我们可不可以先将每一个块的数都排好序,然后查找每一个块的时候就直接二分呢? ofcause,当然可以!那零零散散的剩下的非整块的数就暴力找就可以了。
(3).排序操作 我们查询需要先排序,那么我们排序也成为了一个操作。我们另外开一个数组ve[i](ve[i]为vector,i表示第i个块)来存每个块排序的数据(这里我使用了vector)。到时候查询的时候直接二分ve[i]就可以了。那每一次零散修改操作都会修改数值(整块操作还是直接加tag),那么我们要对有修改数值的那个块重新进行块内排序。(额,好慢啊)
所以这道题的复杂度是O(msqrt(nlogn))
那么我们这个分块的基本思想就是这样了。还有很多小细节可以看看我的代码:
//P2801 教主的魔法#include
广告
如果需要更系统的学习分块可以看我的blog,内容更详细,分解更到位qwq
转载地址:https://blog.csdn.net/weixin_30823001/article/details/95776271 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!