DUMBLOG

本贴用来记录口糊出来的杂题的思路、做法等。

没有代码，可能有错。

这是一个测试专用帖。

用于测试博客的各个功能。

思路

开一个 set 维护当前有哪些点是区间的左区间。

对于每个有序区间，开一个权值线段树维护，并记录一下该区间是升序还是降序。

每次排序时就将维护这些区间的线段树分裂再合并，最后查一下每棵树再输出就好了。

洛谷P2824 [HEOI2016/TJOI2016]排序。

思路

离线做法

受 01 串排序的启发，我们可以二分答案，将大于等于 $mid$ 的数设为 $1$，小于的设为 $0$，然后排个序。

如果排完序后询问的 $q$ 位置的数仍为 $1$，则 $mid$ 可行。

前置芝士

• 动态开点线段树
• 线段树的一般操作（建树、修改、查询等）

引子

先来个例题耍耍。

给出一棵 $n$ 个节点以 $1$ 为根的树，节点 $u$ 的颜色为 $c_{u}$，现在对于每个结点 $u$ 询问以 $u$ 为根子树里一共出现了多少种不同的颜色。
$n \le 2 \times 10^{5}$。
（没错就是 OIWiki 上的例题。。。）

解析

题目很坑，题中的子段是不能为空的。

其余就是一个比较裸的线段树维护区间最大值，在左右区间是否重合、包含上讨论一下就好了（虽然我调了快一晚上）。

题面

武士藤藤准备击杀地图上的幽灵。

地图为 $n \times m$（行，列）的整点网格图，坐标从左向右从下到上从 $0$ 编号。

开始藤藤可以从地图的任意的左侧进入，最后藤藤将从地图的右侧离开。

藤藤地图上的行进有一些奇妙的性质：

1．藤藤每单位时间会向右移动一单位长度，以尽快从地图上离开。
2．当一只幽灵与藤藤坐标重合，藤藤就会将其击杀。

解析

先说下 Kruskal重构树 是啥。

解析

记录一下每个数前面第一个比它大的和比它小的数的位置，然后从后往前跳。

先把比它大的找到，然后让比它小的在范围内向前跳，跳得越前越好。

每次跳完答案加一。