굉장한 학생

Problem link: https://www.acmicpc.net/problem/2336

결과적으로 단 1개의 segment tree를 사용하여 풀 수 있는 문제이지만, (1)입력을 잘못 이해해서, (2)알고리즘을 잘 떠올리지 못해서 꽤나 고전했다.

(1)의 경우는 별건 아니고, 입력이 1등 ~ N등을 한 학생의 번호로 주어지는 것을 주의해주면 된다.

나의 경우에는 입력이 1번 ~ N번 학생의 등수로 주어진다고 착각하고 풀어서 많이 고민을 했었다.

(2)의 경우 우선 아래와 같은 전처리를 수행한다.

• A. 일단, 두번째 시험의 등수를 index로, 세번째 시험의 점수를 value로 하는 min segment tree를 준비한다.
• B. 학생들의 시험성적을 {첫번째 시험 등수, 두번째 시험 등수, 세번째 시험 등수}로 표현되는 구조체로 표현한다.
• C. B의 구조체 벡터를 첫번째 시험 등수를 기준으로 오름차순 정렬한다.

이제 C에서 정렬한 구조체 벡터를 순회한다고 해보자.

i번째 요소(첫번째 시험에서 i등을 한 학생)를 보고 있다고할 때, [0, i-1]번째 요소들은 모두 첫번째 시험에 한해서는 i번 요소가 나타내는 학생보다는 시험을 잘 본 학생들이다.

따라서, 이제 [0, i - 1]번째 요소가 가르키는 학생들 중 두번째, 세번째 시험 모두 i번째 요소가 가르키는 학생보다 잘본 학생이 있는지 찾아주면 된다.

여기서 사고의 전환이 두번 필요한데,

• 굳이 "[0, i - 1]번째"라는 표현에 억메일 필요가 없다.
  • 구조체 벡터를 순차적으로 순회하고 있으므로 자연스럽게 아직 "[i, N]"번째 학생들은 보지 않은 상태이다.
• 두번째 시험 / 세번째 시험을 모두 잘 본 학생을 구할 때, 두번째 시험 등수 위치에 세번째 시험 점수를 저장하는 min segment tree 하나만을 사용해보자.
  • 위와 같이 하면, 현재 보고 있는 i번째 요소가 가르키는 학생의 두번째 시험 등수보다 높은(더 잘본) 등수 구간에서 i번째 요소가 가르키는 학생의 세번째 시험 등수보다 작은 수가 존하는지를 살핌으로써 두번째/세번째 시험을 모두 보다 더 잘 본 학생이 존재하는지를 빠르게 알 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>

using namespace std;

const size_t kMaxNumberOfStudents = 500000;

class Exam
{
public:
  static const size_t k1st = 0;
  static const size_t k2nd = 1;
  static const size_t k3rd = 2;

  size_t ranks_[3];

  bool operator<(const Exam& exam) const
  {
    return ranks_[k1st] < exam.ranks_[k1st];
  }
};

class RankTree
{
private:
  size_t size_;
  size_t node_[kMaxNumberOfStudents * 4];

  size_t Update(const size_t root, const size_t root_left, const size_t root_right, const size_t update_index,
                const size_t update_value)
  {
    if (update_index < root_left || root_right < update_index)
    {
      return node_[root];
    }

    if (root_left == root_right)
    {
      return (node_[root] = update_value);
    }

    const size_t root_mid = (root_left + root_right) / 2;
    const size_t left = Update(2 * root, root_left, root_mid, update_index, update_value);
    const size_t right = Update(2 * root + 1, root_mid + 1, root_right, update_index, update_value);

    return (node_[root] = min(left, right));
  }

  size_t Query(const size_t root, const size_t root_left, const size_t root_right, const size_t query_left,
               const size_t query_right)
  {
    if (query_right < root_left || root_right < query_left)
    {
      return kMaxNumberOfStudents + 1;
    }

    if (query_left <= root_left && root_right <= query_right)
    {
      return node_[root];
    }

    const size_t root_mid = (root_left + root_right) / 2;
    const size_t left = Query(2 * root, root_left, root_mid, query_left, query_right);
    const size_t right = Query(2 * root + 1, root_mid + 1, root_right, query_left, query_right);

    return min(left, right);
  }

public:
  RankTree(const size_t size) : size_(size)
  {
    memset(node_, kMaxNumberOfStudents + 1, size_ * 4 * sizeof(size_t));
  }

  void Update(const size_t index, const size_t value)
  {
    Update(1, 1, size_, index, value);
  }

  size_t Query(const size_t left, const size_t right)
  {
    if (left > right)
    {
      return kMaxNumberOfStudents + 1;
    }

    return Query(1, 1, size_, left, right);
  }
};

size_t number_of_students;
vector<Exam> exam;
RankTree* rank_tree;

int main(void)
{
  // For faster IO
  ios_base::sync_with_stdio(false);
  cout.tie(nullptr);
  cin.tie(nullptr);

  // Read input
  cin >> number_of_students;

  exam.assign(number_of_students, Exam());

  for (size_t rank = 1; rank <= number_of_students; ++rank)
  {
    size_t student_no;
    cin >> student_no;
    exam[student_no - 1].ranks_[Exam::k1st] = rank;
  }

  for (size_t rank = 1; rank <= number_of_students; ++rank)
  {
    size_t student_no;
    cin >> student_no;
    exam[student_no - 1].ranks_[Exam::k2nd] = rank;
  }

  for (size_t rank = 1; rank <= number_of_students; ++rank)
  {
    size_t student_no;
    cin >> student_no;
    exam[student_no - 1].ranks_[Exam::k3rd] = rank;
  }

  // Preprocess
  sort(exam.begin(), exam.end());
  rank_tree = new RankTree(number_of_students);

  // Solve
  size_t tremendous = 0;

  for (size_t idx = 0; idx < number_of_students; ++idx)
  {
    if (rank_tree->Query(1, exam[idx].ranks_[Exam::k2nd] - 1) > exam[idx].ranks_[Exam::k3rd])
    {
      ++tremendous;
    }

    rank_tree->Update(exam[idx].ranks_[Exam::k2nd], exam[idx].ranks_[Exam::k3rd]);
  }

  cout << tremendous << "\n";

  return 0;
}