Swap

Rozwiązanie

Kluczem do rozwiązania jest połączenie rozwiązania zachłannego oraz leniwego podejmowania decyzji. Permutacja $\pi_1$ jest leksykograficznie mniejsza niż permutacja $\pi_2$, jeśli pierwszy element $i$ na którym się różnią spełnia $\pi_1(i) < \pi_2(i)$. Zatem możemy przeglądać elementy od lewej do prawej i za każdym razem próbować ustawić aktualnie przeglądany element na najmniejszy możliwy.

O tym, czy zamieniamy elementy miejscami, będziemy decydować leniwie. Na początku dla żadnego kroku nie mamy podjętej decyzji. Następnie, podczas przeglądania elementu $i$, patrzymy jakie decyzje musielibyśmy podjąć, żeby $\pi(i)$ stało się najmniejsze możliwe. W kolejnych krokach będziemy musieli respektować podjęte decyzje.

Informacje o wartościach permutacji będziemy reprezentować w postaci acyklicznego grafu. Wierzchołek node grafu może być dwóch rodzajów: albo ustaloną wartością, albo wartością zależną od pewnej decyzji.

Jeśli jest ustaloną wartością, to trzymamy ją w składowej value. Jeśli natomiast zależy od pewnej decyzji, to trzymamy składowe: fixed -- wskaźnik na informację o decyzji, le -- wskaźnik na wierzchołek, który zawiera informacje o wartości w przypadku, gdy decyzja będzie „nie zamieniamy”, ri -- wskaźnik na wierzchołek, który zawiera informacje o wartości dla decyzji „zamieniamy”.

Dla wierzchołka potrzebujemy dwóch operacji: ustalenie jaka jest jego najmniejsza możliwa wartość oraz wykonanie niezbędnych decyzji, żeby ustawić taką wartość.

W przypadku wyznaczania minimum, przechodzimy po grafie. Dla wierzchołka z ustaloną wartością zwracamy value, a dla nieustalonego patrzymy na jego decyzję. Jeśli nie była podjęta, to zwracamy minimum z rekurencyjnie obliczonych wartości dla wierzchołków le i ri, a jeśli była, to wartość z odpowiedniego z tych wierzchołków.

Mając minimalną wartość, jeszcze raz przechodzimy graf, aby ustalić wymuszone decyzje. Dla wierzchołka bez podjętej decyzji ustalamy ją tak, aby uzyskać minimum. Dla uproszczenia implementacji, jeśli decyzja będzie „zamieniamy”, to możemy po prostu zamienić miejscami wartości wierzchołków le i ri.

Poniżej implementacja struktury wierzchołka:

struct node {
  node* le;
  node* ri;
  bool* fixed;
  int value;

  int minimum() {
    if (!le) {
      return value;
    } else if (*fixed) {
      return le->minimum();
    } else {
      return min(le->minimum(), ri->minimum());
    }
  }

  void fix(int val) {
    if (!le) {
      assert(val == value);
    } else {
      if (!*fixed && ri->minimum() == val) {
        swap(*le, *ri);
      }
      *fixed = true;
      le->fix(val);
    }
  }
};

Teraz wystarczy stworzyć $n$ wierzchołków zawierających ustalone wartości permutacji, oraz $2(n-1)$ wierzchołków zależących od decyzji. W tym celu zastępujemy wierzchołek $i$-ty nowym wierzchołkiem zależnym od decyzji $d$, który w przypadku podjęcia decyzji „nie zamieniamy” daje starą wartość wierzchołka $i$, a w przypadku dezyzji „zamieniamy” daje starą wartość wierzchołka $i/2$. Analogicznie zastępujemy wierzchołek $i/2$, przy czym decyzja $d$ jest ta sama, ale role starych wartości są zamienione.

Na końcu $n$ razy wyznaczamy minimum i ustalamy decyzje. Zauważmy, że w każdym kroku możemy pozwolić sobie na przejrzenie wszystkich wierzchołków osiągalnych z $i$-tego wierzchołka. Z konstrukcji drzewa wynika bowiem, że dla każdego wierzchołka-decyzji jedno z poddrzew jest jednowierzchołkowe (jest to wierzchołek-wartość), a drugie poddrzewo jest zaczepione w wierzchołku, którego indeks jest dwa razy mniejszy. Zatem liczba wierzchołków osiągalnych jest równa co najwyżej $O(\log n)$.

Tak więc całe rozwiązanie będzie miało złożoność czasową $O(n \log n)$:

const int N = 210000;
int n,a[N];
node* no[N];
bool is_fixed[N];

int main() {
  scanf("%d",&n);
  REP(i,n) {
    scanf("%d",&a[i]);
    no[i] = new node{ nullptr, nullptr, nullptr, a[i] };
  }
  REP(i,n-1) {
    node* le = no[i/2];
    node* ri = no[i+1];

    no[i/2] = new node{ le, ri, &is_fixed[i], -1 };
    no[i+1] = new node{ ri, le, &is_fixed[i], -1 };
  }

  REP(i,n) {
    int v = no[i]->minimum();
    no[i]->fix(v);
    
    printf("%d ",v);
  }
  printf("\n");
}