Агуулгыг алгасах

Трип (Декартын мод)

Трип гэдэг нь хоёртын мод ба хоёртын овоолгыг хослуулсан өгөгдлийн бүтэц юм (эндээс нэр нь гаралтай: tree + heap $\Rightarrow$ Treap).

Тодруулбал, трип нь $(X, Y)$ хосуудыг хоёртын модонд $X$-ээр нь хоёртын хайлтын мод, $Y$-ээр нь хоёртын овоолго байхаар хадгалдаг өгөгдлийн бүтэц юм. Хэрэв модны ямар нэг зангилаа $(X_0, Y_0)$ утгуудыг агуулж байвал зүүн дэд модны бүх зангилаа $X \leq X_0$, баруун дэд модны бүх зангилаа $X_0 \leq X$, зүүн ба баруун дэд модны бүх зангилаа $Y \leq Y_0$ байна.

Трипийг Декартын хавтгайд байрлуулахад амархан байдаг тул үүнийг "Декартын мод" гэж бас олонтаа нэрлэдэг:

Трипийг Raimund Siedel ба Cecilia Aragon нар 1989 онд санал болгосон.

Ийнхүү өгөгдлийг зохион байгуулахын давуу тал

Ийм хэрэгжүүлэлтэд $X$ утгууд нь түлхүүрүүд (мөн зэрэг трипэд хадгалагдаж буй утгууд) байх ба $Y$ утгуудыг тэргүүлэх эрх гэж нэрлэнэ. Тэргүүлэх эрхгүй бол трип нь $X$-ээр эрэмбэлэгдсэн ердийн хоёртын хайлтын мод болох ба нэг багц $X$ утгад олон өөр мод харгалзаж болох бөгөөд тэдгээрийн зарим нь degenerate (жишээ нь холбоост жагсаалт хэлбэртэй) буюу маш удаан (үндсэн үйлдлүүд нь $O(N)$ complexity-тэй) байх болно.

Үүний зэрэгцээ тэргүүлэх эрхүүд (давхардаагүй үед) байгуулагдах модыг цор ганц байдлаар тодорхойлох боломж олгодог бөгөөд (мэдээж энэ нь утгуудыг нэмсэн дарааллаас хамаарахгүй) үүнийг харгалзах теоремоор баталж болно. Хэрэв та тэргүүлэх эрхийг санамсаргүйгээр сонговол дунджаар degenerate биш мод авах нь илэрхий бөгөөд энэ нь үндсэн үйлдлүүдийн $O(\log N)$ complexity-г баталгаажуулна. Эндээс энэ өгөгдлийн бүтцийн өөр нэг нэр гарч ирнэ — санамсаргүй хоёртын хайлтын мод.

Үйлдлүүд

Трип дараах үйлдлүүдийг өгнө:

  • Insert (X,Y) — $O(\log N)$.
    Модонд шинэ зангилаа нэмнэ. Нэг боломжит хувилбар бол зөвхөн $X$-г дамжуулж, $Y$-г үйлдлийн дотор санамсаргүйгээр үүсгэх юм.
  • Search (X) — $O(\log N)$.
    Заасан $X$ түлхүүрийн утгатай зангилааг хайна. Хэрэгжүүлэлт нь ердийн хоёртын хайлтын модныхтой ижил.
  • Erase (X) — $O(\log N)$.
    Заасан $X$ түлхүүрийн утгатай зангилааг хайж, түүнийг модноос устгана.
  • Build ($X_1$, ..., $X_N$) — $O(N)$.
    Утгуудын жагсаалтаас мод байгуулна. Үүнийг шугаман хугацаанд хийж болно ($X_1, ..., X_N$ эрэмбэлэгдсэн гэж үзвэл).
  • Union ($T_1$, $T_2$) — $O(M \log (N/M))$.
    Бүх элемент ялгаатай гэж үзээд хоёр модыг нэгтгэнэ. Хэрэв нэгтгэх явцад давхардсан элементүүдийг устгах шаардлагатай бол мөн ижил complexity-д хүрэх боломжтой.
  • Intersect ($T_1$, $T_2$) — $O(M \log (N/M))$.
    Хоёр модны огтлолцлыг (буюу тэдгээрийн нийтлэг элементүүдийг) олно. Бид энэ үйлдлийн хэрэгжүүлэлтийг энд авч үзэхгүй.

