Mathematics

1. Candy Rush TL;DR - string hash accelerated comparison + big hash trick 2023-2024 ACM-ICPC Latin American Regional Programming Contest Official solution (a math. puzzle)：https://codeforces.com/gym/104736/attachments/download/22730/editorial.pdf After taking the frequency of occurrence of $C_i$ as a vector and doing a prefix sum, we can find that the frequency difference between valid intervals is $k \cdot 1_n$; the leveling complexity of the direct comparison is $O(nk\log{n})$, with $O(k)$ coming from the comparison itself...

Treap ATTENTION: Out the door and to the left. https://caterpillow.github.io/byot Thanks meow. AKA Cartesian Tree, Randomized BST; supports $log n$ insertion, deletion, lookup and closure operations (push_up) https://cp-algorithms.com/data_structures/treap.html https://oi.baoshuo.ren/fhq-treap A. std::set class containers template<typename T> struct treap { struct node { T key; ll priority; ll l, r; // push_up maintains ll size; }; vector<node> tree; vec free_list; private: void push_up(ll o) { tree[o].size = tree[tree[o].l].size + tree[tree[o].r].size + 1; } II split_by_value(ll o, T const& key) { // 偏序 [<, >=] if (!...