結果
| 問題 | No.875 Range Mindex Query |
| コンテスト | |
| ユーザー |
 joji
|
| 提出日時 | 2026-01-21 12:47:59 |
| 言語 | C++23 (gcc 15.2.0 + boost 1.89.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,739 bytes |
| 記録 | |
| コンパイル時間 | 4,214 ms |
| コンパイル使用メモリ | 357,368 KB |
| 実行使用メモリ | 7,980 KB |
| 最終ジャッジ日時 | 2026-01-21 12:48:05 |
| 合計ジャッジ時間 | 6,195 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 2 WA * 16 |
ソースコード
#line 1 "875.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/875"
#line 2 "ds/segment_tree.hpp"
#include <algorithm>
#include <cassert>
#include <vector>
template <typename Monoid> struct SegTree {
using T = typename Monoid::value_type;
int n;
std::vector<T> t;
SegTree() : n(0) {}
SegTree(int n) : n(n) { t.resize(4 * n, Monoid::e()); }
SegTree(const std::vector<T> &A) : n((int)A.size()) {
t.resize(4 * n, Monoid::e());
build(A, 1, 0, n - 1);
}
void build(const std::vector<T> &A, int v, int tl, int tr) {
if (tl == tr) {
t[v] = A[tl];
} else {
int tm = (tl + tr) / 2;
build(A, v * 2, tl, tm);
build(A, v * 2 + 1, tm + 1, tr);
t[v] = Monoid::op(t[v * 2], t[v * 2 + 1]);
}
}
void update(int v, int tl, int tr, int pos, const T &new_val) {
if (tl == tr) {
t[v] = new_val;
} else {
int tm = (tl + tr) / 2;
if (pos <= tm) {
update(v * 2, tl, tm, pos, new_val);
} else {
update(v * 2, tm + 1, tr, pos, new_val);
}
t[v] = Monoid::op(t[v * 2], t[v * 2 + 1]);
}
}
void update(int pos, const T &new_val) { update(1, 0, n - 1, pos, new_val); }
T query(int v, int tl, int tr, int l, int r) const {
if (l > r) {
return Monoid::e();
}
if (l == tl && r == tr) {
return t[v];
}
int tm = (tl + tr) / 2;
return Monoid::op(query(v * 2, tl, tm, l, std::min(r, tm)),
query(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r));
}
T query(int l, int r) const { return query(1, 0, n - 1, l, r); }
T get(int pos) const { return query(pos, pos); }
template <class Pred> int max_right(int l, Pred pred) const {
assert(0 <= l && l <= n);
assert(pred(Monoid::e()));
T acc = Monoid::e();
return max_right_dfs(1, 0, n - 1, l, pred, acc);
}
template <class Pred> int max_right_dfs(int v, int tl, int tr, int l, Pred pred, T &acc) const {
if (tr < l) return l;
if (tl >= l) {
T nxt = Monoid::op(acc, t[v]);
if (pred(nxt)) {
acc = nxt;
return tr + 1;
}
if (tl == tr) return tl;
}
int tm = (tl + tr) / 2;
int res = max_right_dfs(v * 2, tl, tm, l, pred, acc);
if (res <= tm) return res;
return max_right_dfs(v * 2 + 1, tm + 1, tr, l, pred, acc);
}
template <class Pred> int min_left(int r, Pred pred) const {
assert(0 <= r && r <= n);
assert(pred(Monoid::e()));
T acc = Monoid::e();
int res = min_left_dfs(1, 0, n - 1, r, pred, acc);
return res < 0 ? 0 : res;
}
template <class Pred> int min_left_dfs(int v, int tl, int tr, int r, Pred pred, T &acc) const {
if (tl >= r) return r;
if (tr < r) {
T nxt = Monoid::op(t[v], acc);
if (pred(nxt)) {
acc = nxt;
return tl - 1;
}
if (tl == tr) return tl + 1;
}
int tm = (tl + tr) / 2;
int res = min_left_dfs(v * 2 + 1, tm + 1, tr, r, pred, acc);
if (res >= tm + 1) return res;
return min_left_dfs(v * 2, tl, tm, r, pred, acc);
}
template <class Pred> int find_first(int l, int r, Pred check) const {
assert(0 <= l && l <= r && r < n);
return find_first_dfs(1, 0, n - 1, l, r, check);
}
template <class Pred> int find_first_dfs(int v, int tl, int tr, int l, int r, Pred check) const {
if (l > r || !check(t[v])) return -1;
if (tl == tr) return tl;
int tm = (tl + tr) / 2;
int res = find_first_dfs(v * 2, tl, tm, l, std::min(r, tm), check);
if (res != -1) return res;
return find_first_dfs(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r, check);
}
template <class Pred> int find_last(int l, int r, Pred check) const {
assert(0 <= l && l <= r && r < n);
return find_last_dfs(1, 0, n - 1, l, r, check);
}
template <class Pred> int find_last_dfs(int v, int tl, int tr, int l, int r, Pred check) const {
if (l > r || !check(t[v])) return -1;
if (tl == tr) return tl;
int tm = (tl + tr) / 2;
int res = find_last_dfs(v * 2 + 1, tm + 1, tr, std::max(l, tm + 1), r, check);
if (res != -1) return res;
return find_last_dfs(v * 2, tl, tm, l, std::min(r, tm), check);
}
};
#line 3 "875.test.cpp"
#include <bits/stdc++.h>
using namespace std;
void solve() {
int N, Q;
cin >> N >> Q;
vector<int> A(N);
for (auto &x : A) cin >> x;
struct Monoid {
using value_type = pair<int, int>;
static value_type e() { return {1 << 30, -1}; }
static value_type op(const value_type &a, const value_type &b) { return min(a, b); }
};
vector<pair<int, int>> data(N);
for (int i = 0; i < N; i++) {
data[i] = {A[i], i + 1};
}
SegTree<Monoid> seg(data);
while (Q--) {
int t, l, r;
cin >> t >> l >> r;
l--, r--;
if (t == 1) {
int pos1 = seg.get(l).first, pos2 = seg.get(r).first;
seg.update(l, {pos2, l + 1}), seg.update(r, {pos1, r + 1});
} else {
auto mn = seg.query(l, r);
cout << mn.second << '\n';
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t = 1;
// cin >> t;
while (t--) solve();
return 0;
}