Түүнчлэн трип нь хоёртын хайлтын мод учраас $K$ дахь хамгийн их элементийг олох, элементийн индексийг олох зэрэг бусад үйлдлийг хэрэгжүүлж чадна.

Хэрэгжүүлэлтийн тайлбар

Хэрэгжүүлэлтийн хувьд зангилаа бүр $X$, $Y$ ба зүүн ($L$), баруун ($R$) хүүхдүүд рүү заасан заагчуудыг агуулна.

Бид шаардлагатай бүх үйлдлийг ердөө хоёр туслах үйлдэл ашиглан хэрэгжүүлнэ: Split ба Merge.

Split

Split ($T$, $X$) нь $T$ модыг $L$ ба $R$ гэсэн 2 дэд мод болгон салгах ба (эдгээр нь split-ийн буцаах утгууд) $L$ нь $X_L \le X$ түлхүүртэй бүх элементийг, $R$ нь $X_R > X$ түлхүүртэй бүх элементийг агуулна. Энэ үйлдэл $O (\log N)$ complexity-тэй бөгөөд цэвэр рекурс ашиглан хэрэгжүүлэгдэнэ:

  1. Хэрэв үндэс зангилааны (R) утга $\le X$ бол L нь наад зах нь R->L ба R-ээс бүрдэнэ. Дараа нь бид R->R дээр split дуудаж, түүний split-ийн үр дүнг L' ба R' гэж тэмдэглэнэ. Эцэст нь L нь L'-г ч мөн агуулах ба R = R' болно.
  2. Хэрэв үндэс зангилааны (R) утга $> X$ бол R нь наад зах нь R ба R->R-ээс бүрдэнэ. Дараа нь бид R->L дээр split дуудаж, түүний split-ийн үр дүнг L' ба R' гэж тэмдэглэнэ. Эцэст нь L=L' болох ба R нь R'-г ч мөн агуулна.

Тиймээс split алгоритм нь:

  1. үндэс зангилаа аль дэд модонд харьяалагдахыг шийднэ (зүүн эсвэл баруун)
  2. түүний хүүхдүүдийн нэг дээр split-г рекурсивээр дуудна
  3. рекурсив split дуудалтыг дахин ашиглан эцсийн үр дүнг үүсгэнэ.

Merge

Merge ($T_1$, $T_2$) нь $T_1$ ба $T_2$ гэсэн хоёр дэд модыг нэгтгэж шинэ модыг буцаана. Энэ үйлдэл мөн $O (\log N)$ complexity-тэй. Энэ нь $T_1$ ба $T_2$ эрэмбэлэгдсэн ($T_1$ дэх бүх $X$ түлхүүр $T_2$ дэх түлхүүрүүдээс бага) гэсэн таамаглал дор ажиллана. Тиймээс бид эдгээр модыг $Y$ тэргүүлэх эрхийн дарааллыг зөрчихгүйгээр нэгтгэх хэрэгтэй. Үүний тулд бид үндэс зангилаандаа илүү өндөр $Y$ тэргүүлэх эрхтэй модыг үндэс болгон сонгож, нөгөө мод ба сонгосон үндэс зангилааны харгалзах дэд модны хувьд Merge-г рекурсивээр дуудна.

Insert

Одоо Insert ($X$, $Y$)-ийн хэрэгжүүлэлт илэрхий болно. Эхлээд бид модоор доош бууж (X-ээр эрэмбэлэгдсэн ердийн хоёртын хайлтын мод дахьтай адил), тэргүүлэх эрхийн утга нь $Y$-ээс бага байх эхний зангилаанд зогсоно. Бид шинэ элементийг оруулах байрыг оллоо. Дараа нь бид олдсон зангилаанаас эхлэх дэд мод дээр Split (T, X)-г дуудаж, буцаагдсан $L$ ба $R$ дэд модуудыг шинэ зангилааны зүүн ба баруун хүүхэд болгон ашиглана.

