AtCoder Regular Contest 083: F - Collecting Balls

https://beta.atcoder.jp/contests/arc083/tasks/arc083_d

問題概要

2次元平面上に2N個のロボットと2N個のボールがある。ロボットはx軸上のx座標1〜Nの箇所にN個、y軸上のy座標1〜Nの箇所にN個それぞれ設置されている。x軸上のロボットは起動されるとx=a上にあるボールでまだ残っているもののうち最もy座標が小さいものを回収し停止する。y軸上のロボットもy=b上のボールに対して同様に動作する。2N個のボールの座標が与えられたとき、ボールをすべて回収できるようなロボットの起動のさせ方の順番は何通りあるか求めよ。

N <= 10⁵

解法

いったん順番は無視して、どのボールをどのロボットで回収するかという対応づけを考える。(x, y)にあるボールは(x, 0)のロボで取るか(0, y)のロボで取るかの2通りしかない。ここでロボットを頂点、ボールを辺としてとらえてロボ(x, 0)とロボ(0, y)をボール(x, y)が繋いでいるという形のグラフを作る。すると「ボールの回収」という事象は「ある頂点uとそこにつながっているある辺e」をひとつの組としてマッチングさせることに帰着される。ボールとロボットは1対1対応でなければならないこと、またすべてのボールを回収しなければならないことから、構築したグラフのすべての頂点と辺で過不足・重複なく組をつくることが「すべてのボールを回収する」ための必要条件である。グラフは非連結になりうるが、各連結成分どうしは順番に関して明らかに独立なので、個別に考えてよい（あとで答えを合成することも問題なくできる）。よって以降はグラフが連結であると仮定する。

ボールを取り切る、つまり頂点と隣接辺の組を過不足・重複なく作るためには、まず明らかに頂点数=辺数でなければならない。そうでないなら答えは0として終了して良い。頂点数=辺数の単純無向グラフは、木に1本辺が足された形をしている（俗に「なもりグラフ」などと呼ばれているやつ）。これはひとつの閉路から何本も木が生えているもの、というふうに見ることができる。ここで閉路に含まれない頂点に対応する辺は一意に定まる（葉の方から削っていくことを考えればよい）。すると閉路が残るが、閉路でのマッチングのさせかたは回る方向によって2通りありうる。これは両方考慮する必要がある。

頂点と辺の組(=ボールとロボの組)を決めたら、あとは順番を計算していく。回収においては「このボールをこのロボットに回収させるためには、事前にこのボールは回収されていなければならない」という順序の制約がある。例えば(x, 0)のロボットが(x, y)のボールを回収するためには、事前に(x, 1), (x, 2), ..., (x, y-1) にあるボールは回収されていなければいけない。今度はボールとロボの組を頂点とみなしてこのような順序関係を再びグラフにしていくと、できたグラフにおける「トポロジカル順序を守った上で並び替える方法の総数」がすなわちこの組み合わせにおけるありえる並び替えの総数となる。一般的なDAGではこのような計算は指数オーダーになってしまうが（たぶん）、この問題の条件の元でこうして作ったグラフは必ず森になるので、木DPみたいな感じで線形オーダーで総数を計算することができる。なぜ森になるかというと順序の制約が発生する場合は必ず「小さい座標のものが大きい座標のものより先」になるため。xy平面上でいうと必ず上か右に順序の矢印が向かうので、閉路は発生し得ない。

感想

解説を見て解法の概要は結構素直に飲み込めてもそれを実装に落とすところがめちゃくちゃ大変だった

