https://atcoder.jp/contests/yahoo-procon2017-final-open/tasks/yahoo_procon2017_final_c

問題概要

整数MとN要素の数列Aが与えられるので、以下の形のQ個のクエリを順に処理せよ。

クエリ: Aの区間[l, r]の全要素にxを加算する。その後、同じ区間内にMの倍数が何個あるかを出力する。

N, M, Q <= 10⁵

A_i <= 10⁹

解法

平方分割をする。平方分割に関しては以下のブログがわかりやすい。

この問題の場合、分割したあとの上位のバケットに対して、以下の2つの情報を記録しておく必要がある。

sum: この区間全体に対して足された数
count: この区間内において 0 ～ M-1 (mod M)の値が何個存在するか

1の方は上記記事の最初に解説されているbucketSumと同じである。2の方はそれぞれの区間でサイズMの配列を持つことで管理する。メモリが心配になるが、Mが小さいので十分収まる。

次にクエリの処理について。まず加算クエリは、区間全体に足せるならsumバケットに足すだけ。区間に一部だけ重なっている場合は、もとの数列の方に直接加算する（このときcountバケットも更新する）。

倍数カウントクエリの方は、まず区間全体に重なっているならcountの値を見ればよい。つまり「Mの倍数 => mod M で 0」であるから、count配列の対応する要素を見るだけでMの倍数の数がわかる。ただしこのとき同じ区間のsumの値に注意が必要で、この値はつまり「その区間全体に足されたことになっている数値」であるから、そのぶん見る場所をずらす必要がある。区間に一部だけ重なっている場合は愚直にひとつひとつMで割り切れるか判定していけばよい。

各処理とも、「区間全体に対する処理」で済ませられる場合にはO(1), 「区間に一部だけ重なっている場合の処理」についてはO(sqrt(N))かかる（区間全体の長さが高々sqrt(N)であるため）。このとき前者の処理回数は高々sqrt(N)回, 後者の処理回数は高々2回（左右のはみだし）であるから、どちらの処理も結局O(sqrt(N))となる。これをQ回繰り返すので最終的な計算量はO(Qsqrt(N)).

感想

初めて平方分割書いた

Aの方がむずない？

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop, std.bitmanip;

immutable int D = 320;

void main() {
    auto s = readln.split.map!(to!int);
    auto N = s[0];
    auto M = s[1];
    auto Q = s[2];
    auto A = readln.split.map!(a => a.to!int % M).array;

    auto SIZE = N / D + 1;
    auto sd_sum = new int[](SIZE);
    auto sd_cnt = new int[][](SIZE, M);

    foreach (i; 0..N) {
        sd_cnt[i/D][A[i]] += 1;
    }

    int add(int a, int b, int x) { // a <= i <= b に x を加算
        int ret = 0;
        for (int i = 0, l = 0, r = D-1; i < SIZE; i += 1, l += D, r += D) {
            if (a <= l && r <= b) {
                sd_sum[i] += x;
                sd_sum[i] %= M;
                ret += sd_cnt[i][(M - sd_sum[i] + M) % M];
            } else if ((l <= a && a <= r) || (l <= b && b <= r)) {
                for (int j = max(a, l); j <= min(b, r, N-1); ++j) {
                    sd_cnt[i][A[j]] -= 1;
                    A[j] += x;
                    A[j] %= M;
                    sd_cnt[i][A[j]] += 1;
                    if ((A[j] + sd_sum[i]) % M == 0) ret += 1;
                }
            }
        }
        return ret;
    }

    while (Q--) {
        s = readln.split.map!(to!int);
        int l = s[0]-1;
        int r = s[1]-1;
        int x = s[2]%M;
        add(l, r, x).writeln;
        debug {
            sd_sum.writeln;
            sd_cnt.writeln;
            A.writeln;
        }
    }
}

nebukuro09の日記

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

問題概要

解法

感想

コード (D言語)