Өөр хувилбараар insert-г анхны трипийг $X$-ээр хувааж, шинэ зангилаатай $2$ merge хийх замаар гүйцэтгэж болно (зургийг үз).

Erase

Erase ($X$)-ийн хэрэгжүүлэлт мөн ойлгомжтой. Эхлээд бид модоор доош бууж ($X$-ээр эрэмбэлэгдсэн ердийн хоёртын хайлтын мод дахьтай адил), устгахыг хүсэж буй элементээ хайна. Зангилаа олдмогц бид түүний хүүхдүүд дээр Merge-г дуудаж, үйлдлийн буцаах утгыг устгаж буй элементийн байранд тавина.

Өөр хувилбараар бид $X$-г агуулах дэд модыг $2$ split үйлдлээр салган гаргаж, үлдсэн трипүүдийг нэгтгэж болно (зургийг үз).

Build

Бид Build үйлдлийг $N$ ширхэг Insert дуудалт ашиглан $O (N \log N)$ complexity-тэйгээр хэрэгжүүлнэ.

Union

Union ($T_1$, $T_2$) нь онолын хувьд $O (M \log (N / M))$ complexity-тэй боловч практикт маш сайн ажилладаг бөгөөд нуугдмал тогтмол нь маш бага байх магадлалтай. Ерөнхий чанараа алдалгүйгээр $T_1 \rightarrow Y > T_2 \rightarrow Y$ гэж үзье, өөрөөр хэлбэл $T_1$-ийн үндэс нь үр дүнгийн үндэс болно. Үр дүнг авахын тулд бид $T_1 \rightarrow L$, $T_1 \rightarrow R$ ба $T_2$ модуудыг $T_1$-ийн үндсийн хүүхдүүд байж болох хоёр мод болгон нэгтгэх хэрэгтэй. Үүний тулд бид Split ($T_2$, $T_1\rightarrow X$)-г дуудаж, $T_2$-г L ба R гэсэн хоёр хэсэгт хуваана. Дараа нь тэдгээрийг $T_1$-ийн хүүхдүүдтэй рекурсивээр нэгтгэнэ: Union ($T_1 \rightarrow L$, $L$) ба Union ($T_1 \rightarrow R$, $R$), ингэснээр үр дүнгийн зүүн ба баруун дэд модыг авна.

Implementation

struct item {
    int key, prior;
    item *l, *r;
    item () { }
    item (int key) : key(key), prior(rand()), l(NULL), r(NULL) { }
    item (int key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
};
typedef item* pitem;

This is our item definition. Note there are two child pointers, and an integer key (for the BST) and an integer priority (for the heap). The priority is assigned using a random number generator.

void split (pitem t, int key, pitem & l, pitem & r) {
    if (!t)
        l = r = NULL;
    else if (t->key <= key)
        split (t->r, key, t->r, r),  l = t;
    else
        split (t->l, key, l, t->l),  r = t;
}

t is the treap to split, and key is the BST value by which to split. Note that we do not return the result values anywhere, instead, we just use them like so:

pitem l = nullptr, r = nullptr;
split(t, 5, l, r);
if (l) cout << "Left subtree size: " << (l->size) << endl;
if (r) cout << "Right subtree size: " << (r->size) << endl;

This split function can be tricky to understand, as it has both pointers (pitem) as well as reference to those pointers (pitem &l). Let us understand in words what the function call split(t, k, l, r) intends: "split treap t by value k into two treaps, and store the left treaps in l and right treap in r". Great! Now, let us apply this definition to the two recursive calls, using the case work we analyzed in the previous section: (The first if condition is a trivial base case for an empty treap)

