大家好，我不会平衡树，所以我用线段树过了这一题。

其实就是一个 trick：SGT 不能维护插入操作，于是离线处理：先求出序列最后长度，再倒着做所有插入操作（可以将一开始的序列也视作若干次插入）。

先将序列上每个位置标为 $1$，于是插入到第 $x$ 个数后面就变成了线段树上二分，找到第一个前缀和为 $x+1$ 的位置，于是在最终序列中，这个数就是在这个位置，并将这个位置标记为 $0$。

来点另类思路！

首先考虑暴力地做：发现 $L$ 非常大，于是大概率是要矩阵快速幂，求出最后的邻接矩阵的。如果对暴力处理出所有 $T$ 次操作后的最终矩阵，复杂度为 $O(Tn^2\log L)=O(n^4\log L)$。（其实一开始想到了题解区中的 $O(\frac{n^4\log L}{\omega})$ 做法但是我不觉得能过）

但是你发现一个问题：每次只改变一条边，我们会做很多冗余计算。于是考虑把矩阵乘法计算过程列出来，一开始全是 $0$，后面在某一时刻，某些位置可能会变成 $1$，变成 $1$ 的位置后面也不会变成 $0$，于是可以不用管它了。

模拟赛题。赛时暴力被放过了。

考虑如下 $O(n^2q)$ 暴力：将询问区间拎出来成一个序列并排序，设 $dp_{i,j}$ 表示前 $i$ 个数，已经钦定了 $j$ 个位置 $a_i=p_i$。转移是 naive 的，枚举当前位置是否钦定即可。因为有重复数字所以再加一维 $0/1$ 表示当前相同数字是否选过。最后乘上没钦定的数量的阶乘。

然后考虑优化。考虑分治，因为不同的数字之间不关联，考虑将前后两半出现过的不同元素数平均。然后考虑合并两边答案，会发现要进行的操作类似 $dp_{l,i}\times dp_{r,j}\to dp_{r,i+j}$ 。是卷积形式，使 NTT。单次时间复杂度是 $T(n)=2T(\frac{n}{2})+O(n\log n)=O(n\log^2n)$。总复杂度为 $O(nq\log^2n)$。可能需要一定卡常。

现在题解区只有一篇 $O(n\log n)$ 做法，而且是闵可夫斯基和，完全不会。于是讲另一种 $O(n\log n)$ 做法。

首先写 $O(n^2)$ 的树形 dp：设 $dp_{u,i}$ 为处理完 $u$ 的子树，现在 $u$ 处挂着一条长为 $i$ 的链，答案的最大值。这里包含 $(u,fa_u)$ 这条边。

转移的话，对于一个 $u$，设 $f_{i,0/1,0/1/2/3}$ 表示当前已经枚举到的 $u$ 的儿子中，选长度为 $1$ 的和长度为 $3$ 的链的数量的差为 $i$，选了偶数/奇数个长度为 $2$ 的，钦定 $u$ 处挂着一条长度为 $0/1/2/3$ 的链。每次枚举到一个儿子就根据这个儿子处挂一条长度为多少的链转移。

没人写题解，丢一篇来。

首先容易发现，若 $P$ 某些对应位置的限制之间有矛盾，则 $f(P)=0$，否则设 $c$ 为其中元素数量，则 $f(P)=m^{m-c}$。

发现 $Q_{P_i}=P_{i-len+1}$ 这样的限制相当于，每个在序列中的元素都和与它对称位置的元素形成双射。对称位置，很难不联想到回文串。回文串上的计数问题，很难不想到 manacher。

来个单调栈+SGT 做法。

首先题意显然可以转化为求所有 $b$ 的前缀和的最大值加上最大子段和。求前缀和的最值的和是简单的，这里不细讲，维护个单调栈二分即可。

考虑怎么求所有区间 $[l,r]$ 的最大子段和之和。考虑从大到小枚举 $l$，对于每个 $r$ 维护两个值，$f_j$ 表示 $[i,j]$ 内的最大子段的左端点，$w_j$ 表示 $[i,j]$ 内的最大子段和。显然 $l_j$ 和 $w_j$ 都是单调不减的。

一个跑了整整 3900ms 的做法。

考虑如果当前有一个状态 $A$ 能在和不超过 $lim$ 的前提下到达一个状态 $B$，则 $B$ 在同样条件的前提下也能到达 $A$。

于是对于初始状态 $S$，会发现最优策略一定是先把和变得尽可能小，达到状态 $R$，以此让某些要经过很大值的点通过，然后再变成结束状态 $T$。

提示，下文中有较多变量名重复，请注意自行理解。

其实一步一步做还是感觉不难的，可能这就是 ARC 吧。（

先手玩一下，看看两边会如何操作。首先，设分成第 $i$ 个段的第 $j$ 位为 $b_{i,j}$，那么对方肯定会贪心地把 $b_{i,1}$ 最大的 $i$ 段给放到开头，而所有的 $b_{i,1}$ 不相同，所以设最后对方放的第 $i$ 个段的第 $j$ 位为 $c_{i,j}$，则 $c_{1,1}\ge k$。所以我方就要贪心地，使 $b_{i,1}$ 取到当前剩下的最小的 $k$ 个数。

