백준 9345 : 디지털 비디오 디스크(DVDs)

문제 링크

최대, 최소 세그먼트 트리를 이용해서 해결하였다.

주어진 문제에서 해결해야 하는 쿼리는 두 가지이다.
1.선반 A와 B의 책을 바꿈
2.L~R까지 책들이 L~R의 책으로 구성되어 있는지 판단

1의 쿼리는 쉽게 해결할 수 있는데, 중요한 것은 2이다. 이 쿼리는 L~R까지의 책 중 최댓값이 R이고, 최솟값이 L인지를 확인함으로써 O(logn) 에 구할 수 있다. 책의 번호가 모두 다르기 때문에, L~R에서 최댓값이 R이고 최솟값이 L이면 L~R의 책이 모두 있다고 판단할 수 있다. 따라서 최솟값과 최댓값 세그먼트 트리 두개를 만들어 각 쿼리에 대해 사용하면 된다.

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <vector>
#include <utility>
#include <deque>

using namespace std;

typedef pair<int,int> pii;
typedef long long ll;

const int INF = 21 * 1e8;
const int MAX = 1e9;

int n,k;

vector<int> maxseg;
vector<int> minseg;
vector<int> vec;

int Init(vector<int>& segtree,int idx,int s,int e,bool ismax)
{
    if(s == e) return segtree[idx] = vec[s];

    int m = (s+e)/2;
    
    Init(segtree,2*idx,s,m,ismax);
    Init(segtree,2*idx+1,m+1,e,ismax);

    if(ismax) return segtree[idx] = max(segtree[2*idx],segtree[2*idx+1]);
    else return segtree[idx] = min(segtree[2*idx],segtree[2*idx+1]);;
}

int Update(vector<int>& segtree,int newidx,int newval,int idx,int s,int e,bool ismax)
{
    if(!(s <= newidx && newidx <= e)) return segtree[idx];

    if(s == e) return segtree[idx] = newval;

    int m = (s+e)/2;

    Update(segtree,newidx,newval,2*idx,s,m,ismax);
    Update(segtree,newidx,newval,2*idx+1,m+1,e,ismax);

    if(ismax) return segtree[idx] = max(segtree[2*idx],segtree[2*idx+1]);
    else return segtree[idx] = min(segtree[2*idx],segtree[2*idx+1]);
}

int get(vector<int>& segtree,int qs,int qe,int idx,int s,int e,bool ismax)
{
    if(e < qs || qe < s) return ismax ? -INF : INF;

    if(qs <= s && e <= qe) return segtree[idx];

    int m = (s+e)/2;

    int l = get(segtree,qs,qe,2*idx,s,m,ismax);
    int r = get(segtree,qs,qe,2*idx+1,m+1,e,ismax);
    if(ismax) return max(l,r);
    else return min(l,r);
}

int minupdate(int newidx,int newval)
{
    return Update(minseg,newidx,newval,1,0,n-1,false);
}

int maxupdate(int newidx,int newval)
{
    return Update(maxseg,newidx,newval,1,0,n-1,true);
}

int minget(int qs,int qe)
{
    return get(minseg,qs,qe,1,0,n-1,false);
}

int maxget(int qs,int qe)
{
    return get(maxseg,qs,qe,1,0,n-1,true);
}

int main()
{
    ios_base :: sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
 
    int t;
    cin>>t;

    for(int i = 0;i<1e5;i++)
    {
        vec.push_back(i);
    }
    while(t--)
    {
        
        cin>>n>>k;

        maxseg = vector<int>(4*n);
        minseg = vector<int>(4*n);
        
        Init(maxseg,1,0,n-1,true);
        Init(minseg,1,0,n-1,false);

        for(int i = 0;i<k;i++)
        {
            int q,a,b;
            cin>>q>>a>>b;

            if(q == 0)
            {
                int preva = maxget(a,a);
                int prevb = maxget(b,b);

                maxupdate(b,preva); minupdate(b,preva);
                maxupdate(a,prevb); minupdate(a,prevb); 
            }
            else
            {
                int maxb = maxget(a,b);
                int minb = minget(a,b);

                if(maxb == b && minb == a) cout<<"YES\n";
                else cout<<"NO\n";
            }
            
        }
    }
    return 0;
}