結論から言うと、クエリ平方分割で O(N√Q log(max {A}) + Q(√Q + logQ)) で解けます。 問題概要 atcoder.jp 考えたこと クエリ 1 が曲者で、通常の遅延セグメント木には乗せられないため、仕方なく「困ったときの平方分割」をしてみる。 √Q 回のクエリを 1 …