C++
#include <algorithm>
#include <cassert>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
int main() {
int N, M;
cin >> N >> M;
vector<int> P(N);
for (auto& x : P) cin >> x;
vector<pair<int, int>> AB(M);
for (auto& [a, b] : AB) cin >> a >> b;
// 簡単のため 0-indexed の 半開区間にする
for (auto& [a, _] : AB) --a;
// 区間全体を入れる
AB.emplace_back(0, N);
// ソート
sort(begin(AB), end(AB), [](auto l, auto r) {
return l.first == r.first ? l.second > r.second : l.first < r.first;
});
assert(AB[0] == make_pair(0, N));
// 包含関係に対応するグラフを構築
vector<vector<int>> g(M + 1);
vector<int> par(M + 1, -1);
for (int i = 1; i <= M; i++) {
auto [a, b] = AB[i];
// 親のノードは？
int p = i - 1;
// p に完全に含まれるまで親にさかのぼる
// さかのぼる回数は償却 O(1) (cf : オイラーツアー)
while (true) {
auto [pa, pb] = AB[p];
// pa a b pb の順 (b = pb を許容) -> 包含
if (b <= pb) break;
// 並び順は pa pb a b なので親にさかのぼる必要あり
p = par[p];
}
// i を p の子とする
g[p].push_back(i);
par[i] = p;
}
// 区間の先頭要素の最小値を記録する配列
vector<int> mn(M + 1, 1 << 30);
// reverse するかを表す配列
// (子のmin, 子のid(ブロック単体の場合-1) )
vector<vector<pair<int, int>>> chd(M + 1);
// DFSで順番を決定する
auto dfs = [&](auto rc, int c) -> void {
auto [a, b] = AB[c];
int cid = 0;
for (int i = a; i < b;) {
int upd = 0;
if (cid < (int)g[c].size()) {
int d = g[c][cid];
auto [ca, cb] = AB[d];
if (i == ca) {
// dを使う。再帰的に最小値を計算
rc(rc, d);
// chd[c] に pushして更新作業
chd[c].emplace_back(mn[d], d);
cid++;
i = cb;
upd = 1;
}
}
if (!upd) {
chd[c].emplace_back(P[i], -1);
i++;
}
}
if (chd[c].back().first < chd[c][0].first) {
reverse(begin(chd[c]), end(chd[c]));
}
mn[c] = chd[c][0].first;
return;
};
dfs(dfs, 0);
vector<int> ans;
// DFS で解を構成
auto dfs2 = [&](auto rc, int c) -> void {
for (auto& [val, id] : chd[c]) {
if (id == -1) {
ans.push_back(val);
} else {
rc(rc, id);
}
}
};
dfs2(dfs2, 0);
assert((int)ans.size() == N);
for (int i = 0; i < N; i++) cout << ans[i] << " \n"[i == N - 1];
}
Java
import java.util.*;
public class Main {
static int N;
static int M;
static int[] P;
static int[][] AB;
static List<List<Integer>> g;
static List<List<Integer[]>> chd;
static List<String> ans;
static int[] mn;
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
N = Integer.parseInt(sc.next());
M = Integer.parseInt(sc.next());
P = new int[N];
for (int i = 0; i < N; i++) {
P[i] = Integer.parseInt(sc.next());
}
AB = new int[M+1][2];
for (int i = 0; i < M; i++) {
// 簡単のため 0-indexed の 半開区間にする
AB[i][0] = Integer.parseInt(sc.next()) - 1;
AB[i][1] = Integer.parseInt(sc.next());
}
// 区間全体を入れる
AB[M] = new int[] {0, N};
// ソート
Arrays.sort(AB, (x, y) -> x[0] == y[0] ? y[1] - x[1] : x[0] - y[0]);
// 包含関係に対応するグラフを構築
g = new ArrayList<List<Integer>>();
int[] par = new int[M+1];
// 区間の先頭要素の最小値を記録する配列
mn = new int[M+1];
int init = 1 << 30;
// reverse するかを表す配列
// (子のmin, 子のid(ブロック単体の場合-1) )
chd = new ArrayList<List<Integer[]>>();
for (int i = 0; i < M+1; i++) {
g.add(new ArrayList<Integer>());
par[i] = -1;
mn[i] = init;
chd.add(new ArrayList<Integer[]>());
}
for (int i = 1; i <= M; i++) {
int a = AB[i][0];
int b = AB[i][1];
// 親のノードは？
int p = i - 1;
// p に完全に含まれるまで親にさかのぼる
// さかのぼる回数は償却 O(1) (cf : オイラーツアー)
while (true) {
int pa = AB[p][0];
int pb = AB[p][1];
// pa a b pb の順 (b = pb を許容) -> 包含
if (b <= pb) {
break;
}
// 並び順は pa pb a b なので親にさかのぼる必要あり
p = par[p];
}
// i を p の子とする
g.get(p).add(i);
par[i] = p;
}
// DFSで順番を決定する
dfs(0);
ans = new ArrayList<String>();
// DFS で解を構成
dfs2(0);
System.out.println(String.join(" ", ans));
}
static void dfs(int c) {
int a = AB[c][0];
int b = AB[c][1];
int cid = 0;
for (int i = a; i < b;) {
boolean upd = false;
if (cid < g.get(c).size()) {
int d = g.get(c).get(cid);
int ca = AB[d][0];
int cb = AB[d][1];
if (i == ca) {
// dを使う。再帰的に最小値を計算
dfs(d);
// chd[c] に addして更新作業
chd.get(c).add(new Integer[] {mn[d], d});
cid++;
i = cb;
upd = true;
}
}
if (!upd) {
chd.get(c).add(new Integer[] {P[i], -1});
i++;
}
}
if (chd.get(c).get(chd.get(c).size()-1)[0] < chd.get(c).get(0)[0]) {
Collections.reverse(chd.get(c));
}
mn[c] = chd.get(c).get(0)[0];
return;
}
static void dfs2(int c) {
for (Integer[] ele : chd.get(c)) {
int val = ele[0];
int id = ele[1];
if (id == -1) {
ans.add(String.valueOf(val));
} else {
dfs2(id);
}
}
};
}
Python
import sys
sys.setrecursionlimit(10**9)
N, M = list(map(int, input().split()))
P = list(map(int, input().split()))
AB = [list(map(int, input().split())) for _ in range(M)]
for i in range(M):
AB[i][0] -= 1
AB.append([0,N])
AB.sort(key = lambda x: (x[0], -x[1]))
g = [[] for _ in range(M+1)]
par = [-1] * (M+1)
for i in range(1, M+1):
a, b = AB[i]
p = i - 1
while True:
pa, pb = AB[p]
if b <= pb:
break
p = par[p]
g[p].append(i)
par[i] = p
mn = [1<<30] * (M+1)
chd = [[] for _ in range((M+1))]
def dfs(c):
a, b = AB[c]
cid = 0
i = a
while i < b:
upd = 0
if cid < len(g[c]):
d = g[c][cid]
ca, cb = AB[d]
if i == ca:
dfs(d)
chd[c].append([mn[d], d])
cid += 1
i = cb
upd = 1
if not upd:
chd[c].append([P[i], -1])
i += 1
if chd[c][-1][0] < chd[c][0][0]:
chd[c].reverse()
mn[c] = chd[c][0][0]
return
dfs(0)
ans = []
def dfs2(c):
for val, id in chd[c]:
if id == -1:
ans.append(val)
else:
dfs2(id)
dfs2(0)
print(*ans)
