#include #include #include #include using namespace std; struct Node { long long num = 0; long long idx = 0; }; long long n = 0, m = 0; vector arr(100001); vector tree(100001 * 4); Node init(int node, int l, int r) { if (l == r) { tree[node].num = arr[l]; tree[node].idx = l; return tree[node]; } int mid = (l + r) / 2; Node ret_l = init(node * 2, l, mid); Node ret_r = init(node * 2 + 1, mid + 1, r); if (ret_l.num < ret_r.num || (ret_l.num == ret_r.num && ret_l.idx < ret_r.idx)) tree[node] = ret_l; else tree[node] = ret_r; return tree[node]; } Node update(int node, int l, int r, const int& new_idx, const int& new_value) { if (l == r) { tree[node].num = new_value; return tree[node]; } int mid = (l + r) / 2; if (new_idx <= mid) update(node * 2, l, mid, new_idx, new_value); else update(node * 2 + 1, mid + 1, r, new_idx, new_value); Node left = tree[node * 2]; Node right = tree[node * 2 + 1]; if (left.num < right.num || (left.num == right.num && left.idx < right.idx)) tree[node] = left; else tree[node] = right; return tree[node]; } Node query(int node, int l, int r, const int& a, const int& b) { // 완전히 겹치지 않는 경우: 무효한 Node 반환 if (b < l || a > r) return Node{n + 1, n + 1}; // 매우 큰 값과 무효 인덱스 // 완전히 포함된 경우 if (a <= l && r <= b) return tree[node]; int mid = (l + r) / 2; Node left = query(node * 2, l, mid, a, b); Node right = query(node * 2 + 1, mid + 1, r, a, b); // 비교: 값이 작거나, 값이 같으면 인덱스가 작은 쪽 if (left.num < right.num || (left.num == right.num && left.idx < right.idx)) return left; else return right; } int main(void) { cin.tie(0)->sync_with_stdio(0); cin >> n; for(int i = 0; i < n; i++) { cin >> arr[i]; } init(1, 0, n - 1); cin >> m; for(int i = 0; i < m; i++) { int a = 0, b = 0, c = 0; cin >> a >> b >> c; if (a == 1) // update update(1, 0, n - 1, b - 1, c); else if (a == 2) // qurey cout << query(1, 0, n - 1, b - 1, c - 1).idx + 1 << "\n"; } return 0; }

제출 #158685

제출 정보

제출 결과

제출 코드

찾은 반례

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력:

입력:

오답 출력:

정답 출력: