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$. 引理： $gcd(x,y) = gcd(x,y-x)$ 引理： 可以拓展到 **数组 $gcd$数值上等于数组差分 $gcd$ **；证明显然，略 注意该命题在数组及其差分上取子数组时上并不成立，如 991F. Typora怎么快速加页面内链接… 记$g_{pfx} = gcd(a_2-a_1,a_3-a_2,…a_n-a_{n-1})$ 于本题利用$gcd(a_1+b_1,a_2+b_1,…a_n+b_1) = gcd(a_1+b1,a_2-a_1,a_3-a_2,…a_n-a_{n-1}) = gcd(a_1 + b_1, g_{pfx})$即可 int main() { fast_io(); /* El Psy Kongroo */ ll n,m; cin >> n >> m; vector<ll> a(n); for (ll& x: a) cin >> x; // gcd(a_1+b_1,a_2+b_1,....

Treap ATTENTION: 出门左转 https://caterpillow.github.io/byot 谢谢喵 又名笛卡尔树，随机BST；支持$log n$插入，删除，查找及闭包操作(push_up) https://cp-algorithms.com/data_structures/treap.html https://oi.baoshuo.ren/fhq-treap A. std::set 类容器 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 (!o) return {0,0}; if (tree[o].key < key) { // 左大右小 auto [ll,rr] = split_by_value(tree[o]....