唐龙题不知道为什么有 2600。此处应有[对称唐龙.gif]。

首先，把 $a_i=i$ 的序列 $a$ 变成给定序列显然是难做的，考虑将目标序列进行某种映射，转化成将 $a$ 变成 $a_i=i$。

然后发现，对于每个数字，只有对其的最后一次操作是有用的，并且进行放到开头的操作的数字一定是某个 $[1,i]$ 内的所有数，并且依次进行 $i,i-1,i-2,\cdots,1$ 的操作。放到末尾的同理。

这种题稍微联想一下类似的就差不多秒掉了。

对于这种要求一条边的权值和两个点有关的构造，找到一个欧拉回路/环类似物，将一条路径每条边的边权依次设成 $x,-x$，可能会有很好的性质。

令下面的“点权”代表所有相邻边权之和，而不是题目所给的 $c$。

卡到最优解了，这不得写写。顺便讲点实现上的细节。

看起来不会 polylog，观察到是 ynoi 题且 $n\le 10^5$，于是考虑分块。

一个很简单的想法是，如果对于每块能预处理出 $f_{i,j}$ 表示第 $i$ 块，一开始 $v=j$，经过块内的所有变换会变成 $f_{i,j}$。考虑怎么对于每个块 $O(n)$ 预处理。

提供一个更臭一点的 $O(n)$ 做法。

首先分析，如果现在已知 $A$，怎么求 $f(A)$。首先贪心地想，设依次操作 $v_i$，若 $v_{i+1}<v_i$，那么换成先操作 $v_i$ 再 $v_{i+1}$ 一定不劣，因为可能的结果后者包含前者。于是一定是按 $v$ 从小到大操作。

然后发现，对于一个 $a_i=a_j=x$，若 $\exists k\in(i,j),a_k<x$，则无法用一次操作同时使 $a_i,a_j$ 满足要求，否则会影响中间已经确定的数。同时，若 $a_i$ 这个数是第一次出现，显然也要一次操作。

非常好的题！赞美出题人。具体讲讲如何想出来这种题。

容易发现直接做非常难做，一是数据范围非常之大，二是这本身就是相当于一个重排一个序列的问题，计数也很困难。

这种题就大概率要从找性质入手（类似 P2150 寿司晚宴），于是先观察样例及解释，如果你注意力比较集中的话，会注意到，$n=3$ 时就已经出现了很多重复的答案值了。

看到这题不知道为什么第一反应是 flow。

先把每个数质因数分解，然后问题就变成了让选出的集合无交。

如果此时像我一样，发现是分成两个集合，就往最小割的方向想，就到死路了。主要是最小割就要求每两个不互质的数间都要加一个限制，无法优化。

如果你做过 CF79D 你就会把这题秒了。

记 $A+B+C+D+E=m$。

首先区间反转差分一下变成两个点同时反转，然后发现原序列差分序列上只有 $4$ 个 $1$，于是把反转转化成差分数组上 $1$ 的移动。

好题，随机讲讲。

首先期望转 LIS 长度和除以方案数。LIS 这个东西不好刻画，但是发现 $n=6$ ，所以考虑直接枚举每个数排名，也就是枚举 $X_i$ 离散化后的序列。

然后考虑知道这个序列之后怎么求方案数。先想一个弱化版的问题：有 $m$ 个数，已知他们的排名，每个数的取值范围为 $[1,k]$，$k$ 为定值。求方案数。答案显然是 $\binom{k}{m}$。

*2600？*2100！

考虑一个位置 $i$，考虑什么时候交换 $x,y(x<y)$ 位置的数，它会对答案有 $1$ 的贡献。

阅读全文 »

讲的题，但是没听而且感觉挺有意思而且见过类似的，于是自己做出来了。

首先有关键性质：若最大距离的同色点对为 $u,v$，树上的任意一条直径 $(s,t)$ 满足 $s=u,s=v,t=u,t=v$ 其中至少一个成立。

证明：反证。若有一条直径两端点为 $s,t$ 且 $u,v$ 不是任何的一个 $s$ 或 $t$，$s,t,u,v$ 互不相同，钦定 $dis(s,u)<dis(t,u)$，则 $col_u\not=col_t$。同时，因为 $(s,t)$ 为直径，$dis(u,t)<dis(s,t)$，$dis(u,v)<dis(s,v)$，于是 $col_s\not=col_v$，又 $col_u=col_v$，则 $col_s=col_t$，此时显然 $s,t$ 同色且距离更远，不成立。

好久没写过 AC-Automaton 了。来一发。

