Arpa's Trick

問題を解いていてこれを使う機会があったのですが、日本語での解説がほとんどなかったので、書いていこうと思います。

Post Image は近代五種です。内容とは全く関係ないです。

Repovive Starter Round 2 - F. のネタバレを含みます。

導入

次の問題を考えます。

長さ $N$ の配列 ${a_{i}}_{1 \leq i \leq N}$ があり、最初すべての $i$ に対し $a_{i} = 0$ です。
以下のようなクエリが $Q$ 回与えられるので、すべて処理したあとの $a$ を求めてください。

$i$ 回目のクエリでは、 $l_{i}, r_{i}, v_{i}$ が与えられる。 $\forall p \in [l_{i}, r_{i}]$ について、 $a_{p} := v_{i}$ とする。

この問題を、 $lo g$ がつかない計算量で解いてください。

安直にやるなら Lazy Segment Tree を用いると一発ですが、log がついてしまいます。およそ線形時間で求まるようにしたいですね。

Disjoint Union Set であそぼ

これを Disjoint Union Set でやりましょう、という少し不思議な提案をしてみます。

準備 : クエリ先読み

問題を見るに Offline なので、クエリを先読みしてよいです。そうすると、クエリを全部読んで逆から処理していけば、すでに塗られているところを無視することで線形時間で解けそうです。実際に既知の要素を完全に無視できるのならば、すべての配列の要素はそれぞれ 1 回タッチするだけですから高速です。

問題はこれをどう無視するかということですね。

やってみよう

12 マスあって、まず 2~7 番目のマスを青で塗り、次に 4~6 番目のマスを赤で塗るという場合を考えてみましょう。先ほどのように、クエリを逆順に見るので、まず 4~6 番目のマスを赤で塗り、2~7 番目のマスを青で塗るという順番で処理していきます。

$next [i] := i$ 以降にあるまだ塗っていないマスのうち、最も左にあるもの

としてみましょう。最初はどのマスも塗っていないので、 $next [i] = i$ です。

$i$ マス目を塗ったとき、一個右のマスはまだ塗っていないマスなので $next [i] = i + 1$ という風に変化させます。

でもこの数字、塗ってるマス指してるところあるじゃん！これでちゃんと青塗れるの？

というわけでこちらをご用意いたしました。

int find(int p) {
    if (next[p] == p) return p;
    else return next[p] = find(next[p]);
}

これで、 $i$ マス目を塗ったときに、 $next [i] := find (i + 1)$ と更新してあげます。
たとえば、最初は 4 マス目を塗ったので、 $next [4] := find (4 + 1) = 5$ です。

では、次に 2~7 マス目を青で塗ってみましょう。

$next [3]$ を更新するときどうなるかというと、

$find (4)$ を見る。 $next [4] = 5 \neq = 4$ になっている。
$find (5)$ を見る。 $next [5] = 6 \neq = 5$ になっている。
$find (6)$ を見る。 $next [6] = 7 \neq = 6$ になっている。
$find (7)$ を見る。 $next [7] = 7$ になっている。 $7$ を返して $find (7)$ 終了。
$next [6] = find (7) = 7$ に更新して、 $7$ を返して $find (6)$ 終了。
$next [5] = find (6) = 7$ に更新して、 $7$ を返して $find (5)$ 終了。
$next [4] = find (5) = 7$ に更新して、 $7$ を返して $find (4)$ 終了。
$next [3] = find (4) = 7$ に更新する。

という風になります。すると、最初に塗った 4~6 マス目に行くマスがなくなるので、これ以上タッチしなくなります。結果として、3 マス目は次に 7 マス目を指すようになります。

あとは、残った 7 マス目を青く塗って、 $next [7] = 8$ に更新します。

以上のように、DSU と同様に辿ってマージをすることができるというわけです。