  1. When the root node value is $\le$ key, we call split (t->r, key, t->r, r), which means: "split treap t->r (right subtree of t) by value key and store the left subtree in t->r and right subtree in r". After that, we set l = t. Note now that the l result value contains t->l, t as well as t->r (which is the result of the recursive call we made) all already merged in the correct order! You should pause to ensure that this result of l and r corresponds exactly with what we discussed earlier in Implementation Description.
  2. When the root node value is greater than key, we call split (t->l, key, l, t->l), which means: "split treap t->l (left subtree of t) by value key and store the left subtree in l and right subtree in t->l". After that, we set r = t. Note now that the r result value contains t->l (which is the result of the recursive call we made), t as well as t->r, all already merged in the correct order! You should pause to ensure that this result of l and r corresponds exactly with what we discussed earlier in Implementation Description.

If you're still having trouble understanding the implementation, you should look at it inductively, that is: do not try to break down the recursive calls over and over again. Assume the split implementation works correct on empty treap, then try to run it for a single node treap, then a two node treap, and so on, each time reusing your knowledge that split on smaller treaps works.

void insert (pitem & t, pitem it) {
    if (!t)
        t = it;
    else if (it->prior > t->prior)
        split (t, it->key, it->l, it->r),  t = it;
    else
        insert (t->key <= it->key ? t->r : t->l, it);
}

void merge (pitem & t, pitem l, pitem r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
}

void erase (pitem & t, int key) {
    if (t->key == key) {
        pitem th = t;
        merge (t, t->l, t->r);
        delete th;
    }
    else
        erase (key < t->key ? t->l : t->r, key);
}

pitem unite (pitem l, pitem r) {
    if (!l || !r)  return l ? l : r;
    if (l->prior < r->prior)  swap (l, r);
    pitem lt, rt;
    split (r, l->key, lt, rt);
    l->l = unite (l->l, lt);
    l->r = unite (l->r, rt);
    return l;
}

Maintaining the sizes of subtrees

To extend the functionality of the treap, it is often necessary to store the number of nodes in subtree of each node - field int cnt in the item structure. For example, it can be used to find K-th largest element of tree in $O (\log N)$, or to find the index of the element in the sorted list with the same complexity. The implementation of these operations will be the same as for the regular binary search tree.

When a tree changes (nodes are added or removed etc.), cnt of some nodes should be updated accordingly. We'll create two functions: cnt() will return the current value of cnt or 0 if the node does not exist, and upd_cnt() will update the value of cnt for this node assuming that for its children L and R the values of cnt have already been updated. Evidently it's sufficient to add calls of upd_cnt() to the end of insert, erase, split and merge to keep cnt values up-to-date.

int cnt (pitem t) {
    return t ? t->cnt : 0;
}

void upd_cnt (pitem t) {
    if (t)
        t->cnt = 1 + cnt(t->l) + cnt (t->r);
}

Трипийг офлайн горимд $O (N)$-д байгуулах

Эрэмбэлэгдсэн түлхүүрүүдийн жагсаалт өгөгдсөн бол трипийг түлхүүрүүдийг нэг нэгээр нь оруулахаас (энэ нь $O(N \log N)$ хугацаа авна) илүү хурдан байгуулах боломжтой. Түлхүүрүүд эрэмбэлэгдсэн тул тэнцвэржүүлсэн хоёртын хайлтын модыг шугаман хугацаанд амархан байгуулж болно. Овоолгын $Y$ утгуудыг санамсаргүйгээр эхлүүлэх ба дараа нь $X$ түлхүүрүүдээс хамааралгүйгээр овоолго байгуулах хэлбэрээр $O(N)$-д овоолгожуулж болно.

void heapify (pitem t) {
    if (!t) return;
    pitem max = t;
    if (t->l != NULL && t->l->prior > max->prior)
        max = t->l;
    if (t->r != NULL && t->r->prior > max->prior)
        max = t->r;
    if (max != t) {
        swap (t->prior, max->prior);
        heapify (max);
    }
}

pitem build (int * a, int n) {
    // Construct a treap on values {a[0], a[1], ..., a[n - 1]}
    if (n == 0) return NULL;
    int mid = n / 2;
    pitem t = new item (a[mid], rand ());
    t->l = build (a, mid);
    t->r = build (a + mid + 1, n - mid - 1);
    heapify (t);
    upd_cnt(t)
    return t;
}

Тэмдэглэл: upd_cnt(t)-г дуудах нь зөвхөн дэд модны хэмжээ хэрэгтэй үед л шаардлагатай.

Дээрх арга нь үргэлж төгс тэнцвэржсэн мод өгөх бөгөөд практик зорилгод ерөнхийдөө сайн боловч зангилаа бүрд анх оноогдсон тэргүүлэх эрхийг хадгалахгүй байх нь түүний зардал юм. Тиймээс энэ арга нь дараах бодлогыг бодоход тохиромжгүй:

acmsguru - Cartesian Tree

$(x_i, y_i)$ хосуудын дараалал өгөгдсөн байг, тэдгээр дээр Декартын мод байгуул. Бүх $x_i$ ба бүх $y_i$ давхардаагүй.

Энэ бодлогод тэргүүлэх эрхүүд санамсаргүй биш тул оройнуудыг зүгээр нэг нэгээр нь оруулах нь квадрат шийдэл өгч болзошгүйг анзаар.

Эндэх боломжит шийдлүүдийн нэг бол элемент бүрийн хувьд түүнээс бага тэргүүлэх эрхтэй, зүүн ба баруун талын хамгийн ойрын элементүүдийг олох явдал юм. Эдгээр хоёр элементээс илүү өндөр тэргүүлэх эрхтэй нь одоогийн элементийн эцэг байх ёстой.

Энэ бодлогыг минимум стек-ийн өөрчлөлт ашиглан шугаман хугацаанд бодож болно:

void connect(auto from, auto to) {
    vector<pitem> st;
    for(auto it: ranges::subrange(from, to)) {
        while(!st.empty() && st.back()->prior > it->prior) {
            st.pop_back();
        }
        if(!st.empty()) {
            if(!it->p || it->p->prior < st.back()->prior) {
                it->p = st.back();
            }
        }
        st.push_back(it);
    }
}

pitem build(int *x, int *y, int n) {
    vector<pitem> nodes(n);
    for(int i = 0; i < n; i++) {
        nodes[i] = new item(x[i], y[i]);
    }
    connect(nodes.begin(), nodes.end());
    connect(nodes.rbegin(), nodes.rend());
    for(int i = 0; i < n; i++) {
        if(nodes[i]->p) {
            if(nodes[i]->p->key < nodes[i]->key) {
                nodes[i]->p->r = nodes[i];
            } else {
                nodes[i]->p->l = nodes[i];
            }
        }
    }
    return nodes[min_element(y, y + n) - y];
}

Далд трип

Далд трип гэдэг нь ердийн трипийн энгийн өөрчлөлт бөгөөд маш хүчирхэг өгөгдлийн бүтэц юм. Үнэндээ далд трипийг дараах процедуруудыг хэрэгжүүлсэн массив гэж үзэж болно (бүгд онлайн горимд $O (\log N)$):

