C++

Preface References mainly from https://cp-algorithms.com/algebra/fft.html, https://en.wikipedia.org/wiki/Discrete_Fourier_transform, https://oi.wiki/math/ poly/fft/ to take care of a certain OJ this article routines (except miscellaneous) C++ standard only needs 11; board portal,topic portal define The $DFT$ of a polynomial $A$ is the value of $A$ in each unit root $w_{n, k} = w_n^k = e^{\frac{2 k \pi i}{n}}$ $$ \begin{align} \text{DFT}(a_0, a_1, \dots, a_{n-1}) &= (y_0, y_1, \dots, y_{n-1}) \newline &= (A(w_{n, 0}), A(w_{n, 1}), \dots, A(w_{n, n-1})) \newline &= (A(w_n^0), A(w_n^1), \dots, A(w_n^{n-1})) \end{align} $$...

Note: segment_tree are accessed using 1-Index; vector is 0-Index in segment_tree::reset(vector&). 242E. XOR on Segment Interval binary change + lazy pass + binary trick You’ve got an array $a$, consisting of $n$ integers $a_1, a_2, …, a_n$. You are allowed to perform two operations on this array: Calculate the sum of current array elements on the segment $[l,r]$, that is, count value $a_l + a_{l+1} + … + a_{r}$ Apply the xor operation with a given number x to each array element on the segment $[l,r]$, that is, execute $a_l = a_l \oplus x, a_{l+1} = a_{l+1} \oplus x,…,a_r = a_r \oplus x$ This operation changes exactly $r - l + 1$ array elements....

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

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

Preface Reference primarily from [Introductory Classics for Algorithmic Competition: A Training Guide (https://cread.jd.com/read/startRead.action?bookId=30133704&readType=1)、OIWiki、CP Algorithms and other resources and multiple blogs and courses, authored under their own code breeze Note: Some implementations may use newer language features, so please modify them for use on older OJs; In principle, the code provided is compatible with compilers that comply with the Cpp20 standard and above. Header #include "bits/stdc++.h" using namespace std; #define PRED(T,X) [&](T const& lhs, T const& rhs) {return X;} typedef long long ll; typedef unsigned long long ull; typedef double lf; typedef long double llf; typedef __int128 i128; typedef unsigned __int128 ui128; typedef pair<ll, ll> II; typedef vector<ll> vec; template<size_t size> using arr = array<ll, size>; const static void fast_io() { ios_base::sync_with_stdio(false); cin....

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