(17082) 쿼리와 쿼리

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

단계별로 풀어보기

42단계(그리디 알고리즘 2) 9번째

 

 

 

왼쪽 주머니에 a와 b, 오른쪽 주머니에 c와 d가 들어있고 a<b, c<d라고 생각하자.

이때 구간을 잡는 경우는 [a,c], [b,d]와 [a,d], [b,c] 두 가지이다. 여기서 두번째 경우 [a,d]⊃[b,c]이므로 [a,d]의 최댓값과 같다. 이때 [a,c]∪[b,d]⊆[a,d]이므로 첫번째 경우에서 나오는 최대값의 최소값은 항상 두번째 경우보다 작거나 같다.

따라서 L과 R을 정렬한 뒤 짝지은 [l1,r1]∪[l2,r2]∪...∪[lm,rm] 범위의 최대값이 가능한 최소값이다. li>ri인 경우가 있다면 문제 조건에 의해 쿼리에 관계없이 정답은 항상 10^9이다.

이때 구간의 최대값을 구하는 것은 쿼리로 인해 구간 내 삽입과 삭제가 빈번하게 일어나므로 멀티셋을 쓰면 된다.

 

 

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
using namespace std;
#define INF 1000000000

int main() 
{
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  
  int n, m, q;
  
  cin >> n >> m >> q;
  
  vector<int> v(n+1), l(m), r(m);
  vector<bool> check(n+1);
  
  for(int i=1;i<=n;i++)  cin >> v[i];
  for(int i=0;i<m;i++)  cin >> l[i];
  for(int i=0;i<m;i++)  cin >> r[i];
  
  sort(l.begin(), l.end());
  sort(r.begin(), r.end());
  
  for(int i=0;i<m;i++){
    if(l[i]>r[i]){
      while(q--)  cout << INF << "\n";
      
      return 0;
    }
  }
  
  multiset<int, greater<int>> ms;
  
  for(int i=0,idx=0;i<m;i++){
    idx= max(idx, l[i]);
    
    while(idx<=r[i]){
      check[idx]= true;
      ms.insert(v[idx]);
      idx++;
    }
  }
  
  while(q--){
    int ai, aj;
    
    cin >> ai >> aj;
    
    if(check[ai]&&!check[aj]){
      ms.erase(ms.find(v[ai]));
      ms.insert(v[aj]);
    }else if(!check[ai]&&check[aj]){
      ms.erase(ms.find(v[aj]));
      ms.insert(v[ai]);
    }
    
    swap(v[ai], v[aj]);
    
    cout << *ms.begin() << "\n";
  }
  
  return 0;
}