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

문제 URL : https://www.acmicpc.net/problem/9345

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

문제 접근법:

세그먼트 트리문제인데

swap를 하더라도 해당구간 b~c까지의합이

세그트리와 같으면 답인줄 알았습니다. 83프로 까지는 맞는데 틀리더군요

다른방법이 도저히 생각이안나서

다른블로그에 참고했는데

신기하게도 swap를하더라고 해당구간에서 min값과 max값이 동일하면 모든수가 있다는것이 보장이 되더군요

 

소스코드:

#include<bits/stdc++.h>
#include<unordered_set>
using namespace std;
#define ll long long
vector<pair<ll,ll>> tree;
vector<tuple<ll,ll,ll>> iv;
int n,m;
void input(){
	cin>>n>>m;
	iv.clear();
	tree=vector<pair<ll,ll>>(2*n);
	for(int i=0;i<n;i++)tree[i+n]={i,i};
	ll a,b,c;
	for(int i=0;i<m;i++){
		cin>>a>>b>>c;
		iv.push_back({a,b,c});
	}
}
void insert(pair<ll,ll> &t,pair<ll,ll> a,pair<ll,ll> b){
	t.first=min(a.first,b.first);
	t.second=max(a.second,b.second);
}
void init(){
	for(int i=n-1;i>0;i--){
		insert(tree[i],tree[i<<1],tree[i<<1|1]);
	}
}
void update(ll p,ll val){
	for(tree[p+=n]={val,val};p>1;p>>=1){
		insert(tree[p>>1],tree[p],tree[p^1]);
	}
}
pair<ll,ll> query(ll l,ll r){
	pair<ll,ll> res = {1e15,-1e15};
	for(l+=n,r+=n+1;l<r;l>>=1,r>>=1){
		if(l&1){
			insert(res,res,tree[l++]);;
		}
		if(r&1)insert(res,res,tree[--r]);
	}
	return res;
}
void solve(){
	init();
	string res[]={"NO","YES"};
	for(auto[a,b,c]:iv){
		if(a==0){
			swap(tree[b+n],tree[c+n]);
			update(b,tree[b+n].first);
			update(c,tree[c+n].first);
		}
		else{
			pair<ll,ll> q=query(b,c);
			cout<<res[q.first==b&&q.second==c]<<"\n";
		}

	}
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	//freopen("input.txt","r",stdin);
	int test;
	cin>>test;
	while(test--){
		input();
		solve();
	}
}

 

궁금한점 혹은 모르는점 논리적인 오류등 어떤질문이든 댓글은 언제나 환영입니다.