コード (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;

alias Point = Tuple!(int, "x", int, "y");
alias Edge = Tuple!(int, "to", int, "x", int, "y");

immutable long MOD = 10^^9 + 7;

void main() {
    auto N = readln.chomp.to!int;
    auto G = new Edge[][](2*N); // ロボットが頂点、ボールが辺
    auto uf = new UnionFind(2*N);
    auto balls = new Point[](2*N);
    auto deg = new int[](2*N);
    auto used = new bool[](2*N);
    auto stack = new int[](2*N);
    foreach (i; 0..2*N) {
        auto s = readln.split.map!(to!int);
        int x = s[0] - 1;
        int y = s[1] - 1;
        balls[i] = Point(x, y);
        G[x] ~= Edge(y + N, x, y);
        G[y + N] ~= Edge(x, x, y);
        deg[x] += 1;
        deg[y + N] += 1;
        uf.unite(x, y + N);
    }

    long[] F = new long[](2*N+1);
    F[0] = 1;
    foreach (i; 0..2*N) F[i+1] = F[i] * (i + 1) % MOD;

    foreach (i; 0..2*N) { // 各連結成分において 辺数 = 頂点数 が成り立ってないと駄目
        if (uf.find(i) != i) {
            continue;
        }
        if (uf.edges[i] != uf.group[i].length) {
            writeln(0);
            return;
        }
    }


    long topological_count(const long[] len, const long[] num) {
        long ret = F[len.sum];
        foreach (i; 0..len.length) {
            ret = ret * powmod(F[len[i]], MOD-2, MOD) % MOD;
            ret = ret * num[i] % MOD;
        }
        return ret;
    }

    long calc(Tuple!(int, Edge)[] matching) {
        int n = matching.length.to!int;

        Tuple!(int, int)[int] X;
        Tuple!(int, int)[int] Y;

        auto tree = new int[][](n);
        auto is_root = new bool[](n);
        fill(is_root, true);

        foreach (i; 0..n) {
            if (matching[i][0] < N) {
                X[matching[i][1].x] = tuple(matching[i][1].y, i);
            } else {
                Y[matching[i][1].y] = tuple(matching[i][1].x, i);
            }
        }

        // ひとつのマッチングをひとつの頂点とみなして、マッチングの順序関係からDAGをつくる(必ず有向森になる)

        foreach (i; 0..n) {
            if (matching[i][0] < N) {
                if (matching[i][1].y in Y && matching[i][1].x < Y[matching[i][1].y][0]) {
                    tree[Y[matching[i][1].y][1]] ~= i;
                    is_root[i] = false;
                }
            } else {
                if (matching[i][1].x in X && matching[i][1].y < X[matching[i][1].x][0]) {
                    tree[X[matching[i][1].x][1]] ~= i;
                    is_root[i] = false;
                }
            }
        }

        // つくった森をトポロジカルソートするやり方が何通りあるか数える

        Tuple!(long, long) dfs(int n, int p) {
            long[] len, num;
            foreach (m; tree[n]) {
                if (m == p) continue;
                auto t = dfs(m, n);
                len ~= t[0];
                num ~= t[1];
            }
            return tuple(len.sum+1, topological_count(len, num));
        }

        long[] len, num;
        foreach (i; 0..n) {
            if (!is_root[i]) continue;
            auto t = dfs(i, -1);
            len ~= t[0];
            num ~= t[1];
        }

        return topological_count(len, num);
    }

    long solve(const int[] nodes) {
        int[] cycle_nodes;
        Edge[] cycle_edges;
        Tuple!(int, Edge)[] not_cycle;

        int sp = -1;
        foreach (n; nodes) if (deg[n] == 1) stack[++sp] = n;

        while (sp >= 0) {
            int n = stack[sp--];
            used[n] = true;
            foreach (e; G[n]) {
                if (used[e.to]) continue;
                deg[e.to] -= 1;
                if (deg[e.to] == 1) stack[++sp] = e.to;
                not_cycle ~= tuple(n, e);
                break;
            }
        }

        foreach (start; nodes) {
            if (used[start]) continue;
            int next = start;
            while (cycle_nodes.empty || next != start) {
                cycle_nodes ~= next;
                int cur = next;
                used[cur] = true;
                foreach (e; G[cur]) {
                    if (e.to == start && cycle_nodes.length == 2) continue;
                    if (e.to != start && used[e.to]) continue;
                    cycle_edges ~= e;
                    next = e.to;
                    break;
                }
            }
            break;
        }


        Tuple!(int, Edge)[] cycle1; // サイクル順周り
        Tuple!(int, Edge)[] cycle2; // サイクル逆周り
        int cnt = cycle_nodes.length.to!int;

        foreach (i; 0..cnt) {
            cycle1 ~= tuple(cycle_nodes[i], cycle_edges[i]);
        }
        foreach (i; 0..cnt) {
            cycle2 ~= tuple(cycle_nodes[(i+1)%cnt], Edge(cycle_nodes[i], cycle_edges[i].x, cycle_edges[i].y));
        }

        return (calc(cycle1 ~ not_cycle) + calc(cycle2 ~ not_cycle)) % MOD;
    }


    long[] len, num;

    foreach (i; 0..2*N) {
        if (uf.find(i) != i) {
            continue;
        }
        len ~= uf.group[i].length.to!long;
        num ~= solve(uf.group[i]);
    }

    long ans = topological_count(len, num);
    ans.writeln;
}


class UnionFind {
    int N;
    int[] table;
    int[][] group;
    int[] edges;

    this(int n) {
        N = n;
        table = new int[](N);
        fill(table, -1);
        group = N.iota.map!(i => [i]).array;
        edges = new int[](N);
    }

    int find(int x) {
        return table[x] < 0 ? x : (table[x] = find(table[x]));
    }

    void unite(int x, int y) {
        x = find(x);
        y = find(y);
        if (x == y) {
            edges[x] += 1;
            return;
        }
        if (table[x] > table[y]) swap(x, y);
        table[x] += table[y];
        table[y] = x;
        group[x] ~= group[y].dup;
        group[y] = [];
        edges[x] += edges[y] + 1;
    }
}

long powmod(long a, long x, long m) {
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}

AtCoder Regular Contest 071: F - Infinite Sequence

https://beta.atcoder.jp/contests/arc071/tasks/arc071_d

問題概要

整数Nが与えられたとき、以下の性質をすべて満たす数列が何通りあるか求めよ。

• 数列は無限長で、各要素は1〜Nのいずれかの整数である
• 数列の第N項以降はすべて同じ値である
• 数列のある要素がaであったとき、続くa個の要素はすべて同じ値である (aと同じである必要はない)

N <= 10⁶

解法

左から数列を埋めていくことを考える。数列の性質を考えると、2以上の数のあとにまた2以上の数が来た場合、以降も全部同じ数字で埋まることが確定する(ex. 2, 3 のあとは 3, 3, 3, ... しかありえない)。これを踏まえると以下のDPができる。

dp[i][最後が1かどうか]: i番目まで見て、最後の要素が1もしくは2以上のときの数列の総数

数列をAと表すことにすると、このDPの遷移は以下のようになる。

1. A[i]が1のとき: 次に何が来てもよい（その決定によって連鎖的にi+2以降の値も決まってしまう、ということがない）。
2. A[i]が2〜Nで、次が1のとき: 1がA[i]個連続して埋まる。
3. A[i]が2〜Nで、次が2〜Nのとき: 以降無限に同じ数字が繰り返される。

1, 3の遷移は比較的単純なDPである。2のケースは若干面倒だが要は i -> i+2, i+3, i+4, ..., i+N にそれぞれ同じ値を配ればいいので累積和とかでなんとかなる。

感想

自力でできたので嬉しかった。上の文章は細かい数字のやりくりとか端折ってるんで公式解説とか見たほうがいいと思います。

コード (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 long MOD = 10^^9 + 7;

void main() {
    auto N = readln.chomp.to!int;

    auto dp = new long[][](N+1, 2);
    dp[0][1] = 1;

    auto imos = new long[](3*N);
    long INV = powmod(N-1, MOD-2, MOD);
    long ans = 0;

    foreach (i; 0..N) {
        (dp[i+1][0] += dp[i][1] * (N - 1) % MOD) %= MOD; // 1のあとに2〜N
        (dp[i+1][1] += dp[i][1]) %= MOD; // 1のあとに1
        (dp[N][0] += dp[i][0] * (N - 1) % MOD) %= MOD; // 2〜Nのあとに2〜N (無限ループ)

        // 2〜Nのあとに1
        (imos[i+2] += dp[i][0] * INV % MOD) %= MOD;
        (imos[i+N+1] -= dp[i][0] * INV % MOD) %= MOD;

        (imos[i+1] += imos[i]) %= MOD;
        (dp[i+1][1] += imos[i+1]) %= MOD;
    }

    foreach (i; N..3*N-1) {
        (imos[i+1] += imos[i]) %= MOD;
        (ans += imos[i+1]) %= MOD;
    }

    ans = (ans + dp[N].sum % MOD + MOD) % MOD;
    ans.writeln;
}

long powmod(long a, long x, long m) {
    long ret = 1;
    while (x) {
        if (x % 2) ret = ret * a % m;
        a = a * a % m;
        x /= 2;
    }
    return ret;
}

CODE FESTIVAL 2018 qual A: D - 通勤

https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_d

問題概要

自分の家が座標0, オフィスが座標Dにあり、N個のガソリンスタンドの座標が数列Xで与えられる。車の燃料タンクの容量がFで距離1の移動に燃料を1消費する。はじめ車の燃料は満タンで、ガソリンスタンドについたときの燃料がT未満のとき、またそのときにかぎり必ず燃料を満タンまで補給することにする。ガソリンスタンドの部分集合を選び、含まれないものは潰すとき、家からオフィスまで燃料が0未満にならないように移動できるような選び方は何通りあるか求めよ。

0 < T <= F <= 10⁹

N <= 10⁵

解法

dp(i) = 最後に燃料を補給したガソリンスタンドがi番目のときの,　i番目までのガソリンスタンドの選び方の総数

上のDPの遷移を考える。i番目のガソリンスタンドで補給して燃料満タンの状態で出発したとき、以降のスタンドは以下の3種類に分類できる（3番は明らかに関係ないので考えなくてよい）。

1. iからの距離が (F - T) 以下にあるスタンド
2. iからの距離が (F - T) より大きく F 以下であるスタンド
3. iからの距離が F より大きいスタンド

1の範囲のスタンドを通過するときは燃料がT以上なので補給は発生しない。つまりこの範囲のスタンドはどっちにしろ影響がないため、潰しても潰さなくてもよい。よってこの範囲のスタンドの数をkとすると、2^kの選び方がある。

2の範囲のスタンドを通過するときは燃料がT未満になっているのでスタンドが潰れていない限り必ず補給が発生する。仮にこの範囲の中に j, j+1, j+2 の3つのスタンドがあったとすると、そのままであれば次に補給が発生するのは j である。逆にいえば i の次 j+1 に止まるためには j が潰れている必要がある。i の次 j+2 に止まりたいときも同様に j, j+1 が両方潰れていなければならない。よって結局3つのうち次どれに止まる場合でも、潰し方に自由度があるのは結局1の範囲に存在するガソリンスタンドだけである。

よって上のDPの遷移は、上の j, j+1, j+2 の例をとると dp[j], dp[j+1], dp[j+2] に一律 dp[i] * 2^k を足す、という処理に落ち着く。この計算方法はいろいろやり方があると思うが、自分はDPテーブル自体をBinary Indexed Treeで持って区間加算するという感じでやった。iからの距離が(F-T)〜Fにあるスタンドの範囲を求めるのは二分探索とかしゃくとり法とかでできる。

感想

なんか細かいところで詰まってやたら時間かかってしまった

コード (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 long MOD = 10^^9 + 7;

void main() {
    auto s = readln.split.map!(to!int);
    auto D = s[0].to!long;
    auto F = s[1].to!long;
    auto T = s[2].to!long;
    auto N = s[3];
    auto A = 0 ~ readln.split.map!(to!long).array;
    N += 1;

    auto P2 = new long[](N+1);
    P2[0] = 1;
    foreach (i; 0..N) P2[i+1] = P2[i] * 2 % MOD;

    auto bt = new BIT(N+1);
    bt.add(0, 1);
    bt.add(1, -1);
    long ans = 0;

    foreach (i; 0..N) {
        auto ub = A.assumeSorted.lowerBound(A[i] + F + 1).length.to!int;
        auto lb = A.assumeSorted.lowerBound(A[i] + F - T + 1).length.to!int;
        long num = bt.sum(0, i+1) * P2[max(0, lb - i - 1)] % MOD;
        bt.add(lb, num);
        bt.add(ub, -num);
        if (D - A[i] <= F) ans = (ans + num) % MOD;
    }

    ans = (ans % MOD + MOD) % MOD;
    ans.writeln;
}


class BIT{
    int n;
    long[] table;

    this(int x){
        n = x;
        table = new long[](x+1);
    }

    void add(int i, long x){
        i++;
        while (i <= n){
            (table[i] += x) %= MOD;
            i += i & -i;
        }
    }

    // [0, i]
    long sum(int i){
        i++;
        long ret = 0;
        while (i > 0){
            (ret += table[i]) %= MOD;
            i -= i & -i;
        }
        return ret;
    }

    // [l, r)
    long sum(int l, int r){
        if (l >= r) return 0;
        return (sum(r-1) - sum(l-1)) % MOD;
    }
}

CODE FESTIVAL 2018 qual A: C - 半分

https://beta.atcoder.jp/contests/code-festival-2018-quala/tasks/code_festival_2018_quala_c

問題概要

N要素の数列Aが与えられる。数列の要素をひとつ選び2で割る、という操作をちょうどK回行ったあと、残った数列としてありえるものが何通りあるか求めよ。

N <= 50

Ai <= 10¹⁸

K <= 10⁹

解法

DPをする。愚直には以下のようなDPとなる。

dp(i, j): i番目までの要素に対してj回操作した結果としてありえる数列の数

問題はKが大きいことで、このDPは遷移も含めるとO(NK²)とかになってしまってまず間に合わない。ここで「ひとつの要素を割り続けると割と早い段階で0になる」「0を割り続ければ状態を変えずに操作回数を空費できる」という2点に注目すると、このDPをもうちょっと効率的にやることができる。

まず Ai <= 10¹⁸ より、多くても60回割ればAiは0になる。よって上のDPの操作回数は1要素につき60回、最大で50要素×60=3000回までしか考える必要がない。遷移を考えるときもひとつの要素に対して高々60回まで見ればよい。また操作後の要素にひとつでも0があればそこを割り続けて状態を変えずに余ったKを消費できるので、「操作の結果要素が0になったか」もDPの状態に含めることにする。するとDPは状態数が最大ケースでも 50 * 3000 * 2, 遷移が 60 通りで だいたい 2 * 10⁷ くらいの計算量になるので間に合う。最終的にはこのDP表のうち操作回数がKに等しいか、あるいは0フラグが立っているものを足し合わせれば答えが出る。

感想

本番結構適当に辻褄を合わせて通してしまった

コード (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 long MOD = 10^^9 + 7;

void main() {
    auto s = readln.split;
    auto N = s[0].to!int;
    auto K = s[1].to!long;
    auto A = readln.split.map!(to!long).array;
    auto cnt = new long[](N);
    long ans = 0;

    foreach (i; 0..N) {
        for (long a = A[i]; a > 0; a /= 2) {
            cnt[i]++;
        }
    }

    auto dp = new long[][][](N+1, 65*N, 2);
    //foreach (i; 0..N+1) foreach (j; 0..50*N) foreach (k; 0..2) dp[i][j][k] = -1;
    foreach (i; 0..N) if (A[i] == 0) dp[0][0][1] = 1;
    if (dp[0][0][1] == 0) dp[0][0][0] = 1;

    foreach (i; 0..N) {
        foreach (j; 0..65*N) {
            foreach (k; 0..2) {
                if (dp[i][j][k] == 0) continue;
                foreach (using; 0..cnt[i]+1) {
                    if (j + using > K) continue;
                    (dp[i+1][j+using][k||(using==cnt[i])] += dp[i][j][k]) %= MOD;
                }
            }
        }
    }

    //dp.each!writeln;
    foreach (j; 0..min(65*N, K+1)) (ans += dp[N][j][1]) %= MOD;
    if (K < 65*N) (ans += dp[N][K][0]) %= MOD;


    ans.writeln;
}

仕事やめ彦・せん蔵

今まで新卒で入った会社でプログラミングとは全然関係なく事務職をやってたんですが、そこを辞めて競プロア〜が多いと噂の会社でプログラマーをすることになりました。転職活動ではかなり競プロの経験を生かせたと思う（というか生かせそうなところに応募した）し、何より競プロやってなかったらこういう道があるんだってことに気づくことさえなかったと思うので、競プロに関わっている皆さんには本当に感謝しています。思えば暇つぶしで始めたことがこういう形で人生に影響を及ぼすとは当初全く想像していませんでした。年齢的なこともあって本当にここで職変えて大丈夫なんかという気持ちは正直あるんですが、だからこそこっちを選んで良かったとなるようにがんばりたいな〜と思います。次働き出すまではかなり間があるのでしばらくは精進とか業プロの勉強とか英語の勉強とかをやっていけたらなーという感じです。そんな感じで今後ともよろしくお願いします。

天下一プログラマーコンテスト2013 決勝: A - 天下一有無

https://beta.atcoder.jp/contests/tenka1-2013-final/tasks/tenka1_2013_final_a

問題概要

N×Mのグリッドの各マスに対して「着色されたマスが縦・横・斜めで隣り合わない」かつ「最低1マスは着色されている」という条件のもと色を塗るとき、何通りの塗り方があり得るか求めよ。

N, M <= 15

解法

上の行から順に各マスを塗る・塗らないのbitDPをしていく。遷移を単純にやると2¹⁵×2¹⁵かかってしまうが、そもそも2¹⁵の中には正しくない塗り方（塗りが隣り合う）がかなりの数含まれているため、そういうのを飛ばす枝刈りを入れると十分間に合う（M=15のとき正しい塗り方は1597通りしかない）。

感想

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 long MOD = 10^^9 + 7;

bool valid(int mask) {
    return !((mask & (mask << 1)) || (mask & (mask >> 1)));
}

bool valid2(int mask1, int mask2) {
    return !((mask1 & (mask2 << 1)) || (mask1 & mask2) || (mask1 & (mask2 >> 1)));
}

void main() {
    auto s = readln.split.map!(to!int);
    auto H = s[0];
    auto W = s[1];
    auto masks = iota(1<<W).filter!(a => valid(a)).array;

    auto dp = new long[][](H+1, 1<<W);
    dp[0][0] = 1;

    foreach (r; 0..H) {
        foreach (mask1; masks) {
            if (dp[r][mask1] == 0) continue;
            foreach (mask2; masks) {
                if (!valid2(mask1, mask2)) continue;
                dp[r+1][mask2] += dp[r][mask1];
                dp[r+1][mask2] %= MOD;
            }
        }
    }

    auto ans = (dp[H].sum - 1) % MOD;
    ans.writeln;
}

天下一プログラマーコンテスト2016予選B: D - 天下一数列にクエリを投げます

https://beta.atcoder.jp/contests/tenka1-2016-qualb/tasks/tenka1_2016_qualB_d

問題概要

N要素の数列a1, a2, .., aNに対してA個の加算クエリとB個の調査クエリが与えられるので順次処理せよ。

• 加算クエリ: 数列の区間[L, R]にXを加算する
• 調査クエリ: S回目の加算クエリを実行する直前からT回目の加算クエリを実行した直後までで、数列のK番目がとる値の最小値

N, A, B <= 10⁵

解法

「ある時点での数列の各要素の値」を追いかけたくなるが、そうではなく「数列のある要素の全ての時点での値」に注目するとうまくいく。イメージとしては以下のような処理の流れになる。まず（加算クエリの数）要素ある数列を用意し、これを各加算クエリ実行時点でのa1の値とみなす。次に左端が1であるような加算クエリを持ってくる。このクエリの順番をt, 足される値をxとすると、t回目のクエリ以後はa1の値はx足されていることになるわけなので、用意した数列のt番目以降の要素に一律xを加算する。次にa1が対象の調査クエリを持ってきて、区間[S-1, T]をチェックすればこの調査クエリの答えが求まる。ここまで処理が終わったら今度はこの数列をa2のものと見なすことにする。このとき区間[L, R]のRがa1であるような加算クエリの分は消す必要があるので、先ほどの加算の逆操作（t番目以降に一律-xを足す）を行う。以上を繰り返していけばすべてのクエリを処理していくことができる。そしてここで必要となっている区間加算、区間最小取得といった処理は遅延評価セグメントツリーを用いれば効率的に行うことができ、時間内に答えを出すことができる。

感想

言われてみれば…というタイプの問題だけど自分で思いつくのは厳しかった

コード (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;

alias Tuple!(int, "t", int, "l", int, "r", int, "x") Query;

void main() {
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!long).array;
    auto q1 = readln.chomp.to!int;
    auto Q1 = q1.iota.map!(i => (i+1) ~ readln.split.map!(to!int).array).array;
    auto q2 = readln.chomp.to!int;
    auto Q2 = q2.iota.map!(i => (i+1) ~ readln.split.map!(to!int).array).array;
    auto st = new LazySegmentTree!long(q1+10);
    auto ans = new long[](q2);

    auto add_queue1 = new BinaryHeap!(Array!Query, "a.l > b.l");
    auto add_queue2 = new BinaryHeap!(Array!Query, "a.r > b.r");
    foreach (q; Q1) add_queue1.insert(Query(q[0], q[1], q[2], q[3]));
    Q2.sort!"a[3] < b[3]";
    int p = 0;

    foreach (i; 1..N+1) {
        while (!add_queue2.empty && add_queue2.front.r < i) {
            auto q = add_queue2.front;
            add_queue2.removeFront;
            st.add(q.t, q1+1, -q.x);
        }
        while (!add_queue1.empty && add_queue1.front.l == i) {
            auto q = add_queue1.front;
            add_queue1.removeFront;
            st.add(q.t, q1+1, q.x);
            add_queue2.insert(q);
        }
        while (p < q2 && Q2[p][3] == i) {
            ans[Q2[p][0]-1] = st.getVal(Q2[p][1]-1, Q2[p][2]) + A[i-1];
            ++p;
        }
    }

    ans.each!writeln;
}

class LazySegmentTree(T) {
    T[] table;
    T[] lazy_;
    int size;

    this(int n) {
        assert(bsr(n) < 29);
        size = 1 << (bsr(n) + 2);
        table = new T[](size);
        lazy_ = new T[](size);
        fill(table, 0);
        fill(lazy_, 0);
    }

    void eval(int i, int l, int r) {
        if (lazy_[i] == 0) return;

        table[i] += lazy_[i];
        if (l != r) {
            lazy_[i*2+1] += lazy_[i];
            lazy_[i*2+2] += lazy_[i];
        }

        lazy_[i] = 0;
    }

    void add(int a, int b, T num) {
        add(a, b, num, 0, 0, size/2-1);
    }

    void add(int a, int b, T num, int i, int l, int r) {
        eval(i, l, r);

        if (a > r || b < l) return;
        if (a <= l && r <= b) {
            lazy_[i] += num;
            eval(i, l, r);
        } else {
            add(a, b, num, i*2+1, l, (l+r)/2);
            add(a, b, num, i*2+2, (l+r)/2+1, r);
            table[i] = min(table[i*2+1], table[i*2+2]);
        }
    }

    T getVal(int a, int b) {
        return getVal(a, b, 0, 0, size/2-1);
    }

    T getVal(int a, int b, int i, int l, int r) {
        eval(i, l, r);

        if (a > r || b < l) return 1L << 59;
        if (a <= l && r <= b) return table[i];
        return
            min(getVal(a, b, i*2+1, l, (l+r)/2),
                getVal(a, b, i*2+2, (l+r)/2+1, r));
    }
}