고통받는 난쟁이들 (백준 5817)

안녕하세요. 오늘은 난쟁이들을 고통에서 구해줄 거예요.

문제

https://www.acmicpc.net/problem/5817

아이디어

realarr[i]: i번째에 서있는 난쟁이 번호
arr[i]: i번 난쟁이가 서있는 인덱스

2 b c의 형식의 입력이 들어왔을 경우 arr[b], arr[b+1],arr[b+2]...,arr[c]의 값중 최대/최소를 구하고 그 값의 차가 c-b와 같으면 연속해있다고 할 수 있습니다.

소스코드

#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;

ll maxtree[808080] = { 0 }, mintree[808080] = { 0 }, arr[202020] = { 0 }, realarr[202020] = { 0 };
ll maxinit(ll s, ll e, ll node)
{
    if (s == e) return maxtree[node] = arr[s];
    ll mid = (s + e) / 2;
    return maxtree[node] = max(maxinit(s, mid, node * 2), maxinit(mid + 1, e, node * 2 + 1));
}
ll MAX(ll s, ll e, ll node, ll l, ll r)
{
    if (e < l || r < s) return 0;
    if (l <= s && e <= r) return maxtree[node];
    ll mid = (s + e) / 2;
    return max(MAX(s, mid, node * 2, l, r), MAX(mid + 1, e, node * 2 + 1, l, r));
}
ll mininit(ll s, ll e, ll node)
{
    if (s == e) return mintree[node] = arr[s];
    ll mid = (s + e) / 2;
    return mintree[node] = min(mininit(s, mid, node * 2), mininit(mid + 1, e, node * 2 + 1));
}
ll MIN(ll s, ll e, ll node, ll l, ll r)
{
    if (e < l || r < s) return 2e9;
    if (l <= s && e <= r) return mintree[node];
    ll mid = (s + e) / 2;
    return min(MIN(s, mid, node * 2, l, r), MIN(mid + 1, e, node * 2 + 1, l, r));
}
void change(ll s, ll e, ll node, ll idx, ll num)
{
    if (e < idx || idx < s) return;
    if (s == e)
    {
        mintree[node] = maxtree[node] = num;
        return;
    }
    ll mid = (s + e) / 2;
    change(s, mid, node * 2, idx, num);
    change(mid + 1, e, node * 2 + 1, idx, num);
    maxtree[node] = max(maxtree[node * 2], maxtree[node * 2 + 1]);
    mintree[node] = min(mintree[node * 2], mintree[node * 2 + 1]);
}

int main(void)
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    ll N, M, i, a, b, c;
    cin >> N >> M;
    for (i = 1; i <= N; i++)
    {
        cin >> realarr[i];
        arr[realarr[i]] = i;
    }
    maxinit(1, N, 1); mininit(1, N, 1);

    for (i = 0; i < M; i++)
    {
        cin >> a >> b >> c;
        if (a == 1)
        {
            ll num1 = realarr[b], num2 = realarr[c];
            change(1, N, 1, num1, c);
            change(1, N, 1, num2, b);
            swap(realarr[b], realarr[c]);
        }
        else
        {
            if (MAX(1, N, 1, b, c) - MIN(1, N, 1, b, c) == c - b) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}

감사합니다.