BOJ 3045 - 이중 연결 리스트

BOJ 3045 - 이중 연결 리스트

완성된 배열 $A$ 를 갖고 있다고 하자.

정답의 개수는 $N - n(LIS_A)$ 이다.

왜냐면 LIS에 포함되지 않은 원소들을 옮김으로써 정렬해줄 수 있기 때문이다.

완성된 배열 $A$는 링크드리스트를 빡구현해서 다시 만들 수 있고,

LIS에 포함되어있지 않은 원소들을 다른 원소 앞이나 뒤에 붙여줄지 결정하는건 std:set 을 잘 활용하면 $O(N \log N)$ 에 가능하다.

struct Node {  
   Node *prev = 0, *next = 0;  
   int num;  
  
   Node(int num) : num(num) {}  
};  
  
void solve() {  
   int N, M;  
   cin >> N >> M;  
   vector<Node *> nodes(N);  
   for (int i = 0; i < N; i++) {  
      nodes[i] = new Node(i);  
      if (i > 0) {  
         nodes[i]->prev = nodes[i - 1];  
         nodes[i - 1]->next = nodes[i];  
      }  
      Node *node = new Node(i);  
   }  
  
   while (M--) {  
      string cmd;  
      int a, b;  
      cin >> cmd >> a >> b, a--, b--;  
      if (a == b) continue;  
      bool is_a_first = nodes[a]->prev == 0;  
      bool is_b_first = nodes[b]->prev == 0;  
      bool is_a_last = nodes[a]->next == 0;  
      bool is_b_last = nodes[b]->next == 0;  
  
      if (cmd == "A") {  
         // 앞에 추가  
         if (nodes[a]->next == nodes[b]) continue;  
  
         if (!is_a_first && !is_a_last) {  
            // a의 양옆 노드 연결  
            nodes[a]->prev->next = nodes[a]->next;  
            nodes[a]->next->prev = nodes[a]->prev;  
         } else if (!is_a_first) {  
            assert(is_a_last);  
            nodes[a]->prev->next = 0;  
         } else if (!is_a_last) {  
            assert(is_a_first);  
            nodes[a]->next->prev = 0;  
         }  
  
         // a를 업데이트  
         nodes[a]->next = nodes[b];  
         nodes[a]->prev = nodes[b]->prev;  
  
         // b의 전 노드를 업데이트  
         if (!is_b_first)  
            nodes[b]->prev->next = nodes[a];  
         // b를 업데이트  
         nodes[b]->prev = nodes[a];  
      } else {  
         // 뒤에 추가  
         if (nodes[a]->prev == nodes[b]) continue;  
  
         if (!is_a_first && !is_a_last) {  
            // a의 양옆 노드 연결  
            nodes[a]->prev->next = nodes[a]->next;  
            nodes[a]->next->prev = nodes[a]->prev;  
         } else if (!is_a_first) {  
            assert(is_a_last);  
            nodes[a]->prev->next = 0;  
         } else if (!is_a_last) {  
            assert(is_a_first);  
            nodes[a]->next->prev = 0;  
         }  
  
         // a를 업데이트  
         nodes[a]->prev = nodes[b];  
         nodes[a]->next = nodes[b]->next;  
  
         // b의 후 노드를 업데이트  
         if (!is_b_last)  
            nodes[b]->next->prev = nodes[a];  
         // b를 업데이트  
         nodes[b]->next = nodes[a];  
      }  
   }  
   int first = -1;  
   for (auto &node: nodes) {  
      if (node->prev == 0) {  
         first = node->num;  
      }  
   }  
   vi result;  
   Node *cur = nodes[first];  
   while (cur) {  
      result.pb(cur->num);  
      cur = cur->next;  
   }  
   for (int i: result) debug(i + 1);  
  
   vi lis(N), m;  
   for (int i = 0; i < N; i++) {  
      int j = lbi(m, result[i]);  
      if (j == sz(m)) m.pb(result[i]);  
      else m[j] = result[i];  
      lis[i] = j + 1;  
   }  
   int cur_lis = maxe(lis);  
   set<int> s;  
   for (int i = N - 1; i >= 0; i--) {  
      if (lis[i] == cur_lis) {  
         s.insert(result[i]);  
         cur_lis--;  
      }  
   }  
   vector<array<int, 3>> ans;  
   for (int i = 0; i < N; i++) {  
      if (hass(s, i)) {  
         continue;  
      }  
      auto it = s.lower_bound(i);  
      if (it == s.end()) {  
         ans.pb({2, i, *s.rbegin()});  
      } else {  
         ans.pb({1, i, *it});  
      }  
      s.insert(i);  
   }  
   cout << sz(ans) << endl;  
   for (auto[a, b, c]: ans) {  
      cout << (a == 2 ? "B " : "A ") << b + 1 << ' ' << c + 1 << endl;  
   }  
  
}