LR Minimum Spanning Tree さらに簡素で高速な解法

クラスカル法を行うことを想像します。（実際に実行することは計算量の問題で不可能です）
ただしここでは、辺のコストが同じであれば、タイブレークで頂点番号の差が小さい順、それも同じなら頂点番号が小さい順に採用するとします。

このとき、以下の $2$ 条件のいずれかに該当する辺は、必ず採用されます。

1. ある整数kを境に「未満」と「以上」で頂点をグループ分けしたときの、「未満」側のL最小頂点と「以上」側のR最小頂点を結ぶ辺

ただし、同じ値を持つ頂点が複数あった場合には、番号が最も $k$ に近いもの同士を結ぶ辺を指します。

クラスカル法において、その境界をまたぐ辺として初めて登場する辺なので、既に連結であることは絶対にありません。
よって、必ず採用されます。

2. ある頂点から、他の任意の頂点に繋ぐ最小コストの辺

ただし、同コストの頂点が複数あった場合には、自身に最も番号が近いもの、それでも同じなら番号が小さい相手と結ぶ辺を指します。

クラスカル法において、その頂点が初めて登場する辺なので、既に連結であることは絶対にありません。
よって、必ず採用されます。

以上の $2$ 種類の辺を全て採用すれば、自動的に全体が連結になり、最小全域木が形成されます。
これは、以下の $3$ つが成り立つことから言えます（細かい証明は省略します）。

$1.$ で選ばれる辺から重複を除いたものは、必ず木を形成する
$2.$ で選ばれる辺で結ぶ相手は、必ず $1.$ でできる木に含まれる頂点である
どの頂点も $2.$ によって少なくとも $1$ つの辺が接続されている

$L$ の左からの累積最小値とその位置、 $R$ の右からの累積最小値とその位置、を事前準備します。
UnionFind木などで重複を避けながら辺を追加していくことにより、 $O(N\alpha(N))$ で解けます。

重複管理を工夫すれば、 $O(N)$ にもできます。

以下の実装では、 $1.$ でできる木に含まれない頂点についてのみ $2.$ の辺を追加します。
この場合は、同コストの辺のどちらを選んでもよいため、 $2.$ のタイブレークを省略しています。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74#include <bits/stdc++.h>
#include <atcoder/all>
using namespace std;
using namespace atcoder;

constexpr int INF = 1001001001;

/////////////////// メイン ///////////////////

int main() {

  //////////////////// 入力 ////////////////////

  int n;
  cin >> n;

  vector<int> l(n);
  for (int i = 0; i < n; i++) {
    cin >> l.at(i);
  }

  vector<int> r(n);
  for (int i = 0; i < n; i++) {
    cin >> r.at(i);
  }

  //////////////// 出力変数定義 ////////////////

  long long result = 0;

  //////////////////// 処理 ////////////////////

  vector<pair<int, int>> vec_l(n, {INF, -1});
  for (int i = 0; i < n - 1; i++) {
    if (vec_l.at(i).first >= l.at(i)) {
      vec_l.at(i + 1) = {l.at(i), i};
    } else {
      vec_l.at(i + 1) = vec_l.at(i);
    }
  }

  vector<pair<int, int>> vec_r(n, {INF, INF});
  for (int i = n - 1; i > 0; i--) {
    if (vec_r.at(i).first >= r.at(i)) {
      vec_r.at(i - 1) = {r.at(i), i};
    } else {
      vec_r.at(i - 1) = vec_r.at(i);
    }
  }

  dsu d(n);

  for (int i = 0; i < n - 1; i++) {
    if (d.same(vec_l.at(i + 1).second, vec_r.at(i).second)) continue;
    d.merge(vec_l.at(i + 1).second, vec_r.at(i).second);
    result += vec_l.at(i + 1).first + vec_r.at(i).first;
  }

  for (int i = 0; i < n; i++) {
    if (d.same(i, 0)) continue;
    int cost_l = r.at(i) + vec_l.at(i).first;
    int cost_r = l.at(i) + vec_r.at(i).first;
    result += min(cost_l, cost_r);
  }

  //////////////////// 出力 ////////////////////

  cout << result << endl;

  //////////////////// 終了 ////////////////////

  return 0;

}