핵심 아이디어

<aside> 💡

$[L, R]$ 구간에 $L$부터 $R$이 모두 있다면 구간의 $min$값은 $L,$ $max$값은 $R$이다.

</aside>

코드

#include <bits/stdc++.h>
#define FASTIO ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
using namespace std;
typedef long long int ll;

struct Node
{
    int mn, mx;
};

class Seg
{
    private:
        int n;
        vector<Node> tree;

        void build(int node, int start, int end)
        {
            if(start == end){
                tree[node] = {start, start};
                return;
            }

            int mid = start+end>>1;
            build(2*node, start, mid);
            build(2*node+1, mid+1, end);

            Node &l = tree[2*node];
            Node &r = tree[2*node+1];
            tree[node] = {min(l.mn, r.mn), max(l.mx, r.mx)};
        }

        void upd(int node, int start, int end, int idx, int val)
        {
            if(idx<start || end <idx) return;
            if(start == end){
                tree[node] = {val, val};
                return;
            }

            int mid = start+end>>1;

            upd(2*node, start, mid, idx, val);
            upd(2*node+1, mid+1, end, idx, val);

            Node &l = tree[2*node];
            Node &r = tree[2*node+1];
            tree[node] = {min(l.mn, r.mn), max(l.mx, r.mx)};
        }

        Node qry(int node, int start, int end, int left, int right)
        {
            if(end<left || right<start) return {int(1e+9), int(-1e+9)};
            if(left<=start && end<=right) return tree[node];

            int mid = start+end>>1;
            Node l = qry(2*node, start, mid, left, right);
            Node r = qry(2*node+1, mid+1, end, left, right);

            return {min(l.mn, r.mn), max(l.mx, r.mx)};
        }

    public:
        void init(int n)
        {
            this->n = n;
            tree.resize(4*n);
            build(1, 0, n-1);
        }

        void upd(int idx, int val) {upd(1, 0, n-1, idx, val);}
        Node qry(int l, int r) {return qry(1, 0, n-1, l, r);}
};

void solve()
{
    int n, k;
    cin >> n >> k;
    
    Seg seg;
    seg.init(n);

    for(int i = 0; i<k; i++){
        int q, a, b;
        cin >> q >> a >> b;
        if(q == 0){
            Node aVal = seg.qry(a, a);
            Node bVal = seg.qry(b, b);

            seg.upd(a, bVal.mn);
            seg.upd(b, aVal.mn);
        }
        else{
            Node node = seg.qry(a, b);
            if(node.mn == a && node.mx == b){
                cout << "YES\\n";
            }
            else{
                cout << "NO\\n";
            }
        }
    }
}

signed main()
{
    FASTIO;
    int _tc; cin >> _tc;
    while(_tc--) solve();    
    return 0;
}