ただ、マージの仕方が重要な問題です。DSU では、マージの計算量を落とすために、Path Compression と Union by Size (or Rank) を行うのがよくある手法ですが、今回のケースでは Union by Size は行うことができません。というのも、自身より右にある頂点に向かって結合するという向きが重要な役割を果たすので、単にサイズなどを基準にして swap などを行うことはできないのです。

Path Compression しかできないと、マージには $O (lo g N)$ かかってしまうのでは？と思われるかもしれませんが、大丈夫です。

Important Fact:
Union Find を構成する木が Line Graph である場合、union by size/rank の処理を行わず、単に Path compression を行うだけでも、結合は $O (α (N))$ で実行できる。

証明は省略しますが、Line Graph のもつ特殊な性質を用いることで示すことができます。よって、 $O (N + Q α (N))$ で解くことができました。

Arpa's Trick

長さ $N$ の配列 ${a_{i}}_{0 \leq i < N}$ に対して、

\forall i \in [0, n - 1], b_{i} := min {j ∣ j > i, a [j] < a [i]}

を $O (N)$ で求めてください。 ${j ∣ j > i, a [j] < a [i]}$ が empty である場合は $b_{i} := N$ としてください。

例えば、 $a = {5, 8, 2, 1, 6, 3, 9, 7}$ に対し、 $b = {2, 2, 3, 8, 5, 8, 7, 8}$ です。

$O (N^{2})$ なら超簡単ですね。

for (int i = n - 1; i >= 0; i--) {
    b[i] = i + 1;
    while (b[i] != n && a[i] <= a[b[i]]) {
        b[i]++;
    }
}

1 行変えてみました！

for (int i = n - 1; i >= 0; i--) {
    b[i] = i + 1;
    while (b[i] != n && a[i] <= a[b[i]]) {
       b[i] = b[b[i]];
    }
}

なんと！　 $O (N)$ になるんですね～　何？

b[i]++ を b[i] = b[b[i]] に変えただけですが、ここがいわゆる Path Compression に相当する操作になります。

つまり、ここでやっていることは、本質的には先ほどの色塗りの問題と変わりません。まず $i \to i + 1$ という辺を張って、それに沿ってマージしていくというだけです。こちらも形が Line Graph なので、Path Compression のみを行ってもマージは $O (α (N))$ です。

このように DSU 的な操作を行うことで、線形時間でこの問題を解くテクニックは、考えた人の Handle Name から Arpa's Trick と呼ばれています。

問題

ここからネタバレです。

Repovive Starter Round 2 - F. Pair Increment Ranges

こちらの問題を解いていきたいと思います。

とりあえず問題をまずは日本語に書き直していきます。

2 本の配列 $a_{1}, a_{2}, \dots, a_{n}$ と $b_{1}, b_{2}, \dots, b_{n}$ があります。
ある閉区間 $[l, r]$ が beautiful であるとは、配列 $a$ に対し、ある index $l < i \leq r$ を選んで、 $a_{i - 1}$ から $1$ 引いて $a_{i}$ に $1$ 足すという操作を $0$ 回以上行うことで、 $\forall i \in [l, r], a_{i} = b_{i}$ を満たすことを言います。
beautiful な閉区間の個数を求めてください。 $t$ 個のテストケースが与えられるので、それぞれに対して答えてください。

Constraint :

$1 \leq t \leq 1 0^{4}$
$1 \leq n \leq 2 \cdot 1 0^{5}$
$0 \leq a_{i}, b_{i} \leq 1 0^{9}$
$\sum n \leq 2 \cdot 1 0^{5}$

$[l, r]$ が beautiful である条件は

$\sum_{i = l}^{r} a_{i} = \sum_{i = l}^{r} b_{i}$
$\forall p \in [l, r], \sum_{i = l}^{p} a_{i} \geq \sum_{i = l}^{p} b_{i}$

の 2 つが成立することです。 $d_{x} := \sum_{i = 0}^{x} a_{i} - \sum_{i = 0}^{x} b_{i}$ とすると、以上の条件は

