boj9345.cpp

#include <iostream>
#include <cstdio>
#include <algorithm>
  
using namespace std;
  
#define MAXN 100100
#define INF 987654321
  
int p=1;
  
int min_indexTree[5 * MAXN];
int max_indexTree[5 * MAXN];
  
int Left[MAXN], Right[MAXN];
  
int check(int left, int right){
    int Max = -INF;
    int Min = INF;
  
    int firstL = left, firstR = right;
    left += p;
    right += p;
  
    while (left <= right){
        if ((left&1)){
            Max = max(Max, max_indexTree[left]);
            Min = min(Min, min_indexTree[left]);
            left++;
        }
        if (!(right &1)){
            Max = max(Max, max_indexTree[right]);
            Min = min(Min, min_indexTree[right]);
            right--;
        }
        left >>= 1;
        right >>= 1;
    }
  
    if (Min == firstL && Max == firstR)
        return 1;
    else
        return 0;
}
  
void change(int index, int item){
    index += p;
      
    min_indexTree[index] = item;
    max_indexTree[index] = item;
  
    for (int i = (index>>1); i >= 1; (i >>=1)){
        min_indexTree[i] = min(min_indexTree[i * 2], min_indexTree[i * 2+1]);
        max_indexTree[i] = max(max_indexTree[i * 2], max_indexTree[i * 2+1]);
    }
}
  
int main(){
    int T;
    cin >> T;
    while (T--){
        int N, K;
        int flag;
        p = 1;
        cin >> N >> K;
  
        while (N > p) p <<= 1;
  
        for (int i = 0; i< N; i++){
            max_indexTree[i+p] = i;
            min_indexTree[i+p] = i;
        }
  
        for (int i = p + N; i < (p << 1); i++){
            max_indexTree[i] = -INF;
            min_indexTree[i] = INF;
        }
  
        //부모층 구성
        for (int i = p - 1; i >= 1; i--){
            max_indexTree[i] = max(max_indexTree[i * 2], max_indexTree[i * 2 + 1]);
            min_indexTree[i] = min(min_indexTree[i * 2], min_indexTree[i * 2 + 1]);
        }
  
        for (int i = 0; i < K; i++){
            scanf("%d%d%d", &flag, &Left[i], &Right[i]);
            if (flag == 0){
                int left_temp = min_indexTree[Left[i]+p];
                int right_temp = min_indexTree[Right[i]+p];
                change(Left[i], right_temp);
                change(Right[i], left_temp);
            }
            else{
                int temp = check(Left[i], Right[i]);
  
                if (temp == 1)
                    printf("YES\n");
                else
                    printf("NO\n");
            }
        }
    }
    return 0;
}