有个显然的 dp 为 $dp_i=\max(dp_j+w[j+1,i])$，其中 $w[l,r]$ 表示字串 $[l,r]$ 对应的模式串的价值。时间复杂度大概是 $O(|S|\sum|P_i|)$ 的。显然不能过。

考虑这种有一个文本串，很多模式串匹配的题一般怎么做，容易发现可以用 AC-Automaton 维护。

记录一下这道感觉非常神的 daily problem。讲思路。

下文 $1$ 表示亮，$0$ 表示不亮。

首先，操作到一个固定状态显然是比操作回全 $0$ 难做的。于是把操作逆过来。

偶然找到的线性基好题。

考虑 $s=\bigoplus x_i$，则此时 $b=s\oplus a$，问题变为 $\max(a+(s\oplus a))$。

然后观察 $s$，有一个很典的想法是，$s$ 为 $0$ 的位上，$a$ 如果是 $0$ 则会产生 $0$ 的贡献，否则产生 $2$，$s$ 为 $1$ 的位则稳定产生 $1$ 的贡献，结合异或本质理解。

大常熟另类做法。不用排序。

要求直径长度，则想到把直径这一条链拎出来处理。然后考虑其他边会接在哪里，发现树最优情况下一定是一个毛毛虫的形式。更进一步，所有边都挂在接近直径中点的点上。

然后再考虑这些不在直径中的，长度为 $l$ 的边带来的限制，设直径为 $d$，从每个点将直径切成两半，记其中一段为 $c_i$，则有 $\max(\min(c_i,d-c_i))\ge l$。

非常好题目，使我的大脑旋转（？）

还是一样，介绍思路。

既然题目让我们计算 $f_{\max}(n)$ 的数量，则先考虑 $f_{\max}(n)$ 的值怎样求得。容易发现，设 $n=\prod p_i^{k_i},p_i\in \operatorname{prime}$ ，则 $f(n)=\sum k_i+1$。注意是 $f(n)$ 不是 $f_{\max}(n)$。简单贪心，发现当 $x=2^m$ 时，$f(x)$ 会尽可能大。

好像是一种不一样的建模方法。

首先我们会做只有 $a$ 的情况：每个 $i\to a_i$ 连边，答案即为 $n-cntc$，其中 $cntc$ 为环的个数。

考虑加上 $b$ 后怎么做。考虑补集转化，每个环内可以选一个数，不去操作它，只操作其他的，它也可以自动归位。此时问题就变成：给你一个长度为 $n$ 的 $01$ 序列和 $m$ 个性质，形如集合 $S$ 中每个位置，其中最多只能有一个 $1$。

cdqz 两道题都很有意思啊！顺便是第一篇 *3500 题解。

先考虑第一问。

显然有单调性，所以可以二分。cdqz 这是二分专题吗

感觉，有时候把问题往网络流上想，不失为一种好的思路。

我们考虑 $(i,j)$ 上填一个 $c$ 的意义。则第 $i$ 行和第 $j$ 列需要填的和都会减少 $c$。如果把他看作是一条 $(i.j)$ 之间的边，问题就变为：在两个点集之间连边，可以有重边，$a_{i,0/1}$ 表示第 $1/2$ 个点集的第 $i$ 个点度数为 $a_{i,0/1}$，匹配的方案数。

此时发现值域只有 $3$，并且知道总数和其中一个就可以推出另外两个。联想到 AT_dp_j。从前往后匹配 $a_{i,0}$，$dp_{i,j}$ 表示考虑第一个点集的前 $i$ 个点，第二个点集中还剩 $j$ 个 $1$ 没匹配。转移是 naive 的，可以参考代码。

首杀问号题，虽然没有问号题的难度，但是至少是自己想出来的。

对于操作一和二，我们直接用分一个数组记录下来，$O(nq)$。

对于操作三，我们思考怎么样通过上面记录的信息处理答案。发现对于一个矩形，只要确定了 $x+y$ 的值，$x-y$ 的值就是一个区间，因为矩形的约束可以变成 $2\times A\le(x+y)+(x-y)\le 2\times B,2\times C\le(x+y)-(x-y)\le 2\times D$。这启示我们可以类似莫队，维护两个指针。

首先看到题目，容易想到一个简单很多的情况：在一条链上，且终点确定。此时就可以把终点两边的点分开，分别计算到终点的距离之和，看是否相等即可。

没有确定终点时，枚举一个终点即可。

考虑将这种做法带入本题。先 $O(n)$ 枚举终点，然后会发现，这其实是一个判定问题：如果可以全部到终点，那么答案就是 $\dfrac{\sum_{c_i=1}dep_i}{2}$。这一点下面会证明。$c_i$ 表示点 $i$ 上是否有棋子。