디지털 비디오 디스크(DVDs) C++ - 백준 9345

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

세그 응용은 정말 다양해서 문제를 많이 풀어봐야겠다.

문제 접근

처음에는 공차가 1인 등차수열만 생각해서 합공식으로 접근하다가

공차가 1이 아닌 등차수열을 생각하기 전까지 무한 WA를 받았다.

따라서 새로운 접근이 필요했다.

모든 원소가 $[0,n-1]$에 대해 일대일 대응이므로

어떤 구간 내 최대/최소를 알면 바로 답을 구할 수 있다.

구간 $[a,b]$에 $a$부터 $b$가 존재하려면 당연히

최솟값은 $a$이고 최댓값은 $b$일것이다.

아닌 경우는 없음이 자명하다.

따라서 이를 구현한 코드는 다음과 같다.

#include <bits/stdc++.h>
#define fi first
#define se second
#define SIZE 100001
typedef long long ll;
using namespace std;

int mtree[SIZE*4],ntree[SIZE*4];
int idx[SIZE];

void update(int x, int v, int node, int s, int e){
    if(x<s || e<x) return;
    if(s==e){
        mtree[node]=v;
        ntree[node]=v;
        return;
    }
    int mid=(s+e)/2;
    update(x,v,2*node,s,mid);
    update(x,v,2*node+1,mid+1,e);
    mtree[node]=max(mtree[2*node],mtree[2*node+1]);
    ntree[node]=min(ntree[2*node],ntree[2*node+1]);
}

pair<int,int> query(int l, int r, int node, int s, int e){
    if(r<s || e<l) return {SIZE,-1};
    if(l<=s && e<=r) return {ntree[node],mtree[node]};
    int mid=(s+e)/2;
    pair<int,int> ll=query(l,r,2*node,s,mid);
    pair<int,int> rr=query(l,r,2*node+1,mid+1,e);
    return {min(ll.fi,rr.fi),max(ll.se,rr.se)};
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    int tt;
    cin >> tt;
    while(tt--){
        int n,k;
        cin >> n >> k;
        for(int i=0;i<n;i++){
            update(i,i,1,0,n-1);
            idx[i]=i;
        }
        while(k--){
            int q,a,b;
            cin >> q >> a >> b;
            if(q){
                pair<int,int> qq=query(a,b,1,0,n-1);
                cout << ((qq.fi==a && qq.se==b)?"YES":"NO") << '\n';
            }
            else{
                swap(idx[a],idx[b]);
                update(a,idx[a],1,0,n-1);
                update(b,idx[b],1,0,n-1);
            }
        }
    }
    return 0;
}