一行超人

弱省胡策中大部分题还是很不错的，除了一些报复社会的题目

所以还是补起来比较好。

现在做了几道：

                   6

【#0 A】结论题，戳链接

【#0 B】戳链接

【#0 C】给出$.out$要求构造$.in$。

    第一个类数据给出$MST$上每对点之间的最大权值，要求构造原图。我们把每对点之间的最大权值作为这两个点之间的一条边做一个$MST$就能符合要求。正确性自(wo)行(ye)脑(bu)补(hui)。

    第二类数据给出一个$x^x$，要你输入$x$。注意到这个函数增长速度非常快且输出都不大，所以我们可以打表。有一个不用写高精度的方法就是直接在模意义下判断是否相等就好了。

    第三类数据给出每对点之间的最短路，要求构造原图。和第一类数据一样的思路。我们从小到大往里面加边，如果要加的边的权值>当前两点的最短路，那么加进去，并且更新其他点对儿之间的最短路。否则忽视。正确性参加第一类数据。

    第四类数据给出一个树分块的方案，要求构造原树。注意到可以随意构造，那我们把每条链都连到$root$上面好了。每一个块我们可以分成两部分，$root$所在的块特殊处理一下。另外还要注意遍历的顺序。

    第五类数据给出一个$1-n$的排列，分成了若干块，告诉了你若干块内的某大的值。要求构造出一个排列。我们根据限制从小到大塞一遍，再从大到小塞一遍就好了。这样显然正确。

【#1 A】首先容易想到的是线段树套$AC$自动机，但是此题卡内存。但是此题支持离线算法。所以我们可以先给需要查询的区间打上标记，然后遍历线段树的节点。每建一棵$AC$自动机就把这个节点上的询问全部干掉。这样就没有空间问题了。出题人的解法使用$LCT$维护$AC$自动机的$size$域。这样一个节点不能走当且仅当$size=0$.复杂度我并不知道靠不靠谱。反正出题人很丧病就是了

【#1 B】显然按一维排序之后就成了查询三维空间中某个区域的最大$dp$值，$K-Dtree$即可。也可以$CDQ$分治套$CDQ$分治。

【#1 C】首先需要注意到一个性质，第$k$大的连通块一定是前$k-1$个中的某个连通块加了一条边之后产生的。证明显然。于是我们可以考虑维护任意时刻所有连通块可以拓展出来的下一个状态。可以用可持久化堆来实现。具体题解可以参加laekov 另外$get$了左偏树的新姿势，我们直接用$size$而不用到XX的最短距离也可以保证复杂度。别问我为什么。还有我想问有没有学长二分