西电新生赛网络赛题解
持续六天的新生赛终于落下了帷幕，打了 8 道题，第 21 名，对于两年没有碰过 oi 的我来说已经是一个不错的成绩了，如果运气好的话还能水到一等奖，怎么说都血赚。
但不得不说的是，我这次的状态比两年前打 CSPS 要好太多了，如果以我现在的心理素质和之前的知识水平去打，那肯定是不同的结果了。
这次比赛原本想用 Amentiraz 这个昵称去打，但思来想去还是用了最开始的 dsfly 昵称去打，一来这个名称短（够装 B），二来这个名称是我最开始打 oi 时的昵称，意味着一个新的开始吧。
说是六天，实际上就打了前三天，主要是还有本职的学习工作，第二是因为小说太好看了（笑）。还是把除了 J 题以外的所有题都摸了一遍，可以说除了 J 题我做不出来，其余的花时间都能做出来，放了 H 题和 K 题，H 题是因为纯模拟暴力，太恶心了，不想写，K 题是让你直接输出时间复杂度，搞了几下没出来，又不想去看资料，于是就放了。（留着时间看番不香吗）
Tarjan
想当年高中组织活动的时候我还专门写过 Tarjan 的流程和证明，如今已经忘的干干净净，原来的代码也找不到了，只能现写了。
总的来说就是利用一个栈，将每个访问到的点 push 入栈，在寻找的过程中记录两个值，一个是 dfn—— 它是第几个搜索到的，一个是 low—— 它能衍生的点中 dfn 最小的值。如果一个点 dfn==low 说明它本身就是最小的点，把它及它栈以上的点全部 pop 出来就行，因为它上面的点必定是与它形成强联通分量。我们不妨假设它上面的点有不是它强联通分量的，那么此点在回溯到它本身的时候只有两种情况，一是它本身是强联通最小的点，那么在找到此点时会把它上面的点全部 pop 出去，另一种是它不是最小点，那么在遍历的过程中总会到第一种情况把它排除。
Tarjan 程序是正确无误的，然后最后要跑一个拓扑，然鹅我不大会。luogu 上爆了 40pt，然后去看别人的题解秒懂。用拓扑可以优化掉 ans、Q、new_val 等等数组，估计就 80pt 了，然后我们还得用 dp 去解决菊花图这种类型的数据。
这道题还给人一个教训是，对于缩点的题，我们记录下每条路径的开始与结束去构造新图，没必要单独列个 Q 这种数组。
40pt 代码如下：
（其实会个 Tarjan 就行了吧）
LCA
LCA（Least Common Ancestors），即最近公共祖先，是指在有根树中，找出某两个结点 u 和 v 最近的公共祖先。 ——— 来自百度百科
对于一棵树来说，我们为了求它的最近公共祖先其实思路和快速幂是差不多的，我们不能直接一个个的向上查找，这样会使时间复杂度爆表，我们应当以 2^k 的速率往上找，这样可以使其时间复杂度降为 log 级别。
不得不说 luogu 上的题解实在是晦涩难懂，我能明白他们在寻找相同深度的点的时候使用 log 可以更快的找到，但是其实可以一层层的向上跳，可能时间复杂度常数上乘个 5 左右的数，但影响不大。（还是自己的代码好懂）
听说树链剖分也可以做，但这玩意写起来太麻烦了，我高中最快时写一遍也要半个小时（毕竟 100 多行）
总之，我们求 LCA 时首先找每个节点 2^i 的父亲，然后先将它们跳到相同的深度然后再同时向上跳，注意特判其中一个节点就是 LCA。
线段树
线段树是一种树状数据结构，它可以区间加减，区间乘除等一系列操作，用于处理那种可以合并状态的数据，在使用其 3 倍左右的空间的代价下使得其修改、查询、求区间和等等操作变得更加快捷。但与此同时，我们无法利用它处理类似于区间最长 01 序列此类问题，而且线段树代码冗长，其实很容易写错（也可能是因为我太菜了）。
我们将一组数据进行如下处理，每相邻的两个数据有一个父亲节点来记录其总的状态，然后再记录其相邻父节点的总的状态，以此类推，最终得到一个树状结构，我们从上到下依次编号 1-n，这棵树满足父节点 * 2 = 左节点，父节点 * 2+1 = 右节点，设每个父节点代表 l-r 区间的状态，则左区间为 l,(r+l)/2 , 右区间为 (r+l)/2+1,r。根据此性质我们可以对他们进行维护。
每当我们访问一个节点，我们保证此节点的值一定正确，并尽可能少的改变其子孙节点的值，让时间消耗尽可能的小，同时把 lazy 标记也就是本来应该加的数传递到下一节点。
第一颗树实现了区间加与查询，第二颗树实现了区间乘法，加法，判断其中的先后顺序，其实也大同小异。
第三颗树用于实现历史最大值这种操作，然而由于本人电脑跑不动 500mb 的程序，再加之修改起来有点麻烦，就写个大致正确的程序摆在这了。
如果要继续完善，那么需要记录次大值并对于 spread 函数进行修改，就这样吧，后面再来补。
