平方分割

みんなのプロコン (2017) 本選 C - 倍数クエリ

問題概要 整数MとN要素の数列Aが与えられるので、以下の形のQ個のクエリを順に処理せよ。 クエリ: Aの区間[l, r]の全要素にxを加算する。その後、同じ区間内にMの倍数が何個あるかを出力する。 N, M, Q <= 105 A_i <= 109 解法 平方分割をする。 平方分割に…