ABC288D - Range Add Query

import std;

void main () {
    int N, K; readln.read(N, K);
    auto A = readln.split.to!(int[]);
    // クエリO(N)かけられないよな～からスタート。
    // Kが小さいなぁ～
    // じゃあ逆に、最初の列を幅KのRAQで構築したと考えたらどうだろう。
    // -> 重要なのは高々O(K)個のRAQだけで、クエリ区間に含まれるRAQはすべて打ち消すことが出来るじゃないか。
    // -> じゃあ、片方に寄せ集めてこれを消せればOKではないですかね？

    auto acc = new long[](N);
    auto raq = new long[](N);
    foreach (i; 0..N) {
        // もらう
        if (0 < i) acc[i] += acc[i - 1];

        // そこから積む値は？
        raq[i] = A[i] - acc[i];

        // 実際積んでおく
        acc[i] += raq[i];
        if (i + K < N) acc[i + K] -= raq[i];
    }

    auto buf = new long[](N);
    auto q = new int[](0);
    void add (int i, long v) {
        q ~= i;
        buf[i] += v;
    }
    long get (int i) {
        return buf[i];
    }
    void reset () {
        foreach (v; q) buf[v] = 0;
        q.length = 0;
    }

    int Q = readln.chomp.to!int;
    auto ans = new string[](Q);

    foreach (z; 0..Q) {
        int l, r; readln.read(l, r);
        l--, r--;

        reset();

        // 後ろ側のクエリ
        foreach (i; 0..K - 1) {
            add(r - i, raq[r - i]);
        }

        // 前側のクエリ
        foreach (i; 0..K - 1) {
            if (l - i - 1 < 0) break;
            int rem = K - i - 1;

            int d = (r - l + 1) / K;
            add(l + d * K - 1 - (K - rem - 1), -raq[l - i - 1]);
            if (l + d * K <= r) add(l + d * K, raq[l - i - 1]);
        }

        // 累積
        {
            int cur = r - 2 * K;
            while (cur <= r) {
                if (l < cur) add(cur, get(cur - 1));
                cur++;
            }
        }

        // 消せるかトライする。
        {
            int cur = r - 2 * K;
            while (cur <= r) {
                if (l <= cur && cur + K - 1 <= r) {
                    foreach (i; 0..K) {
                        add(cur + K - i - 1, -get(cur));
                    }
                }
                cur++;
            }
        }

        bool ok = true;
        foreach (i; 0..2 * K) {
            if (r - i < l) break;
            if (get(r - i) != 0) ok = false;
        }

        if (ok) {
            ans[z] = "Yes";
        }
        else {
            ans[z] = "No";
        }
    }

    foreach (i; 0..Q) {
        writeln(ans[i]);
    }
}

void read (T...) (string S, ref T args) {
    import std.conv : to;
    import std.array : split;
    auto buf = S.split;
    foreach (i, ref arg; args) {
        arg = buf[i].to!(typeof(arg));
    }
}