$d_{r} = d_{l - 1}$
$\forall p \in [l, r], d_{p} \geq d_{l - 1}$

に書き換えられます。

$l - 1$ を固定して考えます。日本語で説明すれば、自分より右にいて、自分と同じ値で、かつ自分より小さい値が間にないものがカウント対象の要素です。と考えたら、とりあえず末尾から考えていけばよいということが分かります。

$dp [i]$ を $i$ 番目が左端であるような beautiful な閉区間の個数とします。求める答えは $\sum dp [i]$ です。上の条件を満たすような最小の $r > i$ があったとしたら、 $dp [i] = dp [r] + 1$ と更新すればよいです。なければ、ないので $0$ です。じゃあその $r$ をどうやって探すのかというのが問題です。

$x = y ⟺ x \leq y \land x \geq y$ というのは皆さんもおなじみかと思いますが、これを言い換えると、 $x = y ⟺ x \leq y \land \neg (x < y)$ となります。ということは、次の配列を考えてみるといいのかもしれません。

$nex t_{<} [i] = min {j ∣ j > i, d_{j} < d_{i}}$
$nex t_{\leq} [i] = min {j ∣ j > i, d_{j} \leq d_{i}}$

どちらも、集合が empty な場合は $n + 1$ を代わりに入れます。

$next_{<} [i] = next_{\leq} [i]$ の場合、その場所を $p$ とすると $d_{p} \leq d_{i} \land d_{p} < d_{i}$ であるので $d_{p} \neq = d_{i}$ です (1)。逆に、 $next_{<} [i] \neq = next_{\leq} [i]$ の場合、 $p := next_{\leq} [i]$ とすると $d_{p} \leq d_{i} \land \neg (d_{p} < d_{i})$ ですので、 $d_{p} = d_{i}$ であり、間に自身より小さい値は存在しません (2)。よって先述の $r$ が求められたというわけです。

では、 $next_{<} [i], next_{\leq} [i]$ をどう求めるかという話ですが、この集合の中身は Arpa's Trick の説明で書いたものとほぼ同じです。そのため、条件に注意しながら Arpa's Trick を使えば高速に求めることができます。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve();
int main() {
    int t; cin >> t;
    while (t--) solve();
}
void solve() {
    int n; cin >> n;
    vector<ll> a(n), b(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        cin >> b[i];
    }
    vector<ll> d(n + 1, 0);
    for (int i = 0; i < n; i++) {
        d[i + 1] = d[i] + (a[i] - b[i]);
    }
    const ll inf = numeric_limits<ll>::max() / 4;
    d.push_back(-inf);
    vector<ll> dp(n + 2, 0);
    vector<ll> next0(n + 1, 0), next1(n + 1, 0);
    ll ans = 0;
    for (int i = n; i >= 0; i--) {
        next0[i] = i + 1;
        while (next0[i] != n + 1 && d[i] < d[next0[i]]) {
            next0[i] = next0[next0[i]];
        }
        next1[i] = i + 1;
        while (next1[i] != n + 1 && d[i] <= d[next1[i]]) {
            next1[i] = next1[next1[i]];
        }
        if (next0[i] == next1[i]) dp[i] = 0;
        else dp[i] = dp[next0[i]] + 1;
        ans += dp[i];
    }
    cout << ans << endl;
}

おわり

明日のブログリレーは @phi_isct さんです。

参考にした資料

https://cp-algorithms.com/data_structures/disjoint_set_union.html
https://codeforces.com/blog/entry/143633
https://repovive.com/contests/10/problems/F
Harold N.G., Robert E.T., (1983) A linear-time algorithm for a special case of disjoint set union, https://doi.org/10.1016/0022-0000(85)90014-5

Arpa's Trick

導入

Disjoint Union Set であそぼ

準備 : クエリ先読み

やってみよう

Arpa's Trick

問題

Repovive Starter Round 2 - F. Pair Increment Ranges

おわり

参考にした資料

この記事をシェア

関連する記事