등산 을 좋아 하 는 꼬마 Z

E - 등산 을 좋아 하 는 꼬마 Z
Time Limit: 
6000/3000MS (Java/Others)    
Memory Limit: 
128000/64000KB (Java/Others)
Submit  Status
Problem Description
옛날 에 ACdream 왕국 이 있 었 는데 이 왕국 은 산 으로 둘러싸 여 있 었 기 때문에 밖 에 있 는 사람들 은 그 존 재 를 아 는 사람 이 별로 없 었 다.
이 왕국 에는 등산 을 좋아 하 는 젊은이 가 있 었 다. 작은 Z 는 등산 을 하 는 과정 에서 자연 을 정복 할 수 있다 는 느낌 이 들 었 다.
작은 Z 는 전체 경로 에서 지나 가 는 산 의 높이 의 최대 치 를 나타 내 는 등산 경로 의 어려움 정 도 를 정의 한다.
그러나 아 크 드 림 왕국 은 신기 한 왕국 으로 산 의 높이 가 자주 바 뀌 기 때문에 작은 Z 는 수시로 산 의 높이 를 재 측정 해 야 한다.
작은 Z 는 높이 측정 에 지 쳐 모든 경로 의 어려움 정 도 를 고려 할 정력 이 없다.그래서 도와 달라 고.
Input
여러 그룹의 데이터, 각 그룹의 데 이 터 는 먼저 하나의 정수 N (N < = 100000) 으로 ACdream 왕국 을 둘 러 싼 산 의 수량 을 나타 낸다.
다음은 N 개의 정수 로 각 산 의 높이 를 나타 낸다.
다음은 정수 Q (Q < = 100000) 로 작은 Z 가 진행 하 는 동작 을 나타 낸다.
다음은 Q 줄 입 니 다. 각 줄 은 세 개의 정수 a, b, c 입 니 다. a 가 0 이면 작은 Z 를 대표 하여 b 번 째 산 을 재 측정 하고 높이 는 c 입 니 다. (1 < = b < = N, 1 < = c < = 100000)
a 가 1 이면 작은 Z 가 b 에서 c 까지 의 최소 어려움 정 도 를 알 고 싶다 는 뜻 이다.(1<=b,c<=N)
Output
작은 Z 에 대한 질문 마다 하나의 정 수 를 출력 하 는 것 은 경로 상의 최소 어려움 정 도 를 나타 낸다.
Sample Input

6
1 10 2 20 3 30
3
1 1 5
0 6 3
1 1 5

Sample Output

20
3

Hint
이 야 기 는 이 렇 습 니 다. Z 군 은 토끼 한 마리 와 거북이 한 마 리 를 키 웠 고 Z 군의 흥미 에 영향 을 받 아 토끼 와 거북이 도 등산 을 좋아 합 니 다 ~
어느 날 토끼 와 거북 이 는 1 호 산 을 기점 으로 5 호 산 을 종점 으로 규정 하고 시합 을 한다.
Z 군 이 "준비, 기 ~"라 고 말 하 자 영리 한 토끼 는 1 - 2 - 3 - 4 - 5 순 으로 필사적으로 달 렸 다.
이것 은 전문 갱 동료의 작은 Z 가 자신의 지 도 를 발견 한 6 호 산 의 높이 가 틀 렸 습 니 다. 0 을 하나 더 썼 습 니 다. 빨리 고 쳤 습 니 다 ~
그런데 토끼 가 어디로 갔 는 지 모 르 겠 어 요. 그래서 거북이 가 1 - 6 - 5 를 천천히 따라 산책 을 하 다가 거북이 가 승 리 를 거 두 었 어 요 ~!
'아 드 림 동화 이야기 - 거북이 토끼 경주' 완료
제목 대의: 수열 을 제시 하고 양쪽 이 연결 되 며 구간 의 최대 치 를 구하 고 바로 있 는 구간 과 거꾸로 있 는 구간 을 포함한다.
분석: 선분 나무 가 약간 변형 되 었 다.바로 서 있 는 구간 은 RMQ 로 역 주 행 은 구간 왼쪽 끝 점 에서 1, 구간 오른쪽 끝 점 에서 n 으로 나 뉜 다.
코드:

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int maxn = 200010;
int Max[4*maxn];

void PushUP(int root) {
    Max[root] = max(Max[2*root+1], Max[2*root+2]);
    return;
}

void Update(int root, int l, int r, int p, int c) {
    if(l == r) {
        Max[root] = c;
        return;
    }
    int m = (l+r)>>1;
    if(p <= m) Update(2*root+1, l, m, p, c);
    else Update(2*root+2, m+1, r, p, c);
    PushUP(root);
    return;
}

int Query(int root, int l, int r, int L, int R) {
    if(L <= l && r <= R) {
        return Max[root];
    }
    int m = (l+r)>>1;
    int ans = 0;
    if(L <= m) ans = max(ans, Query(2*root+1, l, m, L, R));
    if(m < R) ans = max(ans, Query(2*root+2, m+1, r, L, R));
    return ans;
}

void Build(int root, int l, int r) {
    if(l == r) {
        scanf("%d", &Max[root]);
        return;
    }
    int m = (l+r)>>1;
    Build(2*root+1, l, m);
    Build(2*root+2, m+1, r);
    PushUP(root);
    return;
}

int main() {
    int n;
    while(~scanf("%d", &n)) {
        if(n == 0) continue;
        Build(0, 1, n);
        int m, op, a, b;
        scanf("%d", &m);
        while(m--) {
            scanf("%d%d%d", &op, &a, &b);
            if(op){
                if(a > b) swap(a, b);
                printf("%d
", min(Query(0, 1, n, a, b), max(Query(0, 1, n, 1, a), Query(0, 1, n, b, n))));
            }
            else Update(0, 1, n, a, b);
        }
    }
    return 0;
}