Stern-Brocot 树是一个包含着所有 ⊥ 的全部非负的分数 的二叉树结构其思想是从 0 阶 Stern-Brocot 序列 {01,10} 出发高阶 Stern-Brocot 序列由以下递归操作定义对于一个 阶 Stern-Brocot 序列在其任意两个相邻分数 与 ′′ 之间插入它们的中位分数′′ 后形成的序列即为 1 阶 Stern-Brocot 序列。例如1 阶是 {01,11,10}。2 阶是 {01,12,11,21,10}。3 阶是 {01,13,12,23,11,32,21,31,10}。容易看作二叉树的结构每个分数都是 ′′ 的形式其中 是左上方离它最近的祖先′′ 是右上方离它最近的祖先。oi-wiki 上的图较为形象大家可以看着理解下为什么树上的都是最简分数为什么不会重复出现某个分数为什么所有可能的非负的最简分数都会在树上出现容易发现这样一个性质如果 和 ′′ 在某一阶的 Stern-Brocot 序列中相邻那么必然满足′−′1证明考虑数学归纳法初始 0 阶时有 1⋅1−0⋅01若当前 阶 Stern-Brocot 序列中满足条件那么在 与 ′′ 中间插入的 ′′相当于要证明(′)−(′)1′(′)−(′)′1第一个直接拆开 ′−−′′−′1第二个同理于是得证。同时上面 ′−′1 这个式子也可以说明 ⊥,′⊥′那么可以得到树上的所有分数必然是最简分数。然后来考虑插入的分数的大小关系显然有′′′即一个中位分数在它原先两个值的中间于是树上必然没有重复的分数。好接下来要证所有正的最简分数 都在树上出现考虑反证法初始显然01′1′0然后假设当前阶段有′′考虑 ′′ 与 的大小关系若 ′′与命题矛盾退出。若 ′′令 ←′,′。否则 ′′令 ′←′,′←′。考虑证明这个过程不会无限进行下去因为{−0′′−0即{−0′−′0显然 −,′−′ 都是整数于是{−≥1′−′≥1然后必然有(′′)(−)()(′−′)≥′′前面把 和 专门提出来((′′)−′())(′()−(′′))然后它们的系数可以根据 ′−′1 化简成 1于是≥′′而上面每次操作中 ′′ 都会增加于是至多进行 次后就会退出即找到 于是证明了所有非负分数即正有理数都在树上可以将 Stern-Brocot 树看作一个有理数的数系。因为每个正最简分数只出现一次所以其与树上从根到它的路径是一一对应的即我们可以用字母 , 来表示当前节点是往左右哪个儿子去走一串 , 组成的序列就唯一的表示了一个位置例如 表示 11→12→23→34→57特别的对于 11 用 来表示。考虑这样一个问题给出一组 , 组成的字符串 求出其对应的分数是什么容易想到从初始 11 开始动态维护这个点是由左右哪两个节点合并的初始是 01,′1′0若 往左走那么左祖先不会变右祖先会变成当前节点即 ′←′,′←′。若 往右左同理那么右祖先不会变左祖先会变成当前节点即 ←′,←′。大家理解的时候可以看前面那个树的图来理解然后我们就可以写下如下代码解决inline pairint, int getLR(string s){int len s.size();int m 0, n 1, m_ 1, n_ 0;for(int i 0; i len; i){if(s[i] L)m_ m m_, n_ n n_;elsem m m_, n n n_;}return mkp(m m_, n n_);}当长度很长时即给定是 / 每次走几次也可以根据式子直接做inline pairint, int getLR(vectorpairchar, int s){int len s.size();int m 0, n 1, m_ 1, n_ 0;for(int i 0; i len; i){if(s[i].fi L)m_ s[i].se * m m_, n_ s[i].se * n n_;elsem m s[i].se * m_, n n s[i].se * n_;}return mkp(m m_, n n_);}这种还是太程序性了数学语言怎么表示容易想到矩阵即初始()(′′)这里为啥不用像分数那样上面分子下面分母呢主要是此时初始根节点的状态 ()(1001) 这是一个单位矩阵而用分数的表示形式的话不是单位矩阵要多乘一个矩阵形式上也不那么清晰。然后考虑()(′′)()(′′′′)那么可以推出 , 矩阵(1101)(1011)即()(),()()于是求 () 时可以看作是 中的 , 作矩阵乘法例如 ()(1101)(1011)(1011)(1101)(3423)。于是求 所对应的分数只需要经过矩阵运算得到()((′′))′′那么现在考虑给定一个分数 求其唯一对应 序列这个问题这就比较简单了根据生成规则我们知道 Stern-Brocot 树是一颗二叉搜索树即左子树的点都比它小右子树的点都比它大于是可以通过比较与当前位置的值来决定。那么可以写下如下代码inline string backLR(int m, int n){string ans ;Mat S;while(1){auto t f(S);if(t mkp(m, n))break;if(mkp(m, n) t){S S * L;ans.push_back(L);}else{S S * R;ans.push_back(R);}}return ans;}显然这个效率较为低下且要进行矩阵运算考虑怎么优化一下注意到(′′′)(′′′)那么()′′′()1()′′′1()1()1设 () 表示其对应的字符串那么我们可以看出若第一步为 则 1否则第一步为 则 1于是可以递归的去做()→−()()()(−)()()→−()()()(−)()那么可以写出如下代码inline string backLR(int m, int n){string ans ;while(m ! n){if(m n){ans.push_back(L);n n - m;}else{ans.push_back(R);m m - n;}}return ans;}你发现这特别像更像减损法于是可以用辗转相除法类似的思路去优化即inline vectorpairchar, int backLR(int m, int n){vectorpairchar, int ans;while(m n m ! n){if(m n){if(n % m 0)ans.push_back({L, n / m - 1});elseans.push_back({L, n / m});n n % m;}else{if(m % n 0)ans.push_back({R, m / n - 1});elseans.push_back({R, m / n});m m % n;}}return ans;}此时就可以做到 (log⁡) 复杂度去找对应的路径。然后对于一个分数 考虑其在树上一个子树 显然 是无限大的但是显然其有界在 (,) 之间那么怎么求出 ,,, 呢回到前面每次插入的中位分数在两个值之间的性质于是这只是换一个问法显然只是在问合并出 的是哪两个分数比较简单求出 的 串后模拟一下即可。对于树上问题容易想到 LCA那么考虑 Stern-Brocot 树上的两个点 ,怎么求出它们的 LCA容易发现找到 , 的 串 (),()它们 LCP 的长度就是它们 LCA 的深度而这个长度是容易求的然后它们的 LCA 就是这个 LCP 对应的节点套用上面函数一下即可。同理 的树上 级祖先也是可以算出 () 后删掉末尾的 个字符后套用前面函数得出。显然单次时间复杂度都是 (log⁡)总时间复杂度为 (log⁡)。link完整代码#includebits/stdc.h#define ls(k) k 1#define rs(k) k 1 | 1#define lowbit(x) x (-x)#define fi first#define se second#define popcnt(x) __builtin_popcount(x)#define open(s1, s2) freopen(s1, r, stdin), freopen(s2, w, stdout);#define mkp(x, y) make_pair(x, y)using namespace std;typedef __int128 __;typedef long double lb;typedef double db;typedef unsigned long long ull;typedef long long ll;bool Begin;inline ll read(){ll x 0, f 1;char c getchar();while(c 0 || c 9){if(c -)f -1;c getchar();}while(c 0 c 9){x (x 1) (x 3) (c ^ 48);c getchar();}return x * f;}inline void write(ll x){if(x 0){putchar(-);x -x;}if(x 9)write(x / 10);putchar(x % 10 0);}inline pairint, int getLR(vectorpairchar, int s){int len s.size();int m 0, n 1, m_ 1, n_ 0;for(int i 0; i len; i){if(s[i].fi L)m_ s[i].se * m m_, n_ s[i].se * n n_;elsem m s[i].se * m_, n n s[i].se * n_;}return mkp(m m_, n n_);}inline vectorpairchar, int backLR(int m, int n){vectorpairchar, int ans;while(m n m ! n){if(m n){if(n % m 0)ans.push_back({L, n / m - 1});elseans.push_back({L, n / m});n n % m;}else{if(m % n 0)ans.push_back({R, m / n - 1});elseans.push_back({R, m / n});m m % n;}}return ans;}inline pairint, int getkfa(int m, int n, int k){auto V backLR(m, n);int sum 0, len V.size();for(int i 0; i len; i)sum V[i].se;if(sum k)return mkp(-1, -1);vectorpairchar, int fa;for(int i 0; i len; i){if(!k)break;if(V[i].se k){fa.push_back(V[i]);k - V[i].se;}else{fa.push_back(mkp(V[i].fi, k));k 0;}}return getLR(fa);}inline pairpairint, int, pairint, int range(int p, int q){auto s backLR(p, q);int len s.size();int m 0, n 1, m_ 1, n_ 0;for(int i 0; i len; i){if(s[i].fi L)m_ s[i].se * m m_, n_ s[i].se * n n_;elsem m s[i].se * m_, n n s[i].se * n_;}return mkp(mkp(m, n), mkp(m_, n_));}inline pairint, int getlca(int a, int b, int c, int d){auto A backLR(a, b), B backLR(c, d);int s1 0, s2 0;for(auto v : A)s1 v.se;for(auto v : B)s2 v.se;if(s1 s2){swap(a, c), swap(b, d);swap(A, B);}vectorpairchar, int lca;int j 0;for(int i 0; i (int)A.size(); i){int s A[i].se;while(j (int)B.size() s){if(B[j].fi ! A[i].fi)break;if(B[j].se s){s - B[j].se;j;}else{B[j].se - s;s 0;}}if(j (int)B.size() || s){lca.push_back(mkp(A[i].fi, A[i].se - s));break;}lca.push_back(A[i]);}return getLR(lca);}int T, a, b, c, d, p, q, len, x, k;char C;char op[20];int main(){T read();while(T--){scanf(%s, op);if(op[0] E){p read(), q read();auto V backLR(p, q);write(V.size());putchar( );for(auto t : V){putchar(t.fi);putchar( );write(t.se);putchar( );}putchar(\n);}else if(op[0] D){vectorpairchar, int V;len read();while(len--){C getchar();x read();V.push_back({C, x});}auto t getLR(V);write(t.fi);putchar( );write(t.se);putchar(\n);}else if(op[0] L){a read(), b read(), c read(), d read();auto t getlca(a, b, c, d);write(t.fi);putchar( );write(t.se);putchar(\n);}else if(op[0] A){k read(), a read(), b read();auto t getkfa(a, b, k);if(t.fi 0){puts(-1);continue;}write(t.fi);putchar( );write(t.se);putchar(\n);}else{a read(), b read();auto t range(a, b);write(t.fi.fi);putchar( );write(t.fi.se);putchar( );write(t.se.fi);putchar( );write(t.se.se);putchar(\n);}}return 0;}UVA11350 Stern-Brocot Tree洛谷同步题解。模版这有使用getLR即可。linkP5179 Fraction洛谷同步题解。怎么题解区的 Stern-Brocot 树怎么都在递归去做来一篇 Stern-Brocot 树的依靠树性质的单 log 做法。思路首先看看 Stern-Brocot 树的图显然这是一颗二叉搜索树考虑 , 在树上的关系分讨一下令 LCA(,)。若 ≠ 且 ≠即 与 分别在 的左右儿子的子树中说明必然 考虑证明 就是最优答案显然的 子树内的分数 ′′ 必然满足 ′≥,′≥因为都是以 为基础合并出来的于是子树内满足条件的没有 优而子树外的显然不可能在 (,) 之间。否则 与 在一条链上这里只说 是其 LCA 的情况另一种对称类似即可显然 在 的左儿子 子树中那么直接选左儿子作为 行吗不行因为若 在 的右子树内那么就不满足条件了所以再分讨一下若 在 的左子树内那么 是最优的证明类似。否则 或者在 的右子树内怎么办容易想到考虑 的位置从 出发后一直往右跳直到 在当前点左子树中或者等于当前点若 等于当前点那么最优的是 的右儿子。否则 在当前点的左子树中那么最优的就是当前点。大家可以自己手摸感受一下。于是直接在应用 Stern-Brocot 树模版找到 LCA 与找对应路径等时间复杂度为 (log⁡)。