9345 디지털 비디오 디스크

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

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

A ~ B 번까지 선반에 A~B 번 비디오(순열)가 순서에 상관없이 존재함은

A B선반 구간에서 최솟값이 A이고 최대값이 B인 것인 것과 같다. 

 

#include <iostream>
using namespace std;
using ll = long long;
const ll n_= 3e6+100;
ll n,m,tc,a,b,c,k;
ll min_tree[n_],max_tree[n_],arr[n_];

void init(ll N, ll s, ll e){
    if(s == e){
        min_tree[N] = max_tree[N] = s; return;
    }
    ll mid = (s+e)>>1;
    init(N*2,s,mid);
    init(N*2+1,mid+1,e);
    
    min_tree[N] = min(min_tree[N*2],min_tree[N*2+1]);
    max_tree[N] = max(max_tree[N*2],max_tree[N*2+1]);
}
void getNum(ll N,ll s,ll e, ll idx){
    if(s > idx || idx > e) return;
	if(s == e){
		if(idx == s)  {k = N;return;}
	}
	ll mid = (s+e)/2;
	getNum(N*2,s,mid,idx);
	getNum(N*2+1,mid+1,e,idx);
}

void update(ll N,ll s,ll e,ll idx){
    if(s > idx || e < idx) return;
    if(s == e) return;

	ll mid=(s+e)/2;
	update(N*2,s,mid,idx);
	update(N*2+1,mid+1,e,idx);
    min_tree[N] = min(min_tree[N*2],min_tree[N*2+1]);
    max_tree[N] = max(max_tree[N*2],max_tree[N*2 + 1]);
}
ll min_query(ll N,ll s,ll e,ll l, ll r){
	if(e < l || s > r) return 10000000001;
	if(l <= s && e <= r) return min_tree[N];
	ll mid=(s+e) >> 1;
	return min(min_query(N*2,s,mid,l,r),min_query(N*2+1, mid+1,e,l,r));
}
ll max_query(ll N,ll s,ll e,ll l, ll r){
	if(e < l || s > r) return 0;
	if(l <= s && e <= r) return max_tree[N];
	ll mid=(s+e) >> 1;
	return max(max_query(N*2,s,mid,l,r),max_query(N*2+1, mid+1,e,l,r));
}
void solve(){
	cin>>n>>m;
    init(1,0,n-1);
	while(m--){
		cin>>a;
		if(a == 0){
		    cin>>b>>c;
		    getNum(1,0,n-1,b);
		    ll x = k;
		    getNum(1,0,n-1,c);
		    ll y = k;
		    swap(min_tree[x],min_tree[y]);
		    swap(max_tree[x],max_tree[y]);
		    update(1,0,n-1,b);
		    update(1,0,n-1,c);
		}
		else {
		    cin>>b>>c;
		    ll x = min_query(1,0,n-1,b,c);
		    ll y = max_query(1,0,n-1,b,c);
		   // cout<<x <<" "<<y<<'\n';
		    if(b == x && c == y) cout<<"YES\n";
		    else cout<<"NO\n";
		}
	}

}
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>tc;
	while(tc--) solve();
	return 0;
}