这是一道挂羊头卖狗肉的题。(虽然我也不知道究竟能不能用线段树解决)但是分块实在是太方便了。

题意

给定一个长度为n的序列和一个正整数k,有m次操作。(n,m,k<=105)每次操作是将一个区间[a,b]加上一个数c,或者询问区间[a,b]中是k的整数倍的数有几个。

思路

可以用分块大法。每一块保存这个块中处以k为各个余数的数的个数,以及这些数同时加上了多少。这样就可以O(sqrt(n))修改,查询。
(1) 如果当前修改一整块,则直接修改“这些数同时加上了多少”
(2) 如果当前修改块部分,则修改“这个块中处以k为各个余数的个数”