GCD

691C. Row GCD You are given two positive integer sequences $a_1, \ldots, a_n$ and $b_1, \ldots, b_m$. For each $j = 1, \ldots, m$ find the greatest common divisor of $a_1 + b_j, \ldots, a_n + b_j$. Lemma: $gcd(x,y) = gcd(x,y-x)$ ** Lemma: ** can be extended to ** the array $gcd$ is numerically equal to the array difference $gcd$ **; the proof is obvious, omitted Note that the proposition does not hold on arrays and subarrays taken on their differences, as in 991F....

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 (!...