Untitled

 avatar
unknown
c_cpp
2 years ago
2.4 kB
14
Indexable
#include <iostream>
#include <algorithm>

using namespace std;
struct node{
    int mini;
    int maxi;
};

int n;
node tree[400003];
int arr[100001];

void init(int node, int start, int end){
    if(start==end){
        tree[node].maxi = arr[start];
        tree[node].mini = arr[start];
        return;
    }

    int mid = (start+end)>>1;
    init(2*node, start, mid);
    init(2*node+1, mid+1, end);
    tree[node].mini = min(tree[2*node].mini, tree[2*node+1].mini);
    tree[node].maxi = max(tree[2*node].maxi, tree[2*node+1].maxi);

    return;
}

void update(int node, int start, int end, int idx, int change){
    if(idx < start || idx > end){
        return;
    }

    if(start == end){
        tree[node] = {change, change};
        // arr[idx] = change;
        return;
    }
    
    int mid = (start+end)>>1;
    update(2*node, start, mid, idx, change);
    update(2*node+1, mid+1, end, idx, change);
    tree[node] = {min(tree[2*node].mini, tree[2*node+1].mini), max(tree[2*node].maxi, tree[2*node+1].maxi)};
}

// node left, node right
node query(int N, int start, int end, int left, int right){
    if(start > right || end < left){
        // default 
        return {INT32_MAX, INT32_MIN};
    }
    if(left<= start && end <= right){
        return tree[N];
    }
    int mid = (start+end)>>1;
    node L = query(2*N, start, mid, left, right);
    node R = query(2*N+1, mid+1, end, left, right);
    return {min(L.mini, R.mini), max(L.maxi, R.maxi)};
}

int main(void){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int t;
    cin >> t;
    while(t--){
        int k;
        cin >> n >> k;
        for(int i = 0;i<4*n;i++){
            tree[i] = {INT32_MAX, -1};
        }
        for(int i = 1;i<=n;i++){
            arr[i] = i;
        }
        init(1,0,n-1);
        int q, a, b;
        
        while(k--){
            cin >> q;
            if(q==0){
                cin >> a >> b;
                // A <- B
                int A = arr[a];
                // B <- A
                int B = arr[b];
                update(1,0,n-1,b,A);
                update(1,0,n-1,a,B);
                swap(arr[a], arr[b]);
            }else{
                cin >> a >> b;
                node res = query(1,0,n-1,a,b);
                if(res.mini == a && res.maxi == b){
                    cout << "YES\n";
                }else{
                    cout << "NO\n";
                }
            }
        }
    }
}
Editor is loading...