1777 - 순열복원

 

1777번: 순열복원

 

#include <stdio.h>

const int LN = 1e5 * 3;
int tree[LN];

int N, r;
int ARR[LN];
int R_ARR[LN];

int push(int n, int s, int e, int t, int v) {
  if (t < s || e < t) { return tree[n]; }
  if (s == e && t == s) {
    tree[n] = v;

    return tree[n];
  }


  int m = (s + e) / 2;

  push(n * 2, s, m, t, v);
  push(n * 2 + 1, m + 1, e, t, v);

  tree[n] = tree[n * 2] + tree[n * 2 + 1];

  return tree[n];
}

int query(int n, int s, int e, int qs, int qe) {
  if (qe < s || e < qs) { return 0; }
  if (qs <= s && e <= qe) { return tree[n]; }

  int m = (s + e) / 2;

  int l = query(2 * n, s, m, qs, qe);
  int r = query(2 * n + 1, m + 1, e, qs, qe);

  return l + r;
}

void init() {
  scanf("%d", &N);

  for (int n = 1; n <= N; ++n) {
    scanf("%d", &ARR[n]);

    push(1, 1, N, n, 1);
  }
}

void bs(int s, int e, int t) {
  if (s > e) {
    return;
  }

  int m = (s + e) / 2;
  int seg_t = query(1, 1, N, m, N) - 1;

  if (t <= seg_t) {
    r = m;
    bs(m + 1, e, t);
  } else {
    bs(s, m - 1, t);
  }
}

void print() {
  for (int n = 1; n <= N; ++n) {
    printf("%d ", R_ARR[n]);
  }
}

void cal() {
  for (int n = N; n >= 1; --n) {
    int t = ARR[n];
 
    bs(1, N, t);

    R_ARR[r]= n;

    push(1, 1, N, r, 0);
  }
}

int main(void) {
  // freopen("1777.txt", "r", stdin);

  init();

  cal();

  print();

  return 0;
}

 

아직 이진탐색 / 세그먼트 트리 더 연습해야할 듯