冒泡排序
题意：
给定\(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]\)，这是必要性。
考虑如何维护这个东西。仍然考虑 \([l,r]\) 扩展到 \([l,r+1]\) 的改变，会有两类操作是有效的。
- \(r+1\) 新带来的点（线路）。
- \(r+1\) 新连上的有效边（站）。
显然，只有 \([l,r]\) 的有效操作 \(2\)，可能会再次在 \([l,r+1]\) 时有效，而其他 \([l,r]\) 的操作均不可能有效，\(r+1\) 带来的操作也有可能有效。
由于 \([l,r]\) 的连通块最少也就 \(0\)，加上 \(r+1\) 后，如果不做任何改变最少也是 \(2\)，因此只有有效操作（让连通块数量减 \(1\)），才会有可能成为答案，这样的数量在 \(m\) 数量级。
利用并查集时间复杂度为 \(O(nm\alpha(m))\)。
标签：线路,...,地铁站,test1227,True,bubble,不会 From： https://www.cnblogs.com/xcs123/p/17934003.html