1849 - 순열

 

1849번: 순열

 

#include <stdio.h>

const int LN = 1e5;

int N;
int tree[LN * 3 + 10];
int arr[LN];
int R_ARR[LN];
int R;

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

    return tree[n];
  }

  if (t < s || e < t) { 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;

  return query(n * 2, s, m, qs, qe) + query(n * 2 + 1, m + 1, e, qs, qe);
}

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 target) {
  if (s > e) {
    return;
  }

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

  if (q_res >= target) {
    R = m;
    bs(s, m - 1, target);
  } else {
    bs(m + 1, e, target);
  }
}

void print() {
  for (int n = 1; n <= N; ++n) {
    bs(1, N, arr[n]);

    push(1, 1, N, R, 0);

    R_ARR[R] = n;
  }

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

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

  init();

  print();

  return 0;
}

 

순열복원이랑 똑같은 문제