Home
Problem
Status
Contest
Workbook
User
Group
Forum
Register
Login
{"workbook":{"problemsBrief":"{\"计蒜客-T2341\":[\"优秀的拆分\",2,\"[NOI2016]\"],\"洛谷-P3975\":[\"弦论\",5199,\"TJOI2015\"],\"CodeForces-1207G\":[\"Indie Album\",1031,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1207\\\"\\u003eEducational Codeforces Round 71 (Rated for Div. 2)\\u003c/a\\u003e\"],\"洛谷-P2408\":[\"不同子串个数\",6021,null],\"Gym-103447L\":[\"Karshilov\\u0027s Matching Problem\",47,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/103447\\u0027 target\\u003d\\u0027_blank\\u0027\\u003eThe 2021 China Collegiate Programming Contest (Harbin)\\u003c/a\\u003e\"],\"Gym-104160H\":[\"P-P-Palindrome\",90,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/104160\\u0027 target\\u003d\\u0027_blank\\u0027\\u003eThe 2022 ICPC Asia Shenyang Regional Contest (The 1st Universal Cup, Stage 1: Shenyang)\\u003c/a\\u003e\"],\"Gym-103427M\":[\"String Problem\",289,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/103427\\u0027 target\\u003d\\u0027_blank\\u0027\\u003eThe 2021 ICPC Asia Shenyang Regional Contest\\u003c/a\\u003e\"],\"SPOJ-LCS\":[\"Longest Common Substring\",4455,\"\"],\"CodeForces-932G\":[\"Palindrome Partition\",938,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/932\\\"\\u003eICM Technex 2018 and Codeforces Round 463 (Div. 1 + Div. 2, combined)\\u003c/a\\u003e\"],\"黑暗爆炸-3942\":[\"Censoring\",134,\"Usaco2015 Feb\"],\"洛谷-P4070\":[\"生成魔咒\",4496,\"SDOI2016\"],\"洛谷-P6292\":[\"区间本质不同子串个数\",1075,null],\"洛谷-P5840\":[\"Divljak\",1224,\"COCI2015\"],\"洛谷-P5685\":[\"快乐的 JYY\",702,\"JSOI2013\"],\"CodeForces-163E\":[\"e-Government\",1697,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/163\\\"\\u003eVK Cup 2012 Round 2\\u003c/a\\u003e\"],\"洛谷-P4555\":[\"最长双回文串\",6227,\"国家集训队\"],\"洛谷-P6139\":[\"广义后缀自动机(广义 SAM)\",4482,\"模板\"],\"洛谷-P2414\":[\"阿狸的打字机\",5002,\"NOI2011\"],\"Gym-103470E\":[\"Paimon Segment Tree\",148,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/103470\\u0027 target\\u003d\\u0027_blank\\u0027\\u003eThe 2021 ICPC Asia Nanjing Regional Contest (XXII Open Cup, Grand Prix of Nanjing)\\u003c/a\\u003e\"],\"CodeForces-1202E\":[\"You Are Given Some Strings...\",1880,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1202\\\"\\u003eEducational Codeforces Round 70 (Rated for Div. 2)\\u003c/a\\u003e\"],\"CodeForces-17E\":[\"Palisection\",1739,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/17\\\"\\u003eCodeforces Beta Round 17\\u003c/a\\u003e\"],\"洛谷-P5496\":[\"回文自动机(PAM)\",5350,\"模板\"],\"HDU-7091\":[\"重叠的子串\",43,\"\\u003cdiv class\\u003d\\\"panel_content\\\"\\u003e \\u003ca href\\u003d\\\"https://acm.hdu.edu.cn/search.php?field\\u003dproblem\\u0026amp;key\\u003d2021CCPC%BB%AA%CE%AA%D4%C6%CC%F4%D5%BD%C8%FC\\u0026amp;source\\u003d1\\u0026amp;searchmode\\u003dsource\\\"\\u003e 2021CCPC华为云挑战赛 \\u003c/a\\u003e \\u003c/div\\u003e\"],\"洛谷-P4762\":[\"Virus synthesis\",1269,\"CERC2014\"],\"洛谷-P3311\":[\"数数\",2141,\"SDOI2014\"],\"洛谷-P5576\":[\"口头禅\",345,\"CmdOI2019\"],\"洛谷-P1177\":[\"排序\",243547,\"模板\"],\"洛谷-P4287\":[\"双倍回文\",3820,\"SHOI2011\"],\"洛谷-P5410\":[\"扩展 KMP/exKMP(Z 函数)\",9231,\"模板\"],\"AtCoder-arc151_e\":[\"Keep Being Substring\",122,\"\\u003ca class\\u003d\\\"contest-title\\\" href\\u003d\\\"https://atcoder.jp/contests/arc151\\\"\\u003eAtCoder Regular Contest 151\\u003c/a\\u003e\"],\"Gym-103433J\":[\"Two Prefixes\",34,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/103433\\u0027 target\\u003d\\u0027_blank\\u0027\\u003e2018-2019 Russia Team Open, High School Programming Contest (VKOSHP 18)\\u003c/a\\u003e\"],\"洛谷-P1659\":[\"拉拉队排练\",5248,\"国家集训队\"],\"Gym-103069G\":[\"Prof. Pang\\u0027s sequence\",264,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/103069\\u0027 target\\u003d\\u0027_blank\\u0027\\u003e2020 ICPC Asia East Continent Final\\u003c/a\\u003e\"],\"Gym-103409H\":[\"Popcount Words\",40,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/103409\\u0027 target\\u003d\\u0027_blank\\u0027\\u003eThe 2021 CCPC Guilin Onsite (XXII Open Cup, Grand Prix of EDG)\\u003c/a\\u003e\"],\"Gym-103409J\":[\"Suffix Automaton\",176,\"\\u003ca href\\u003d\\u0027https://codeforces.com/gym/103409\\u0027 target\\u003d\\u0027_blank\\u0027\\u003eThe 2021 CCPC Guilin Onsite (XXII Open Cup, Grand Prix of EDG)\\u003c/a\\u003e\"],\"洛谷-P5341\":[\"甲苯先生和大中锋的字符串\",1470,\"TJOI2019\"],\"洛谷-P4052\":[\"文本生成器\",3733,\"JSOI2007\"],\"洛谷-P3041\":[\"Video Game G\",2442,\"USACO12JAN\"],\"洛谷-P3121\":[\"Censoring G\",3894,\"USACO15FEB\"],\"洛谷-P3649\":[\"回文串\",4592,\"APIO2014\"],\"计蒜客-T2351\":[\"品酒大会\",10,\"[NOI2015]\"],\"洛谷-P3804\":[\"后缀自动机(SAM)\",17409,\"模板\"],\"洛谷-P5829\":[\"失配树\",2824,\"模板\"],\"QOJ-1856\":[\"Interval\",44,\"\\u003ca href\\u003d\\\"https://qoj.ac/contest/695\\\"\\u003ePetrozavodsk Summer 2021. Day 5. Shanghai ICPC Camp 2021 Onsite Day 2 by PKU\\u003c/a\\u003e\"],\"洛谷-P3805\":[\"manacher\",32625,\"模板\"],\"CodeForces-906E\":[\"Reverses\",484,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/906\\\"\\u003eCodeforces Round 454 (Div. 1, based on Technocup 2018 Elimination Round 4)\\u003c/a\\u003e\"],\"CodeForces-1200E\":[\"Compress Words\",7886,\"\\u003ca style\\u003d\\\"color: black\\\" href\\u003d\\\"https://codeforces.com/contest/1200\\\"\\u003eCodeforces Round 578 (Div. 2)\\u003c/a\\u003e\"],\"洛谷-P3809\":[\"后缀排序\",30433,\"模板\"],\"洛谷-P3373\":[\"线段树 2\",65997,\"模板\"],\"洛谷-P5357\":[\"AC 自动机\",13472,\"模板\"],\"洛谷-P5555\":[\"秩序魔咒\",888,null],\"黑暗爆炸-3670\":[\"动物园\",310,\"Noi2014\"],\"洛谷-P3375\":[\"KMP\",78058,\"模板\"]}","joined":false,"groups":{}},"managingGroups":{},"author":"George_Plover","updateTime":1675510508000,"title":"2023树德集训-知识点题单","dislikeCnt":0,"content":"OI-wiki https://oi-wiki.org/string/\n\n\n### KMP\n#### 模板代码示例\n```cpp\n//kmp\nnxt[1]\u003d0;\nfor(int i\u003d2,j\u003d0;i\u003c\u003dm;i++)\n{\n while(j\u0026\u0026b[i]!\u003db[j+1])j\u003dnxt[j];\n if(b[i]\u003d\u003db[j+1])j++;\n nxt[i]\u003dj;\n}\nfor(int i\u003d1,j\u003d0;i\u003c\u003dn;i++)\n{\n while( j \u0026\u0026 a[i]!\u003db[j+1] )j\u003dnxt[j];\n if( a[i] \u003d\u003d b[j+1] )j++;\n if(j\u003d\u003dm){}\n}\n```\n\n```cpp\nvector\u003cint\u003e z_function(string s) {//z函数\n int n \u003d (int)s.length();\n vector\u003cint\u003e z(n);\n for (int i \u003d 1, l \u003d 0, r \u003d 0; i \u003c n; ++i) {\n if (i \u003c\u003d r) z[i] \u003d min(r - i + 1, z[i - l]);\n while (i + z[i] \u003c n \u0026\u0026 s[z[i]] \u003d\u003d s[i + z[i]]) ++z[i];\n if (i + z[i] - 1 \u003e r) l \u003d i, r \u003d i + z[i] - 1;\n }\n return z;\n}\n```\n\n#### 题单\n\n* kmp与扩展kmp的模板\n[problem:洛谷-P3375]\n[problem:洛谷-P5410]\n\n* next数组性质和基础应用\n[1837: 最小循环节](http://132.232.67.120/problem.php?id\u003d1837)\n[1838: 动态匹配](http://132.232.67.120/problem.php?id\u003d1838)\n[problem:洛谷-P5829]\n[problem:黑暗爆炸-3670]\n[problem:CodeForces-1200E]\n[problem:黑暗爆炸-3942]\n[problem:Gym-103433J]\n* [【HDU 7084】Pty loves string](http://132.232.67.120/problem.php?id\u003d4027)\n\n---\n### AC自动机\n```cpp\nstruct ACAM{//不跳fail版,真实的一步到位自动机 以0为根\n const static int None \u003d 0;\n int fail[MAXM];int siz,root;queue\u003cint\u003e q;\n struct node{\n int son[26];int cnt;\n void init(){cnt\u003d0;for(int i\u003d0;i\u003c26;i++)son[i]\u003d0;}//root\u003d0\n }tr[MAXM];\n void init()\n {\n for(int i\u003d1;i\u003c\u003dsiz;i++)tr[i].init();\n siz\u003d0;root\u003d0;fail[root]\u003dNone;\n for(int i\u003d0;i\u003c26;i++)tr[None].son[i]\u003droot;\n }\n ACM(){init();}\n void add(char *s)\n {\n int tmp\u003droot;\n for(int i\u003d0;s[i];i++)\n {\n if(!tr[tmp].son[s[i]-\u0027a\u0027])\n tr[tmp].son[s[i]-\u0027a\u0027]\u003d++siz;\n tmp\u003dtr[tmp].son[s[i]-\u0027a\u0027];\n }\n tr[tmp].cnt++;\n }\n void get_fail()\n {\n q.push(root);\n while(!q.empty())\n {\n int u\u003dq.front();q.pop();\n for(int i\u003d0;i\u003c26;i++)\n {\n int v\u003dtr[u].son[i];\n if(!v)\n {\n tr[u].son[i]\u003dtr[fail[u]].son[i];\n continue;\n }\n fail[v]\u003du?tr[fail[u]].son[i]:root;\n q.push(v);\n }\n }\n }\n void work(char *s)\n {\n int tmp\u003droot;\n for(int i\u003d0;s[i];i++)\n {\n tmp\u003dtr[tmp].son[s[i]-\u0027a\u0027];\n {/*DO SOMETHING*/}\n }\n }\n}acam;\n```\n* 模板\n[problem:洛谷-P5357]\n[problem:洛谷-P3121]\n\n* fail树以及运用\n[problem:洛谷-P2414]\n[problem:CodeForces-163E]\n[problem:CodeForces-1207G]\n[problem:CodeForces-1202E]\n[problem:洛谷-P5840]\n\n* AC自动机dp\n[problem:洛谷-P3041]\n[problem:洛谷-P4052]\n[problem:洛谷-P3311]\n\n* [【HDU 7081】Pty loves book](http://132.232.67.120/problem.php?id\u003d4030)\n\n* AC自动机倍增\n[problem:Gym-103447L]\n[problem:Gym-103409H]\n\n----\n### 后缀自动机(SAM)\nhttps://oi-wiki.org/string/sam/\n\n```cpp\nstruct State{//注意状态数最多是字符数的两倍\n int len,link;\n int son[26];\n State(){len\u003dlink\u003d0;memset(son,0,sizeof(son));}\n};\nState st[MAXN];\nint siz,last;\nvoid init_SAM()//root is 0\n{\n siz\u003d0;st[0].len\u003d0;st[0].link\u003d-1;\n siz++;last\u003d0;\n}\nvoid sam_extend(char c)\n{\n int now \u003d siz++;\n st[now].len \u003d st[last].len+1;\n int p\u003dlast;\n while(p!\u003d-1\u0026\u0026!st[p].son[c-\u0027a\u0027]){\n st[p].son[c-\u0027a\u0027]\u003dnow;\n p\u003dst[p].link;\n }\n if(p\u003d\u003d-1)\n st[now].link\u003d0;\n else{\n int q\u003dst[p].son[c-\u0027a\u0027];\n if(st[p].len + 1 \u003d\u003d st[q].len)\n st[now].link \u003d q;\n else{\n int clone\u003dsiz++;\n st[clone]\u003dst[q];\n st[clone].len\u003dst[p].len+1;\n while(p!\u003d-1\u0026\u0026st[p].son[c-\u0027a\u0027]\u003d\u003dq){\n st[p].son[c-\u0027a\u0027]\u003dclone;\n p\u003dst[p].link;\n }\n st[q].link\u003dst[now].link\u003dclone;\n }\n }\n last\u003dnow;\n}\n```\n\n###### 广义后缀自动机:\n\n(推荐学习的博客:https://www.luogu.com.cn/blog/ChenXingLing/solution-p6139)\n\nendpos集合自然而然变成了字典树上的节点集合。\n\n(修改extend,使其传入last值,并且返回新添节点的号码)\n\n如果允许离线:那么直接在trie树上宽搜拓展即可,拓展的时候起始last取父亲的对应节点。\n\n在线逐串构造:每新开一个串的时候把last置为根(0),然后在extend开头添加特判代码即可:\n\n```cpp\nif(st[last].son[c-\u0027a\u0027]){\n int q \u003d st[last].son[c-\u0027a\u0027];\n if(st[last].len+1 \u003d\u003d st[q].len)return q;\n int clone\u003dsiz++;st[clone]\u003dst[q];st[clone].len\u003dst[last].len+1;\n while(last!\u003d-1\u0026\u0026st[last].son[c-\u0027a\u0027]\u003d\u003dq){\n st[last].son[c-\u0027a\u0027]\u003dclone;\n last\u003dst[last].link;\n }\n return st[q].link\u003dclone;\n}\n```\n\n\n\n* 模板题\n\n[problem:洛谷-P3804]\n[problem:洛谷-P6139]\n\n* 基本运用\n[problem:洛谷-P2408]\n[problem:SPOJ-LCS]\n[problem:洛谷-P4070]\n[problem:洛谷-P5341]\n\n* SAM的图的性质\nSAM 的字符转移边构成DAG,图上任何一条从根出发的路径,都表示了原串的一个子串。\n[problem:洛谷-P3975]\n[problem:Gym-103427M]\n\n* 结合其它数据结构 \n因为link树的性质,可能和一些数据结构题结合。\n[problem:洛谷-P6292]\n[problem:洛谷-P5576]\n[problem:HDU-7091]\n\n----\n\n### 后缀数组\n\n通常指 $O(n\\log n)$ 的后缀排序算法。(存在$O(n)$做法,但实现难度较大)\n\n```cpp\nstruct SA{\n static const int N\u003d1101;\n char s[N];\n int len,sa[N],rk[N],lst_rk[N\u003c\u003c1],lst_sa[N],cnt[N],h[N];\n int ass[N];//rk起点后缀的排名,sa排名对于的后缀起点\n void input(char *str){//输入字符串\n int i;\n for(i\u003d0;str[i];i++)s[i+1]\u003dstr[i];\n s[i+1]\u003d\u0027\\0\u0027;len\u003di;\n }\n bool cmp(int x,int y,int w){//比对,用于重标号\n return lst_rk[x]\u003d\u003dlst_rk[y]\u0026\u0026lst_rk[x+w]\u003d\u003dlst_rk[y+w];\n }\n void get_sa(){\n if(len\u003d\u003d1){//特判长度为1的串\n sa[1]\u003drk[1]\u003d1;return;\n }\n int i,m\u003d300,p,w;\n memset(cnt,0,(m+1)*sizeof(int));\n memset(lst_rk+1,0,2*len*sizeof(int));\n for(i\u003d1;i\u003c\u003dlen;i++)++cnt[rk[i]\u003ds[i]];\n for(i\u003d1;i\u003c\u003dm;i++)cnt[i]+\u003dcnt[i-1];\n for(i\u003dlen;i\u003e\u003d1;i--)sa[ cnt[rk[i]]-- ]\u003di; //最开始做一遍计数排序,初始化sa和rk\n \n for(w\u003d1;w\u003clen;w*\u003d2,m\u003dp)\n {\n for(p\u003d0,i\u003dlen;i\u003elen-w;i--)lst_sa[++p]\u003di;\n for(i\u003d1;i\u003c\u003dlen;i++)\n if(sa[i]\u003ew)lst_sa[++p]\u003dsa[i]-w;//直接利用sa处理好第二关键字排序后的结果\n memset(cnt,0,(m+1)*sizeof(int));\n for(i\u003d1;i\u003c\u003dlen;i++)++cnt[ ass[i] \u003d rk[lst_sa[i]] ];\n for(i\u003d1;i\u003c\u003dm;i++)cnt[i]+\u003dcnt[i-1];\n for(i\u003dlen;i\u003e\u003d1;i--)sa[ cnt[ass[i]]-- ] \u003d lst_sa[i];//基数排序,按第一关键字排序\n memcpy(lst_rk+1,rk+1,len*sizeof(int));\n for(p\u003d0,i\u003d1;i\u003c\u003dlen;i++)\n rk[sa[i]] \u003d cmp(sa[i],sa[i-1],w)?p:++p;//重新标号\n }\n }\n void get_h()\n {\n for(int i\u003d1,k\u003d0;i\u003c\u003dlen;i++)//计算h函数\n {\n if(k)k--;\n while(s[i+k]\u003d\u003ds[ sa[rk[i]-1] + k ])++k;\n h[rk[i]]\u003dk;\n }\n h[1]\u003d0;\n }\n}sa;\n```\n\n\n* 模板\n[problem:洛谷-P1177]\n[problem:洛谷-P3809]\n\n* 运用(难度较大时可结合数据结构)\n[problem:SPOJ-LCS] 板子\u0026基本运用\n[problem:计蒜客-T2341]\n[problem:计蒜客-T2351] 与并查集结合\n[problem:Gym-103409J] 与线段树离线问题结合\n[problem:AtCoder-arc151_e] 运用\n\n----\n\n### 马拉车\n\n```cpp\nchar s[MAXN],t[MAXN*2+10];\nint lens,lent,mx,p[MAXN*2+10];//s:原串,下标从0开始,t\u003d$#...#\nvoid prepare()\n{\n\tlent\u003d0;lens\u003dstrlen(s);t[0]\u003d\u0027$\u0027;//初始化插入串\n\tfor(int i\u003d0;i\u003clens;i++){\n\t\tt[++lent]\u003d\u0027#\u0027;t[++lent]\u003ds[i];\n\t}\n\tt[++lent]\u003d\u0027#\u0027;t[lent+1]\u003d\u0027\u0026\u0027;//注意越界\n}\nvoid manacher()//求出t中每个中心的回文半径,半径-1就是长度\n{\n\tint id\u003dmx\u003d0;\n\tfor(int i\u003d1;i\u003c\u003dlent;i++){\n\t\tif(mx\u003e\u003di)p[i]\u003dmin(mx-i+1,p[id*2-i]);\n\t\telse p[i]\u003d1;\n\t\twhile(t[p[i]+i]\u003d\u003dt[i-p[i]])p[i]++;\n\t\tif(p[i]+i-1\u003emx){\n\t\t\tmx\u003dp[i]+i-1;id\u003di;\n\t\t}\n\t}//s的第i个字符在t的2i下标上\n}\n```\n\n* 模板\n[problem:洛谷-P3805]\n\n----\n\n### 回文自动机(回文树)\n\n```cpp\nstruct node{\n int len,cnt,ch[26],fail;\n int dep;\n}p[MAXN];\nint siz,n,last;\nchar s[MAXN];\nvoid init(){\n siz\u003d2;\n p[1].fail\u003d2;p[1].len\u003d0;//even root\n p[2].fail\u003d1;p[2].len\u003d-1;//odd root\n last\u003d1;\n}\nvoid extend(char* z,int i){//index from 1\n while(z[i]!\u003dz[i-p[last].len-1])last\u003dp[last].fail;\n if(!p[last].ch[z[i]-\u0027a\u0027]){\n p[last].ch[z[i]-\u0027a\u0027] \u003d ++siz;\n p[siz].len \u003d p[last].len + 2;\n int tmp \u003d p[last].fail;\n while(z[i]!\u003dz[i-p[tmp].len-1])tmp\u003dp[tmp].fail;\n if(p[siz].len\u003e1\u0026\u0026p[tmp].ch[z[i]-\u0027a\u0027]){p[siz].fail\u003dp[tmp].ch[z[i]-\u0027a\u0027];}\n else{p[siz].fail\u003d1;}\n }\n last \u003d p[last].ch[z[i]-\u0027a\u0027];\n p[last].cnt++;\n}\n```\n\n* 模板题\n[problem:洛谷-P5496]\n[problem:洛谷-P4287]\n[problem:洛谷-P4555]\n[problem:洛谷-P3649]\n\n* 简单应用\n[problem:洛谷-P5555]\n[problem:洛谷-P1659]\n[problem:洛谷-P5685]\n\n* 应用\n[problem:CodeForces-17E] 邻接链表PAM\n[problem:洛谷-P4762] dp\n[problem:CodeForces-932G] \n[problem:CodeForces-906E] \n[problem:Gym-104160H] 考察性质\n\n----\n\n### 线段树\n\n#### 矩阵运用\n[浅谈矩阵乘法维护线段树标记的技巧](https://www.luogu.com.cn/blog/George-Plover/qian-tan-xian-xing-lan-biao-ji-wei-hu-ji-qiao-yi-xian-duan-shu-wei-li)\n\n[problem:洛谷-P3373]\n[problem:Gym-103470E]\n[problem:Gym-103069G]\n[problem:QOJ-1856]\n\n[4028: 【HDU多校-2021 第二场 1007】I love data structure](http://132.232.67.120/problem.php?id\u003d4028)\n\n(贴一篇 QOJ-1856 Interval 的[题解](https://www.luogu.com.cn/blog/George-Plover/post-2021-icpc-hua-wei-tiao-zhan-sai-prod-interval))\n\n#### 线段树合并\n需要动态开点\n\n```cpp\nint Merge(int x,int y,int L,int R)\n{\n if(!x)return y;\n if(!y)return x;\n if(L\u003d\u003dR)\n {\n tr[x].sum\u003d1;\n return x;\n }\n int mid\u003d(L+R)/2;\n tr[x].l\u003dMerge(tr[x].l,tr[y].l,L,mid);\n tr[x].r\u003dMerge(tr[x].r,tr[y].r,mid+1,R);\n pushup(x);\n return x;\n}\n```\n\n###### \n\n\n----\n\n\n\n","threadId":136055,"likeCnt":0,"createTime":1674830560000,"isWorkbook":true,"viewCnt":816,"openness":2,"fav":false,"id":3434,"trustable":false}