Hallo codeforcers,
As some of you may know, the almighty treap is one of the most versatile data structures out there. It can serve as an ordered + indexed set, a lazy segment tree, and even a dynamic array — all at the same time.
However, its immense versatility comes at a cost: there are so many different variations that making a one-template-fits-all is impossible. Alas, is fate such that we must write it from scratch — every, single, time?
Fear no more! I present to you BYOT: Build your own treap!
Now, you can summon a hand-crafted treap to overkill your Div2D in mere seconds. Gone are the days of using your brain to come up with a clever solution — just go to the site, click on what you need, and enjoy your AC! To see how it is used, you can see some example implementations below.
If you find any bugged configurations or have any suggestions, please leave a comment under this blog. Be warned, no rating refunds will be issued if something breaks on you during contest.
Supported features
Example problems + solutions
Now, I understand if there are still some doubts. To prove the effectiveness of this tool, I have implemented solutions to all of SecondThread's Algorithms Thread Treaps Contest (+ one more problem) using the website! Below, I have linked solutions, where you can see which pieces of code were written by me, which bits came from the site, and what configuration of settings I used.
102787A - Shandom Ruffle — Solution
Basic implicit treap with split and merge, with $$$O(n)$$$ build and tour. No modifications were made to the code after being copied from the site.
102787B - Pear TreaP — Solution
Basic implicit treap with split, merge, insert and range queries (by index). I use two rolling hashes to check for palindromes, which is implemented very simply with only a few lines + modular power.
102787C - Sneetches and Speeches 3 — Solution
Implicit treap with split, merge, range updates and queries (by index), and range reversals. The code is rather bashy, but the body of the treap was left untouched.
102787D - The Grim Treaper — Solution
This problem requires range chmin, range add and range sums — a problem classically solved using segtree beats. However, the cut and paste operation requires you to use a treap. Fortunately, the site supports these operations, so no modifications were made to the generated code. You can see all the operations in action on this submission to Range Chmin Chmax Add Range Sum on https://judge.yosupo.jp/.
102787Z - Trick or Treap — Solution
This problem requires parent pointers and range sums, as well as basic split and merge functionality. This did not require any modifications to the code generated by the site.
Bonus
Since these problems did not feature anything that required the usage of keys, I have a bonus solution (that has been rewritten) to a recent Div2 where I used the site to quickly implement a thoughtless solution in contest.
2042D - Recommendations — 294603712
If you consider a user (l, r) as a point on a plane, the range of "strongly recommended tracks" is simply the intersection of all the users in a rectangle. By answering queries offline and sweeping through one axis (such as leftmost track), we can turn these rectangle queries into range queries.
The usual solution here would be to do coordinate compression + segtree or lazy-create/sparse segtree, but instead I used (you guessed it) a treap!
Here, I sweep through increasing leftmost track, maintaining a treap of previous users. The users in the treap are ordered by their key (the rightmost track some user likes) and I perform range queries and insertions on it. With byot, this data structure can be implemented by modifying only 3 lines of code.
Instead of writing a clever solution, I simply brute forced the range of strongly recommended tracks by abusing OP data structures.