  • Массивын дурын байрлалд элемент оруулах
  • Дурын элементийг устгах
  • Дурын интервал дээрх нийлбэр, хамгийн бага / хамгийн их элемент гэх мэтийг олох
  • Дурын интервал дээр нэмэх, будах
  • Дурын интервал дээрх элементүүдийг эргүүлэх

Санаа нь түлхүүрүүд нь массив дахь элементүүдийн тэгээс эхлэх индекс байх ёстой гэсэн үг. Гэвч бид эдгээр утгыг ил хадгалахгүй (эс тэгвээс жишээ нь элемент оруулах нь модны $O (N)$ зангилааны түлхүүрийг өөрчлөхөд хүргэнэ).

Зангилааны түлхүүр нь түүнээс бага зангилааны тоо болохыг анзаар (ийм зангилаанууд зөвхөн түүний зүүн дэд модонд байх албагүй бөгөөд түүний өвөгүүдийн зүүн дэд модуудад ч байж болно). Тодруулбал, ямар нэг T зангилааны далд түлхүүр нь энэ зангилааны зүүн дэд мод дахь оройнуудын тоо $cnt (T \rightarrow L)$ дээр T зангилааны өвөг P бүрийн хувьд, хэрэв T нь P-ийн баруун дэд модонд байвал, ижил төстэй $cnt (P \rightarrow L) + 1$ утгуудыг нэмсэнтэй тэнцүү.

Одоо одоогийн зангилааны далд түлхүүрийг хэрхэн хурдан тооцоолохыг ойлгоход амархан. Бид бүх үйлдэлд аль ч зангилаанд модоор доош буун ирдэг тул энэ нийлбэрийг хуримтлуулаад функцэд дамжуулж болно. Хэрэв бид зүүн дэд мод руу явбал хуримтлагдсан нийлбэр өөрчлөгдөхгүй, харин баруун дэд мод руу явбал $cnt (T \rightarrow L) +1$-ээр нэмэгдэнэ.

Split ба Merge-ийн шинэ хэрэгжүүлэлтүүд энд байна:

void merge (pitem & t, pitem l, pitem r) {
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
    upd_cnt (t);
}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
    if (!t)
        return void( l = r = 0 );
    int cur_key = add + cnt(t->l); //implicit key
    if (key <= cur_key)
        split (t->l, l, t->l, key, add),  r = t;
    else
        split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
    upd_cnt (t);
}

