冒泡排序

题意：

给定$a_1,a_2,...,a_n$和$m$个三元组$(l_i,r_i,s_i)$。

每个三元组对应如下函数，修改$\{a_n\}$中的元素并返回一个布尔值。

def bubble(l, r, s):
    for i in range(s, n + 1): # s <= i <= n
        if l > a[i]:
            l, a[i] = a[i], l
    return l <= r

判断是否存在$1\sim m$的排列$\{p_m\}$，使得依次执行三元组$p_1,p_2,...,p_m$对应的函数，函数总是返回“True”。

分析：

牛逼题。

考虑 $m=1$ 的情况，此时如果我们所有的数按照 $w$ 来划分，小于等于 $w$ 的数为 $0$，大于 $w$ 的数为 $1$，这里 $w=r$，可以发现，这样转化后函数的返回值一定是正确的。

那 $m \ne 1$ 呢？不难发现当 $w$ 作为划分界限来检验的次数足够大，并且每次不同的 $w$ 都返回 $True$ 时，最终一定也是返回 $True$，这利用了一个相对关系。

现在考虑给定一个 $w$，需要安排一个最优的顺序。显然只有四种情况。

$bubble(0,0,s)$
$bubble(0,1,s)$
$bubble(1,0,s)$
$bubble(1,1,s)$

显然前两种情况，既不会修改序列，又一定返回 $True$，因此随便放。第四种情况，一定返回 $True$，但会修改序列，使得序列更劣，所以放在最后。第三种情况只需要放在第四种情况的前面即可。

第三种情况内部的顺序呢？其实无关紧要。每次抢后面的 $0$，如果一个数抢不到，那么无论怎样变换顺序都抢不到。

综上，按 $r$ 从小到大排序一定是最优的安排顺序。

现在需要更改 $w$，显然 $w$ 是从小到大枚举，并且取的 $w$ 一定必须是能修改序列或者 $l,r$ 的。这样的 $w$ 只有 $n+2m$ 个。

怎么判断所有第三类操作从 $s$ 开始找后面都必定有一个 $0$ 给它用呢？

只需要保证每个位置的后面的第三类操作的数量小于等于后面 $0$ 的数量，即判断两者之差是否小于等于 $0$ 即可。

用线段树维护一个后缀，并使用扫描线的思路，当 $w$ 移到 $a_{i}$ 时，$t[1],t[2],...,t[i]$ 的 $0$ 的个数就会多 $1$。

在 $l>r$ 的情况，在 $w$ 移到 $r$ 的时候，$t[1],t[2],...,t[s]$ 的第三类操作的数量也会多 $1$，在 $w$ 移到 $l$ 的时候，$t[1],t[2],...,t[s]$ 的第三类操作的数量就会少 $1$，因为 $bubble(1,0,s)$ 退化成 $bubble(0,0,s)$。

因此只需要维护区间加，全局最小值查询即可。

时间复杂度 $O(n+m) \log n$。

上升序列

不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。不会。

地铁换乘

题意：

有$n$个地铁站和 $m$ 条地铁线路。给定 $n \times m$ 的 $01$ 矩阵 $a$，第 $i$ 条地铁线路连接所有满足 $a_{j,i} = 1 $ 的地铁站 $j$。每条地铁线路连接的地铁站可以互相到达。

找到最长的区间 $[l, r]$ 满足 $∀i, j ∈ [l, r]$，$i$ 可以仅经过编号为 $l, l + 1, · · · , r$ 的地铁站，通过若干次换乘到达 $j$。

分析：

有点恶心！

一种简单的暴力做法是，枚举左右端点 $l,r$，然后用并查集实时维护联通块数量。

考虑如何优化，注意到 $m \le 500$，可以把每条线路看成一个点，连接两条线路的地铁站看成一条边。具体的，把存在于 $[l,r]$ 内的所有点（路线）看成一个图的点集，把 $[l,r]$ 内的所有地铁站所构成的边看成一个图的边集，$[l,r]$ 为符合答案的区间当且仅当联通块数量为 $1$。

证明：

增量法。考虑 $[l,r]$ 为合法的时候，由于题目保证每个地铁站内有至少一条地铁线路，那么 $[l,r+1]$ 必定会产生一个点，记它为线路 $L$。如果 $[l,r+1]$ 是联通的，也就是存在一条线路经过 $x$ 与 $r+1$，即存在 $L$ 与 $[l,r]$ 的一条边，这是充分性。如果不存在这样的一条边，即 $L$ 不会相交于 $[l,r]$，这是必要性。