Collection/compilation

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

Preface After the v2 facial model update the game finally introduces SDF facial shadows; the implementation is pretty much the same as most of the existing solutions on the market. This article shares one of my own ideas for correctly achieving this effect in Blender Note: Due to personal limitations errors are inevitable, It is highly recommended to read the following text as a preparatory knowledge: Secondary Character Cartoon Rendering - Face by MIZI Cartoon Rendering - 360 Degree Face SDF Lighting Scheme by Yu-ki016 Signed Distance Field by 欧克欧克 1....

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

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

Preface The following Code is a direct port of Cpp version; please consider the former as the upstream and first reference source Python implementation, generally preferring to consider dynamic memory opening and hashing lookups (e.g. defaultdict instead of linear storage) Code section is not categorized, please make good use of Cpp version + Ctrl-F. Header from collections import defaultdict graph theory receiver gauge class graph(defaultdict): def __init__(self): super().__init__(list) def add_edge(self, u, v): self[u]....

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