平方分割

POJ K-th Numberを通すまでに苦労したこと ~領域木(l,rの範囲にx以下の値は何個あるか)~

Quiz http://poj.org/problem?id=2104 POJ一般 auto使えない using使えない include bits使えない 苦労したこと 問題文の読み間違い。Aは負値もある cinではなくscanfを使わないとTLE(問題文に書いてある) scanfで読み込み先がintかlong longかで指定を変…

C - GCD on Blackboardを平方分割で解く

Quiz https://atcoder.jp/contests/abc125/tasks/abc125_c Submit https://atcoder.jp/contests/abc125/submissions/5171443 解法 A[i]を除外した場合の左右のgcdを高速に求めたい 累積gcdもいいが、平方分割でも解ける sqrt(N)で配列を分割し、ブロックと呼…