来个抽象点的做法。

首先显然可以将条件转化成，将 $[l,r]$ 中的边从大到小加入一个图中，找出加入哪条边后不是一个二分图。显然可以用一个拓展域并查集维护。

观察到朴素暴力是 $O(nm)=O(n^3)$，几乎已经能过了（其实就是能过）。于是考虑进行一些小的处理，把它变成实际上就是能过的。

一些符号：$\color{blue}\Diamond$ 表示从中很有收获的题，$\color{blue}\Box$ 表示差不多会，参考题解做出来的题，$\color{blue}\triangle$ 表示完全不会，看题解才会的题，$\color{blue}\nabla$ 表示之前改的题。在题解中穿插表示具体部分。

[ARC104C] Fair Elevator (*2009)

考虑有一个区间 $[l_i,r_i]$，钦定没有另一个区间 $[l_j,r_j]$ 满足 $l_j<l_i\wedge r_j>r_i$。考虑 $l_i+1$ 位置对应的右端点，一定为 $r_i+1$。于是确定了 $[l_i,r_i]$ 就可以确定 $[l_i+1,r_i+1]\cdots [r_i-1,r_i-1+r_i-l_i]$。

感觉这题比赛时反应出来的简单。

首先容易发现一个性质：如果有 $a_i<a_j,a_j<a_k$ 且 $i,j,k$ 两两连边，那么 $(i,k)$ 这条边是完全没用的，因为会直接被 $(i,j),(j,k)$ 代替。

这启发我们先按照 $a_i$ 升序排序。对于每个区间 $[l_i,r_i]$，我们先看之前有哪些区间 $[l_j,r_j]$ 和这段区间有交。根据上面的性质，我们只用考虑其中 $a_i$ 最大的。也就是说，如果一个区间 $[l_j,r_j]\cup[l_i,r_i]$ 被 $[l_k,r_k]\cup[l_i,r_i]$ 所包含且 $a_k>a_j$，则 $i$ 不会向 $k$ 连边。然后发现这就相当于每次区间覆盖，向区间内出现过的数连边。

出题人题解。

Sol 1

首先有个一定需要的 $O(n^2)$ dp：设 $dp_{u,i}$ 表示当前在 $u$ 点，钦定选的链上点权一定不包含 $i$，此时的最小代价。转移是非常简单的，只要看当前链是否在这里断开即可。而且 $\operatorname{mex}$ 性质是很好的，如果此时转移的 $i$ 并不是 $\operatorname{mex}$，也一定不会成为最优解，而是真正的 $\operatorname{mex}$ 会成为最优解。于是这么做是正确的。

首先，我们可以想想对方怎么让我们必败。因为最后要组成排列，所以对方可以一直让我们取不到一个数。

所以，我们需要每一个数都在某一个位置上“一定取得到”，即对于每一个 $x$，都存在一个 $i$，使 $a_i,b_i,c_i$ 中，至少有两个为 $x$。

那么要如何计算方案数呢？我们会发现，如果 $a_i\ne b_i$，那么对于这个 $i$，能“一定取得到”的只能是这两个数中的一个。于是我们可以建出一张图，对于每个 $i$，在 $a_i$ 和 $b_i$ 之间连一条边。每次确定一个 $c_i$ 就相当于是删掉点 $c_i$ 以及它的一条边。答案就是删的方案数。（无序）

一道很好的锻炼推式子能力的题，也是本蒟蒻第一道一遍过的紫题。

既然是递推，那就先定义一下状态：$f_i$ 表示在执行完第 $i$ 个操作后，可能得到的字符串数量。

很明显，我们需要分两种情况讨论：这次操作为添加字符或退格。

对于每次询问，我们可以看成是两个点都不断往上跳（如果一个点是另一个点的祖先则是只有一个跳），有一个很明显的贪心策略：每次都跳到能跳到的深度最小的点。然而一次一次往上跳可能被极端数据卡掉，所以要用倍增维护跳 $2^i$ 次能跳到哪里。

然而两个点都跳到他们的 lca 上并不一定是最优方案，所以可以让两个点都跳到差一步能跳到 lca 的位置，然后判断是否有一条路直接联通两个点。对于这个问题，我们可以处理出 dfs 序，将每一条公交车线路看成是坐标系上 $(dfn_u,dfn_v)$ 的一个点，每次询问就是判断左下角是 $(dfn_u,dfn_v)$，右上角是 $end_u,end_v$ 的矩形内是否有点，其中 $end_i$ 表示 $i$ 的子树中点的 $dfn$ 的最大值。可以转化成二维偏序问题，用树状数组维护。其中要特判一下一个点是另一个点的祖先的情况，直接跳即可。

code：

一种更简单的想法，只用用分块思想（或者根号分治？）不用分块。

先考虑暴力怎么做：修改直接改，查询不停跳下一个点。但这样会被卡到 $O(n^2)$。

考虑分块思想优化：如果保证每次至少跳 $\sqrt n$

挺高妙的题，思维套结论。

题意：给定 $n$ 个数，求在其中选三个不交的子集，使得其异或和相等的方案数。

三个不交的集合异或和相等 $\Leftrightarrow$ 两两异或和为 $0$。