📝 문제 정보#
🧐 관찰 및 접근#
- 수열에서의 swap연산이 주어지고, 수열의 $L, R$ 범위가 주어졌을 때 해당 범위에 $L \leq x \leq R$의 모든 수가 있는지 묻는 문제이다.
- 합같은것으로는 저걸 구분할 수가 없다. $(3, 4)$나 $(2, 5)$나 같으니까.
- 아하, DVD들끼리 겹치지 않으므로 구간 최소/최댓값을 이용하면 되겠다.
💻 풀이#
- 코드 (C++):
void solve(){
int N, K; cin >> N >> K;
vector<pii> a(N);
rep(i, 0, N) a[i] = {i, i};
SegmentTree ST(N, a);
while(K--){
int op, a, b; cin >> op >> a >> b;
if(op == 0){
int aval = ST.query(a, a).first;
int bval = ST.query(b, b).first;
ST.set(a, bval);
ST.set(b, aval);
}
else{
pii res = ST.query(a, b);
if(res.first == a && res.second == b) cout << "YES\n";
else cout << "NO\n";
}
}
}