Дээрх хэрэгжүүлэлтэд $split(T, T_1, T_2, k)$-г дуудсаны дараа $T_1$ мод нь $T$-ийн эхний $k$ элементээс (өөрөөр хэлбэл далд түлхүүр нь $k$-аас бага элементүүдээс), $T_2$ нь бусад бүхнээс бүрдэнэ.

Одоо далд трип дээрх янз бүрийн үйлдлийн хэрэгжүүлэлтийг авч үзье:

  • Элемент оруулах.
    Бид $pos$ байрлалд элемент оруулах хэрэгтэй гэж бодъё. Бид трипийг $[0..pos-1]$ ба $[pos..sz]$ массивуудад харгалзах хоёр хэсэгт хуваана; үүний тулд бид $split(T, T_1, T_2, pos)$-г дуудна. Дараа нь бид $merge(T_1, T_1, \text{new item})$-г дуудаж $T_1$ модыг шинэ оройтой нэгтгэж болно (бүх урьдчилсан нөхцөл хангагдсаныг харахад амархан). Эцэст нь бид $merge(T, T_1, T_2)$-г дуудаж $T_1$ ба $T_2$ модуудыг $T$ болгон буцаан нэгтгэнэ.
  • Элемент устгах.
    Энэ үйлдэл бүр ч хялбар: устгах $T$ элементийг олж, түүний $L$ ба $R$ хүүхдүүдийн merge-г гүйцэтгэн, $T$ элементийг merge-ийн үр дүнгээр солино. Үнэндээ далд трип дэх элемент устгах нь ердийн трип дэхтэй яг ижил.
  • Интервал дээрх нийлбэр / минимум гэх мэтийг олох.
    Эхлээд item бүтцэд энэ зангилааны дэд модны хувьд зорилтот функцийн утгыг хадгалах $F$ нэмэлт талбар үүсгэнэ. Энэ талбарыг дэд модны хэмжээг хадгалахтай адилаар хялбар засварлаж болно: хүүхдүүдийнх нь утгууд дээр үндэслэн зангилааны хувьд энэ утгыг тооцоолох функц үүсгээд, модыг өөрчилдөг бүх функцийн төгсгөлд энэ функцийн дуудалтыг нэмнэ.
    Хоёрдугаарт, бид дурын $[A; B]$ интервалын хувьд асуулгыг хэрхэн боловсруулахыг мэдэх хэрэгтэй.
    $[A; B]$ интервалд харгалзах модны хэсгийг авахын тулд бид $split(T, T_2, T_3, B+1)$, дараа нь $split(T_2, T_1, T_2, A)$-г дуудах хэрэгтэй: үүний дараа $T_2$ нь $[A; B]$ интервал дахь бүх элементээс, зөвхөн тэдгээрээс бүрдэнэ. Тиймээс асуулгын хариу $T_2$-ийн үндсийн $F$ талбарт хадгалагдана. Асуулгад хариулсны дараа модыг $merge(T, T_1, T_2)$ ба $merge(T, T, T_3)$-г дуудаж сэргээх ёстой.
  • Интервал дээр нэмэх / будах.
    Бид өмнөх догол мөртэй адилаар үйлдэнэ, гэхдээ F талбарын оронд дэд модонд нэмэгдсэн утгыг (эсвэл дэд модыг будсан утгыг) агуулах add талбар хадгална. Ямар нэг үйлдэл гүйцэтгэхээсээ өмнө бид энэ утгыг зөв "түлхэх" ёстой — өөрөөр хэлбэл $T \rightarrow L \rightarrow add$ ба $T \rightarrow R \rightarrow add$-г өөрчилж, эцэг зангилаан дахь add-г цэвэрлэх ёстой. Ингэснээр модонд ямар ч өөрчлөлт орсны дараа мэдээлэл алдагдахгүй.
  • Интервал дээр эргүүлэх.
    Энэ нь дахин өмнөх үйлдэлтэй төстэй: бид rev boolean тугийг нэмж, одоогийн зангилааны дэд модыг эргүүлэх шаардлагатай үед түүнийг true болгож тохируулах ёстой. Энэ утгыг "түлхэх" нь жаахан төвөгтэй — бид энэ зангилааны хүүхдүүдийг солиод, тэдгээрийн хувьд энэ тугийг true болгоно.

