Algorithms Thread Episode 9: Treaps

Your last tutorial was very good (Algorithms thread : Tree basic), now i cann't wait for this one anymore. thank you.

I was sad at first because u didn't participated in today's contest as it was really an interesting one, but after watching this post, omg made my day :)

This is great! One possible improvement for your gym contests is sample explanations, consider creating those more often.

Unrelated, but I was kind of scared when you brought an axe infront of that nice little tree in your beautiful episode...In any case, learned a lot of new concepts from your fabulous video. Waiting for the custom gym.

The classic "Good Morning, Everyone" by SecondThread!!

imagine not using splay trees #SplayGang

been postponing even the thought of reading about treaps for god knows how many years xD

Now I can finally have a proper intro, thanks for the help!

Though it's my first participation, I am really excited with the episodes. Happy Halloween !

SecondThread, Afaik I remember, you said that when you create Treap on N numbers, you create N Nodes and then merge them. But when merge is done, it is assumed that all elements on the left treap is smaller than the numbers on the right Treap and merging is done only on the basis of priority. But if I were to make a Treap on unsorted array, then the inorder traversal of the array wont give a sorted representation of the array. Is there an inconsistency or have I miss understood something???

Good!

Why were half of the problems deleted D:

Is it possible to do "treap-beats?" More specifically, is it possible to do the segtree-beats operations, such as range-mod updates and range-sum queries, on a treap? (while still allowing for standard split/merge ops on a treap)

Could someone provide a hint for the "Grim Treaper" problem? Doing all types of queries is simple but maintaining the sum is actually tricky :D

There are a couple things that should be fixed in SecondThread's c++ treap template on his github:

1. There is a missing parentheses in the "rangeAdd" function
2. The value "data" isn't set in the constructor
3. Vectors are used everywhere. This slows down the code a lot (because of the huge vector overhead). Just changing the vectors to std::array helped reduce the runtime of my D solution by a couple of seconds.

Thanks!

I would like to know if the last problem (problem Z: trick or treap) could be solved using splay tree..., anyone could solve this problem using splay tree?. If its possible, I would really like to discuss about it after the contest end

Can anyone give some hints on B and Z? Thanks in advance!

UPD: solved B using string hashing.

UPD2: solved Z by maintaining parent nodes.

Did someone manage implement the C++ code from the GitHub, for some reason I get wrong answer on test case 8 on the first problem, and cannot see the test case in order to debug.

In Problem C, I got 15 TLE on test 15. My solution is treap with lazy-tags.
- Tags 1: flip each node on the subtree
- Tags 2: reverse the subtree
- Tags 3 = Tags 1 + Tags 2
- Tags 4/5: set each node = 0/1
Is that right? or how can I solve this problem?
last submission: 97961309

Auto comment: topic has been updated by SecondThread (previous revision, new revision, compare).

What is test case 19 on problem Z?

SecondThread Does it matter to split with the condition key < node.value or key <= node.value ?

I'm solving CF Education Round 15 F, If I use key < node.value, I am getting AC, If I use key <= node.value, I am getting TLE.

Any idea why would that happen?

Also does different ways insert function affect the running time a lot? I'm getting AC if I use

void insert(pitem &t, pitem it){
    pitem l, r;
    split(t, l, r, it->value);
    merge(t, l, it);
    merge(t, t, r);
}

But TLE if I use

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

I'm not understanding why? Can you please help me?