【codechefFNCS】Chef and Churu

2014年12月18日1,2610

题解

分块水过

将函数分块,每一块大小√n,预处理一块内的函数统计每一个数字的次数,以及这一块的答案

这一部分n√n

并用树状数组维护a的前缀和,线段树呵呵。。。

对于询问

将整块的答案加起来,其余部分的每个函数在树状数组中查询

对于修改

修改树状数组

依照每一个数字在每一块的次数,更新每一块的答案

这一部分n√nlogn

若理论分析似乎分块设小会更优,但若考虑下常数会发现好像并不会。。。

注意本题要用unsigned long long

还有一个很牛逼的重建分块做法

每√n次操作重建a并维护f的前缀和

每次询问分两部分计算答案

一个是不在块内的修改,由于我们得出F前缀和,这部分就是O1了

在块内的修改,我们把一块内的询问都拆成两个1-x

然后对于每一块,从左到右扫F

维护就是1到当前的F,对于每个位置的答案计算次数

每添加一个F,就相当于把一段的答案计算次数+1

用分块可以做到√n修改,每一块内修改次数是n

块内在这个询问前的修改只有√n个,每个查询只要O1

复杂度是n√n

n√nlogn 分块