Интервал дээр эргүүлэх үйлдэл бүхий далд трипийн жишээ хэрэгжүүлэлт энд байна. Зангилаа бүрийн хувьд бид одоогийн байрлал дахь массивын элементийн бодит утга болох value талбарыг хадгална. Мөн бид далд трипийн одоогийн төлөвт харгалзах массивыг хэвлэх output() функцийн хэрэгжүүлэлтийг өгнө.

typedef struct item * pitem;
struct item {
    int prior, value, cnt;
    bool rev;
    pitem l, r;
};

int cnt (pitem it) {
    return it ? it->cnt : 0;
}

void upd_cnt (pitem it) {
    if (it)
        it->cnt = cnt(it->l) + cnt(it->r) + 1;
}

void push (pitem it) {
    if (it && it->rev) {
        it->rev = false;
        swap (it->l, it->r);
        if (it->l)  it->l->rev ^= true;
        if (it->r)  it->r->rev ^= true;
    }
}

void merge (pitem & t, pitem l, pitem r) {
    push (l);
    push (r);
    if (!l || !r)
        t = l ? l : r;
    else if (l->prior > r->prior)
        merge (l->r, l->r, r),  t = l;
    else
        merge (r->l, l, r->l),  t = r;
    upd_cnt (t);
}

void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
    if (!t)
        return void( l = r = 0 );
    push (t);
    int cur_key = add + cnt(t->l);
    if (key <= cur_key)
        split (t->l, l, t->l, key, add),  r = t;
    else
        split (t->r, t->r, r, key, add + 1 + cnt(t->l)),  l = t;
    upd_cnt (t);
}

void reverse (pitem t, int l, int r) {
    pitem t1, t2, t3;
    split (t, t1, t2, l);
    split (t2, t2, t3, r-l+1);
    t2->rev ^= true;
    merge (t, t1, t2);
    merge (t, t, t3);
}

void output (pitem t) {
    if (!t)  return;
    push (t);
    output (t->l);
    printf ("%d ", t->value);
    output (t->r);
}

Ном зүй

Дасгал бодлогууд