前言
场上调 DS 调不出来。/hsh
这篇题解使用吉司机线段树，不是正解的 set 维护。
题意描述
给两个长为 n 的序列 a,b，序列 c 满足 \forall i\in[1,n],c_i=a_i \operatorname{or} c_i=b_i。
对于 i=1\dots n 分别求 c_{1\sim i} 的极差的最小值，极差即 \max\limits_{j\le i}c_j-\min\limits_{j\le i}c_j。
### 解法
先令 $a_i\le b_i$（$a_i>b_i$ 则交换），这样对答案不影响。
从小到大枚举 $2n$ 个可能的最小值，设当前最小值为 $mn$。
限制就是 $c_i\ge mn$，可以贪心。
- $a_i\ge mn$，选择 $c_i=a_i$ 一定比 $c_i=b_i$ 优。
- $b_i\ge mn>a_i$，只能选择 $c_i=b_i$。
- $mn>b_i$，选不了，只能更新 $k<i$ 的答案。
用一个指针维护最大的 $k$ 使得 $\forall j\le k,b_j\ge mn$，$mn$ 只更新 $1\sim k$ 的答案，就不会第三种情况。
由于从小到大枚举 $mn$，对于某个 $c_i$，一开始 $c_i=a_i$，在某个时刻 $mn>a_i$，这时候 $c_i\gets b_i$。
可以指针扫一遍维护出来到 $mn$ 时更新的 $c_i\gets b_i$。
知道了最小值，需要最大值 $\max\limits_{j\le i} c_i$ 更新答案。
于是暴力 $O(n^2)$ 就是 $i\le k$ 的点的答案用 $\max\limits_{j\le i} c_i-mn$ 更新。
直接维护出 $c$ 的前缀 max 数组 $d$，$d_i=\max\limits_{j\le i} c_i$，用 $d_i-mn$ 更新 $i$ 的答案。
对于 $c_i$ 从 $a_i$ 变成 $b_i$ 的一次修改，$c_i$ 一定变大，对 $d$ 的影响为 $\forall j\ge i,d_j\gets\max(d_j,b_i)$。
修改是区间取 max，更新答案形如历史最小值，力大砖飞，直接用[吉司机线段树](https://oi-wiki.org/ds/seg-beats/)维护。
时间复杂度 $O(n\log^2 n)$，但是跑得很快。
代码太丑不放了。