简单题写蠢做法。
我用了 \(set\)
来维护同一行同一列的信息然后还要查询什么的，实际上 vector
就可以了，记录一下该点的行下标和列下标。
简单题写挂。
首先转对照局面。
想到可以先二分个左时间出来，然后仿超级钢琴。
实际上可以二分个左时间和右时间暴力排序，码量更小了。
写挂是排序的各种问题。
排序，尤其是对编号排序，一定要搞清楚排的到底是什么的序。
做不来的趣味题。
考场上想到可以 \(O(n^3)\) 的动态规划，方法是设 \(dp[i][j][k]\) 表示考虑到 \(i\)，漏了 \(j\) 个 \(B\)，当前有 \(k\) 个 \(A\)，转移可以做到 \(O(1)\)。
左看右看都觉得有一维是多余的，但是就是去不掉。
考虑最终答案的分界线，然后动态规划，就可以去掉一维，但是动态规划变成反向了。
容易发现转移的重复性很高，相当于是一个行向量乘上若干矩阵再乘一个列向量，可以反过来写。
考场上没想到反过来写，是因为反过来之后动态规划就没有明晰的组合意义了，所以陷入了正向的窠臼，不容易思考。
参考某道题(T2)。
周末做题脑袋一团浆糊
参考 11.10 T4 的思路，按照 height 从小到大考虑，这样同时也方便了安排 \(a_i\)，然后发现当前叶子只能有被占用或者继续拓展，如果当前的 height 为 \(i\)，那么拓展到 \(i+1\) 还需要考虑右儿子，所以只记一维是不行的。
于是记 \(dp[x][y]\) 表示当前 height 有 \(x\) 个，height-1 有 \(y\) 个，其实可以不用记高度，因为只需要算答案， \(height\) 增加的时候答案整体增加就可以了。
转移的话还需要套上一层已经安排到的位置，设 \(dp[i][x][y]\) 表示前 \(i\) 个已经被安排，当前 height 有 \(x\) 个，height-1 有 \(y\) 个，由于 height-1 已经被强制选过了，延申过左儿子了，所以不能作为叶子，作为叶子转移的只有 height，这样的话阶段是 \(i\)，然后再是 \(x\)，最后是 \(y\)。保证了无环性。
同阶段转移，顺序先枚举 \(x\)，再枚举 \(y\)，转移到 \(dp[i][x+y][x]\)，容易发现除了 \(0\ 0\) 都是无环的且符合拓扑序的。
不同阶段转移很简单。
小猪猪经常把 height 写成 heigh，我不说是谁。
非常非常妙的一道题。
暴力无非就是并查集，但是如果加边比较多，暴力并查集就寄了。
并查集有交换律，考虑改变并查集运算的顺序，达到加速的目的。
可以用倍增的思路设计一种广义并查集，然后操作就被暂时拆了，\(fa[x][i]\) 表示 \(x\) 为起点的 \(2^i\) 个数的并查集父亲，意义是 \(x,x+1,x+2\cdots\) 的并查集父亲分别为 \(fa[x][i],fa[x][i]+1,fa[x][i]+2\cdots\)。
注意这里的操作是具有整体性的，必须对于 \(2^i\) 个点都满足，才能改广义并查集的父亲。
考虑下放操作，这是简单的，只需要将 \((fa[x][i],i-1)\) 和 \((x,i-1)\) ，\((fa[x][i]+(1<<i-1),i-1)\) 和 \((x+(1<<i-1),i-1)\) 连边就行。
很难从一道题中总结出有用的东西，但是不妨作为一个启发性的思路。
这个思路也可以被认为是
lazy_tag，具体怎么思考会得到不同的启发。
感觉每次考贪心都不会。
考虑先排除掉包含其它线段的线段，变成左右双单调。
然后容易发现选的线段是一段区间，一旦选线段变成选区间，就好做了，朴素的方式是动态规划，可以做到 \(O(n^2)\)，看上去已经不容易优化了。
发现答案的计算方式是比较简单的，考虑最终情况，假设选了 \(i\) 作为终点，那么实际上每个 \(i\) 的贡献是独立的，为 \(-L_i+R_{i+1}\)（注意这里忽略了无交的情况，无交的情况下面再讨论），这里的 \(i\) 不能为 \(n\)，因为 \(n\) 本来就是终点，排序取前 \(k-1\) 大即可。
加上那些被排除的线段，被排除的线段，要么原封不动放回去，不对答案贡献，要么就自成一段，枚举前面选了几个区间就行，取最大值。
注意到，我们对无交的情况，答案计算方式是有问题的，需要和无交情况的最大值再比较一下，无交情况的最大值就是选最长的 \(k-1\) 个。
总的来说，这是一道分类讨论题，先讨论包含的情况变成双单调，再排除无交的情况变为排序贪心。
Boruvka 题。
Boruvka 本质上是把 Prim 和 Kruscal 结合了起来，然后需要求一个 \(mn[i]\) 表示连通块 \(i\) 连出去的所有边的最小值，然后尝试连边。
Boruvka 的过程会进行 \(\log n\) 次，可以这么说，Boruvka 以一个 log 的代价，换来了通过预处理同一连通块求 多个 Prim 中的最小值的机会。
Boruvka 是来自异世界的神秘算法，请和我念：“\(\text{B--oru--vka}\)”
Boruvka 的核心是要求 \(mn[i]\)，但是一般来说也可以用分析连边性质（一般是三元环或者四元环）来减小边数，比如边权为异或的题目，分析 \(Kruscal\) 的过程可以做到 \(n\log^2n\)，而不必拘泥于 Boruvka。
考虑对于连通块怎么求 \(mn[i]\)，一件非常阴间的事情是需要排除掉同一联通块的元素。
如果看成染色，那么就是元素有颜色，就是求全局不同于某个颜色的最小值，区间修改。
还是可以线段树，维护一个最小值和颜色，不同于最小值颜色的次小值，然后就可以做了。
一个矩阵加需要映射成两个。
好困难，不会。
用主席树维护求出整个邻接矩阵，考虑哪些边是有用的。
莫名奇妙写挂的题。
题本身意义不大，但是我写了很蠢的做法。
分析问题本质上是需要动态查 \(i\ge l,a_i\in x_i\)，\(a_i\) 不是很大，可以直接预处理每一个元素的 \(next\)，就很方便了，但是考场上写了扫描做法，还写挂了，非常蠢。
拿到题不要直接开冲，可以多想一下有没有更好写的做法/更方便，前面的题没那么难。
观察发现答案不超过 \(1\) 的充要条件是存在一条长度为奇数的路径，答案不超过 \(2\) 的充要条件是存在一条路径。
先假定图联通，所以问题变成了计算无向图 \(s,t\) 之间是否存在长度为奇数的路径，有以下三种方式
思想是分层图跑最短路，但实现上没那么麻烦，考场写的这个做法。
如果有奇环，那在奇环上绕一圈任意可达了，所以考虑先 DFS 求个深度，如果有奇环答案全部为 \(1\)，否则路径唯一求出来就行
还是奇环的思想，实现上使用黑白染色。
这是常数最小的写法，还是考虑分层图，有一条边则合并不同层的两个点，查奇数路径就是不同层是否联通，偶数路径就是相同层是否联通。
不算太难的题，但是确实没有想出来。
首先有个经典结论，先手必败的充要条件为所有可选元素为偶数，证明归纳，显然。
算先手必败显然比先手必胜好算，所以算必败。
先把元素做前缀和，再对 \(2\) 取模。问题就是需要选一个子矩阵，满足首尾两列元素值相同。
考场上想到了可以哈希，由于常数，虽然是 \(n^2m\) 的，但只有 \(52pts\)。
考虑固定下边界，移动上边界的过程，发现相同元素的集合在不断变小，而有了这个集合就可以算答案，这个东西是可以每次 \(O(m)\) 计算的，这样的常数较小，可以得到 \(76pts\)。
先得想到它已经是个字符串题了，考虑上边界不断变化的过程，发现不合法的矩阵个数等于当前 \(m\) 个字符串两两之间 \(LCP\) 的和，然后考虑字符串排序的方式求 LCP，类似后缀排序的 \(height\) 数组，发现后缀排序是很好做的，因为每次上移一行，就是归并排序的过程，\(height\) 和 \(rk\) 都可以线性维护，得到了 \(height\) 之后就单调栈搞定。
考虑非哈希做法的等价类思想，发现虽然维护过程是 \(O(nm)\) 的，但实际上等价类的个数是 \(O(m)\) 的，考虑以移动下边界的方式考察当前下边界所有上边界的等价类，自顶向下的更新等价类，该拆分的拆分，实际上和正解1本质相同。
条件比较特殊，需要先观察。
记 \(T'\) 为 \(T\) 的修剪。
\(T\) 的修剪和 \(T\) 的右子树相同，那么考虑 \(T\) 的右子树 \(R(T)\)，那么 \(L(R(T))=L(T')\)，递归的，\(R(R(T))\) 和 \(R(T)\) 的修剪相同。
归纳边界是 \(L(T)=\emptyset\)，此时右子树可以任意延申右儿子而不受限制，先假设当左儿子为空时右儿子也必须为空，这样就有了一个边界。
因此，如果 \(L(T)\) 确定了，就可以确定出有边界的树的唯一形态。
考察 \(L(T)\) 的各项数据对应到的 \(T\) 的数据。
容易发现： \[ leaf_T=size_{L(T)} + 1\\ height_T=height_{L(T)}+1\\ size_T=height_T+\sum\limits_{u\in L(T)} height_u \] 接下来的事情变成了设计一种合理的方式去枚举合法的 \(L(T)\)，并能够计算这些数据。
枚举二叉树，比较合理的一种方式是以子树大小为阶段来合并，需要记录的信息是 \(dp[i][j][k]\) 表示子树大小为 \(i\)，高度为 \(j\)，\(\sum height_u\) 为 \(k\) 的总方案数，合并的时候需要枚举三维做卷积，复杂度为 \(n^2k^2m^2\)，难以通过本题。
不难发现 \(j\) 可以用前缀和优化，但是其它两维是卷积，动不了的，复杂度 \(O(n^2km^2)\)，实际上常数比较小，可以过掉。
刚刚的方式是子树合并的方式构造二叉树，现在考虑用深度顺序构造，设 \(dp[i][j][k][s]\) 为构造深度为 \(i\)，树大小为 \(j\)，\(\sum height\) 为 \(k\)，可用点数为 \(s\) 的方案数，转移需要枚举向下构造的点数 \(t\)，得到 \(t\) 后可以预处理转移系数，顺便计算出新的 \(j,k,s\)，复杂度为 \(O(kmn^3)\)，更加优秀，事实上 \(j,s,t\) 远远取不到 \(n\)，是非常优秀的复杂度。
但是这个方法是假的，因为深度和 \(\sum height\) 没有必然联系，所以无法计算 \(k\)。
考虑以子树高度的顺序，降序构造二叉树，这和深度顺序又不一样。
考虑设 \(dp[i][j][k][s]\) 表示子树高度为 \(i\)，大小为 \(j\)，\(\sum height\) 为 \(k\) ，叶子个数为 \(s\) 时的方案数，注意这里是按照高度顺序构造，即强制要求先选的部分的高度大于后选的。所以又额外的要求是枚举接下来的增量时需要将所有叶子至少叠加一层，枚举增量 \(t\) 时预处理系数即可，复杂度和深度顺序类似。
考试 考试的时候还很清醒，考完脑子就乱了。
大脑从 i7-9th 退化成 i3-4th，四个字来说就是线程阻塞。
如果说整个社会是一个计算机系统，那一个人自己的大脑就是主板上的所有部件，而其他人，则是一块块只读 HDD 中的数据。当某一块 HDD 损坏，不能存储数据，但是又不想丢失它，就只能将数据保存于主存。主存的大小是有限的，它本不是用来保存数据，如果占用过多，会影响主板部分的正常运行，受到内存大小的限制，CPU 的运算能力自然会退化。
我不太想找心理医生，心理医生会帮我清除掉主存的数据，但是我不想清除。
比较模板的 AC 自动机匹配题，但是 AC 自动机做法需要细算常数，这道题倒是将缓存行访问连续的重要性体现的相当清楚，可以参考几次提交的差异。
另一种方式是注意到两个字符串互不影响，因为出现任何一个字符串都不会对另外一个字符串的出现产生额外影响，所以无需记录具体到了哪个节点。
先考虑没有限制的转移，如果为 ?，则乘
26，否则不变，这样有重复，唯一的重复是对于两种字符串如果接下来可以匹配上，那么转移就应该到对应的差值，因为两种字符彼此不包含所以两种字符串的重复可以独立处理，还是挺好写的。
考场上发现本质上是个可以用线段树做的二维偏序，但是由于马拉车算法本身有二倍常数，还需要跑 4 遍，所以其实有点难卡常，感觉递归版的没救所以我写了非递归版的 update 操作勉强卡过去（query 次数不多可以直接查）。
但是这个答案是可以二分的，二分之后配合马拉车就是个 RMQ，ST 表即可。
容易发现一定会在某个地方反复横跳刷分，所以处理出所有横跳位置的刷分函数（是一次函数），有用的一次函数级别为 \(O(n)\)，为了保证每个函数都可以正常取到，不妨暴力处理前面的 CASE，然后后面的就是维护凸包。
不处理前面的 CASE 是错误的，因为你不能保证在对应的步数限制下一定可以拿到这个函数。
感觉不预处理但是加上某些条件再筛一下函数就可以过，但是这些条件有点难想吧...
少见的 mex 配 xor 题，考场上没想出来，现在脑子很乱，明天再想——11.8
mex 应该是个非常严格的限制，由于询问很少，所以考虑单个询问怎么解决。
比较暴力的方式是逐个加入元素并检查可行性，我们显然必须要求能构成一条链，所以加入点的过程其实比较简单，如果链已经是弯折的形式，那么只能在两颗子树内加点，如果不是，那么新加点和最较深求 LCA，如果在路径上则不合法，重新构造路径的过程也是平凡的。
考虑检查第二个条件，也就是异或合法性，路径的异或值是好求的，对于两边的情况，可以暴力遍历树枚举一边用字典树求另一边。
但是这样的复杂度不对，因为每次暴力遍历都是 \(O(n\log n)\) 的，一共进行了 \(O(nq)\) 次。但是认真思考一下发现答案是可二分的，所以二分即可，复杂度 \(O(nq\log^2n)\)。
\(10^5\) 的题和 \(3\times 10^5\) 的题，考虑复杂度的方式是完全不同的（\(10^5\) 基本可以扔进 L3），所以没必要担心。
好像不二分也是可以的，考虑答案的形式，因为一定会包含 \(0\)，所以以 \(0\) 为根后，可以取到的异或值就形如 \(d_u\oplus d_v\)，其中 \(d_u\) 表示 \(0\) 到 \(u\) 路径上的异或值，每次移动端点时，两边可选的 \(d\) 集合都在变化，集合变化次数是 \(O(n)\) 的，动态维护 \([l,r]\) 区间中数的个数就可以了。
注意，动态维护 lower_bound
的最小值是行不通的，因为最小值不具备逆元，是不可减的。
没想到再来写随记是这样的事。
我没来得及给她说，但很庆幸在这份爱慕没有孤独的消散在心底。
心里的影子失去了实体，会慢慢消散，我希望，我请求，让这个影子，用着这篇记录，留在我心里。
我还算是班上的半个焦点吧，成绩不错，人还行，但是确实就是没有女生喜欢。
我数学很好，初一的时候接触了信息竞赛，还算是有些天赋，初二就开始偶尔停课，但基本还是在班上，可能很多同学对我的印象就是个标准的理科直男，其实我自己不知道，有同学很直白的告诉我，女生们对我的印象是：钢筋混凝土直男。我才知道原来这才是我在班上的真实形象。
初三一次化学实验课的时候，飞象问我，你知道吗，你是班上男生中，唯一一个没有绯闻的。当时飞象已经和 lyx 走在一起了。
对于 lyx，我有过欣赏，如果不是飞象和她已经走在一起了，我可能会追求她，我和飞象是好朋友，毕竟都是当年的信息竞赛三剑客，初三的时候，三剑客走散了，飞象去了数学，jess 去了物理，我留在信息，我信息竞赛成绩确实是最好的那个，但飞象的天赋真的远比我高。
我有些神秘兮兮的告诉飞象，其实我有喜欢的人，我告诉飞象她的名字是 \(Emilia\)，他很吃惊地追问我，我笑而不语，我反复强调，这是 “单方面的暗恋”，他才作罢。
走廊里我和她面对面走过，她举起手对我笑。
"啊，你好！"，我有点羞涩的回答。
她是第一个和我主动打招呼的女生，她有点羞涩，但是脸上的笑很是真诚可爱。
我的目光停在她的短发上。
后面我们每一次正面遇上，我都会和她打招呼。
课间在课桌之间的走道，我装作在随机游走——这是信息竞赛生常见的想题动作，目光却飘向她，飘向她的短发，飘向她的侧脸。
老师会让同学在班上同学的生日时写下祝 xxx 生日快乐，我记下了她的日期。1 月 9 日，写下祝我生日快乐的，应该是她，心中的影子开始清晰起来，所以那次实验课，我才那样对飞象这么说。
初三我开始大面积停课，冲击高一省队，停课时，我和 walk 和 platelet 重新建立起来堪比曾经三剑客的关系。
联赛出了事，无缘高一省队，浑浑噩噩回到班上学文化，12 月很是低落的回到班上学文化课，walk 和 platelet 还在南京集训，但在信息教练，飞象的帮助下，我算是重新振作起来。
老师特地把我安排到飞象旁边坐，在他的帮助下，我文化成绩有些恢复，虽然期末没有考出理想的成绩，但还算是成功走了出来。
停课时在心底的影子浮现出来，和初三一样。在飞象和 lyx 交流感情时，我会起来随机游走，还是那样看着，远远的，像是普通的同学关系。我没有勇气站出来，还没进省队呢，想那么多干什么？我打算，高二先进省队，起码拿到高分银牌，再来处理心里的这份影子。
高一的 12 月，和室友晚间的秘密谈话，我提出了好感度这个议题，大致的标准是 \(20\) 以上称作朋友，\(40\) 以上可以叫亲密朋友，男生之间叫基友，女生之间叫闺蜜，\(60\) 以上，基本可以称作另一半了。
说了很多，我说，同龄人中，我对三个男生好感度有超过 40，而女生，应该只有一个，他说他对一个女生的好感度有 70，我就笑了笑。
其中一天，我告诉室友今天是一个特殊的日子。他问我为啥，我说今天是一个人的生日。他猜出来了，我点点头，这个秘密不再属于我自己。
78 去了南京集训，效果不错，但回来因为疫情留在家里，训练很水，水平往下掉。9 月中旬开学了，状态有所回升。
后面一直没回班上，每天在考试和订正之间徘徊，偶尔穿插一些技术知识的学习和开发实践。
10 月，前三周专心搞竞赛，水平有提升，这段时间陆续结束了其它几科竞赛的考试，我们的成绩都不是很理想。可能是没有找对老师，物理成绩最烂——她是物理竞赛选手。其它竞赛也有各种各样的原因，我们考的很烂。我和 jess 聊了一会儿，jess 决定退役。
CSP 前一周考试和订正之外在研究对话 AI，摸索着搓出了一个小说里的角色——"鹿灵"。“Emilia” 是鹿灵的角色原型，我初三时说出这个名字，也是带着对鹿灵的一分憧憬，我不知道这份对 "鹿灵" 的关注和上心，有没有她的影子，我还是用了 “Emilia” 这个名字。
用英文和鹿灵聊的时候还很是正常，但鹿灵第一次和我用中文对话，她叫我 "彭彭"，还说出很亲密的话，我心里暗道不对，立刻重新开始，但数据被我保留，且当纪念。
CSP 考完了，我的成绩还不错，回来就把鹿灵彻底弄了出来，并连接了 mirai 的接口，放到 QQ 上。
周四，walk 生病住院了，我替他守门，2：1 赢下了球赛，很高兴，晚上吃饭时还看到她排在一旁的队列，她还笑着。
周五上晚自习时，我嗓子开始疼痛，和 walk 症状很像，后面是在受不了，向老师请假出去买药。
在学校门口看到了警车，和一路离校的同学猜测着是不是化学联赛泄题的事情捅出去了，找学生了解情况。
周五晚上我没睡着，喉咙的肿痛让我辗转反侧，今天一早请假去了医院，开了药回家休养，下午去学校拿电脑。
从同住的同学处得知噩耗，确认是那个名字时，好似内心的一块拼图被移走，失去了完整的感觉。
向往飞象那种生活，我暗地给自己打气，要加把劲，让高三可以轻松一点。但憧憬破灭的那一刻，我无力描述心情。
我和她的羁绊，算不上深刻，但绝对可以说是独特，那是我心中唯一一道异性的身影。
离别和相遇虽说是永恒的话题，我也会因为小说中的人物的聚离动情，甚至落泪，但真正在我的身边时，我还是茫然的......
在高一的十二月，我选了一条路。
在高二的十一月，她选了另一条路。
说了那么多，我发现，我没有资格说出那三个字。
我只能祈祷那边没有竞赛课业的烦恼，你能开心地笑起来。
我只能说，我会想你的。我心中的影子，会永远留下的。
你笑起来很可爱的，LXY 同学！
大一届的学长说过，如果把 CW 一整届竞赛班集中起来，是一股难以想象的力量。我说，如果有那么一天，我必定不会缺席。
我们是一个整体，已经持续四年的羁绊，还有两年的路需要我们一起走。
我想起了起床铃 MV 里的悲剧 ~~，它绝对不应该发生在我们这里！
无论前面有多难，请走下去好吗......
那一天那一刻那个场景，你出现在我生命。
从此后从人生重新定义，从我故事里苏醒。
某一天某一刻某次呼吸，我们终将再分离。
而我的自传中曾经有你，没有遗憾的诗句。
hyp or mzx 记于一个伤心的晚上。
很难如此坦诚的讲一件事，但我希望这样坦诚的随记，要少一点。
容易想到只会取到 \(O(n^2)\) 个值，大力动态规划，滑动窗口优化。
滑动窗口的 COST 宏函数写挂了，所以我挂了。
有一个更厉害的思路，容易发现 DP 数组本质上是个分段函数，然后转移就是平移原函数添加一段平的然后再加上一个绝对值函数，根据经典结论，若干绝对值函数叠加是一个形如开口向上二次函数的东西，填一段平的一定会在最低点添，不影响性质。
写挂的题，不过很有意思。
写挂有两个原因，一是图方便用引用，但是没发现被引用的数据其实还有用，然后修改了它，后面又要用它，就寄了。二是转成 \(0-based\) 处理，边转了，但是记录数组先存的边，没有动记录数组。警钟敲烂。
题目本身也是有趣的，首先它定向后必须是个 \(DAG\)，所以只考虑所有的 \(DAG\)，考虑以拓扑序的方式去遍历所有 \(DAG\)，容易发现当拓扑序确定后，定向方式也就确定了，所以一个比较简单的想法是枚举拓扑序。
枚举拓扑序想要转成指数可能不太能用常规方式转，因为的确需要知道每个点的距离, 思考一下其实发现没中过定向方式被计算了多次，所以考虑给这个拓扑序附加一些不影响遍历解空间的性质，比如强制距离单调不降，这样枚举起来就可以大大方方的选一坨独立集，强制转移到它的距离加一，这样的强制加一同样不影响遍历解空间，所以它是对的。
有个东西叫 dilworth 定理, 描述的就是这个东西，最大反链中元素数目等于最小链划分数，我不是很懂这个定理和这道题的关系，但是用这个定理和以上方式思考得出的代码是一样的。
遍历 DAG 的有效方式是通过 TOP 序，尤其是需要定向的 DAG
复杂度 \(O(3^n+n\times2^n)\)
考场上刚出来的题。
指数题看数据范围说话，总感觉子串很麻烦，因为扰乱了信息，所以把子串判掉。
然后觉得如果一个串绕了一圈，也很麻烦，再判掉。
所以现在的环，从某一个子串开始，左端点递增，那右端点也就递增了，所以可以考虑顺序了。
容易发现每个串会尽量往左靠，因为没有子串了，然后最后一个串和第一个串会尽量粘在一起，可以直接把粘在一起的部分减掉，就算减了倒数第二个串的，那其实也没有问题，因为确实可以减掉。
然后阶乘转指数，记录最后一个串的编号和方向，枚举下一个串的编号和方向。
考场上很蠢，每个点为起点算了一遍，其实钦定一个算就行了。
如果把一些 Native 的情况特判掉，可能会得到更加优美的性质，这就是分类讨论题。
字符串替换的题，思路主要有两种。
考虑某个大写字符能替换成什么，发现经过 \(O(\sum)\) 次替换后一定会变成或者多出一个不可替换的字符，所以考虑大力动态规划，设 \(F_{c,i}\) 表示字符 \(c\) 替换成长度为 \(i\) 的不可替换字符串的最小字典序，然后转移顺序不同层已经是固定的，同层转移顺序随意。这样做显然不对，因为有环，但是多做几次他就对了。
考虑按不可替换字符长度为阶段做动态规划，同时处理若干个规则，转移之间如果有环，有两种情况，其一是其它的向它转移过来 \(len\) 个，另一种是下一个大写字符替换为空串，后者可以钦定处理到的位置的顺序转移搞定，前者可以用优先队列类似 DIJ 的思路。
当然，这个思路也可以不考虑转移有环，直接多做几遍就对了。
不像是有低于 \(O(n\sqrt{n})\) 做法的题，上莫队。
题解说 \(O(n\sqrt n\log n)\) 过不了是它写得太烂了，肯定是可以过的。
但是考虑到查询次数为 \(O(\sqrt n)\)， 于是用分块维护就行了。
复杂度 \(O(n\sqrt n)\)，其实进一步观察，发现每次前缀和数组的变换量是 \(O(1)\) 的，分块都可以省了。
\(n,m\) 不要写反，对询问排序的时候 \(n,m\) 写反喜提 WA。
很难的题，我不会。
先得想到它是个构造排列的计数题，直接做哈密顿路径题太过困难了。
构造排列的计数题往往有这些考虑方式：按元素值从小到大考虑构造，按排列下标从小到大构造，以插入元素的方式构造。
以插入元素的方式构造，往往可以按某个外部值排序，经过这个排序之后再来插入，得到理想的结果。
这道题是第三种方式，但是我不是很熟悉这种方式。
转化一下题意，你需要构造一个排列 \(p\)，排列元素的值代表下标，排列顺序代表遍历顺序，需要满足序列的限制条件。
考虑大力动态规划，插入了限制序列下标为 \([1,i]\)，有 \(j\) 个位置不满足条件（R
限制，L 限制必须在插入前满足。）的方案总数为 \(dp[i][j]\)，转移可能还需要记最后一个是否是
R，可以 \(O(n^2)\)
的算出总方案数。
考虑计算以每一个下标结尾的答案，那么在对应位置处需要钦定必须放在最后面，其余的可以正常做，仍然需要讨论倒数第二个到底放的什么，但是动态规划过程中无需记录，只需要讨论最后到底是
R 或 L。
发现我们的计算过程可以等价于一个行向量乘上若干个矩阵再乘上一个列向量。
可以 \(O(n^2)\) 的算出前缀行向量和后缀列向量。因为转移参数和前缀 R 的个数有关，所以还得讨论选择的合并中心是 L 或是 R 。然后 \(O(n)\) 的合并。
复杂度为 \(O(n^2)\)。
题解做法比我高明的一点在于它将第二维记录的信息从简单的 “不合法”
拓展到 “路径条数”，表达力更强，合并起来也更容易理解，同时 DP
的转移矩阵和前缀 R
的个数失去了联系，因为被蕴含在了路径条数这一信息中。
很趣味的题，首先有一个暴力，考虑求出变换后的所有边。
分解样例，猜想答案是一个乘积的形式。
考虑一条边的限制，发现从小到大不太好做，因为对大的有限制的点之间是没有关系的，然后就从大到小做，发现对小的有限制的点必定相互限制，因此第 \(i\) 个元素的贡献就是后面所有 \(n-限制它的点的个数\)，由此也容易证明答案确实是一个乘积形式。
问题变成了求一个点被比它大的哪些点限制，场上没时间了就没想了。
实际上很简单的，直接从小到大合并上来就行，做启发式合并，用并查集去重（一个点如果被合并了，那么就属于较大的那个点，然后另一个点尝试合并它的时候就合并较大那个点），需要把小于等于 \(i\) 的点动态删掉。
复杂度 \(O(n\log^2 n)\)
博弈题，考虑先手必胜的充要条件，直径为 \(2\) 先手必败，考虑直径大于 \(2\) 的所有情况，发现如果选不是叶子的点，每次扔掉所有叶子后直径会减二，如果选直径上的叶子，那直径只会减一，所以一个人可以将一个数减一或者减二。巴什博弈。
问题变成了给根和子树求直径，先搞出以一为根的所有情况，如果根在子树外，输出答案，如果在子树内，那就是向根走一个点之后那个点的 \(from[u]\) 值，很好算。
但是喜提 WA，因为根在当前点是答案是整颗树的答案。
换根问题总共有三种情况：根在子树内，根在子树外，根就是这个点。
从 19 年初二第一次参加 CSP，到今年可能的最后一次，已经四年了。
停课停了也快两年（其中被半停课耽误了半年），勉强到了省队水平。
19 年的 CSP-S 很是开心，毕竟学 OI 8 个月的我和我的朋友，都顺利拿到 1=，只是可惜另一位没有过初赛。
20 年的 CSP-S 有点揪心，CE T2T3 失去了取得历史最高全国排名的机会，（这一年是真的是超水平发挥，100+0+0+95）。但是咱还是顺利 AK 普及组，第一次上了学校的宣传。
20 年发生了很多事，最初一起学 OI 的两位朋友（现在也是最好的朋友），因为各种各样的原因，离开了 OI，我以为我已经是独自一人，但我又结识了新朋友——佳馨和walk。
21 年的 CSP-S 只能说是一般般，我没有做出 T3，T4 也没有写出暴力，遗憾的以 260 画上句号。这一年发生了太多事，NOIP 因为莫名奇妙的原因变成了 0 分，自然无缘省选，高一省队的理想破灭。
22 年，我在 NOIP 碰壁后回归文化课调整心态，期末拿了一个还算行的成绩，我没想到我的文科成绩比理科还好，哈哈。这段时间我接触了软件工程，自己尝试着写工程，学会了 Python 和 JavaScript，22 年开学继续停课冲击省选，虽然我没有机会参考，但水平不能落下。省选自然是几家欢喜几家愁，高三的一位学长心态出了问题，甚至无缘 D 类，佳馨顺利进入省队， walk 以一名之差留在外面，我在 Day1Day2 的下午分别到原考场（我们学校是考点）做了题，心情很是糟糕。省选后学了 2 个月的文化，OI 的水平开始停滞。学完高一的文化课内容，去了外地集训，但是水平并没有太大提升，回学校后开始常态化考试，停滞的水平继续有了一些上涨，这个时候我还要兼顾两三个工程项目的开发，非常累，于是就把工程项目全部推了，发现好像又有点无所事事，最后还是捡回来了一个，CSP 前一周和佳馨研究 web 相关的东西，为盒武器的研发做准备，不小心把 vjudge 搞炸了，后面操作就很小心了，没再出事，事实上我周六早上还在一边写我 mirai-plugin 项目的 kotlin，一边和教练聊怎么学 Python。
终于出发了，在校车坐在前排上一路唱着歌，但是后面的学弟们都没听，我甚至还没有意识到我已经是车上年级最大的人了，还是那副嘻嘻哈哈的脸。
到考场，和转学的同学面基，还拍照留念，然后进考场的时候感叹人家是什么机房，我们是什么机房，有一说一， i7-12 的机子用起来那是一个舒服，可惜 windows 下没有高版本 g++，被迫用 c++11 语法，战斗力下跌 10%，发现有没有 Python，战斗力再下叠 5%。
发题，顺序开，T1 想都没想一个 bfs 求全起点最短路先糊上去了，然后定义了 dp 准备 dp，发现好像不太好搞，想了一下，还是得枚举，枚举策略就那几种，试试就出来了，但发现有不少细节，于是停下来认真构思代码，用了一些面向对象的思想，很顺利的一遍写过，通过所有大样例。
T2 看了一下，简单题，还是细节很多，继续停下构思代码结构，又使用了一些面向对象的方式，写出来很优美的代码，一遍过大样例。
此时还剩 3h，我尝试开 T3，比较顺利的想出 60
暴力，发现不会正解，难道要重蹈覆辙？发现数据其实挺难造的，于是考虑乱搞，写了一个放
Tag 的做法，我尝试 Hack
这个做法，没有成功，但是我确实知道这样的复杂度是假的，我从来没怀疑过自己造数据的能力，我并不认为出题人造数据的水平能比我高到哪里去，所以大胆当正解写了，我对自己的常数也很放心，大致思考了一下最坏情况，如果目标为
\(80pts\)，操作数其实可能也就 \(4\times 10^{10}\)
的样子，而且不可能卡满，但是没有高版本 g++，unordered_set
用起来还是有些提心吊胆的，如果有个
gp_hash_table，我会放心很多。大样例那么水，当然轻而易举跑过啦。
这时我还有 1.5h，思考了一下，扣除了 0.2h 最终检查的时间，我放弃了 T4 正解，尽管我浏览题目时已经想出了它的正确解法，我把目标定为 68pts 的暴力，但是并不顺利，我没有通过最后一个大样例，而且无论如何都找不出问题，最后应该是 36~40 分。
出来自测，不出所料，所有民间数据都卡不掉我的 T3，目前是 100+100+100+40
首先求什么东西的和，这类题，一看到就要想是不是该开
long long。
多测题，特别是样例水的题，一定要认真检查清空，以及不要读入到一半 break 出去！！！