区间在线逆序对板子。

块内分别记录下排序后的结果，并对每个块分别预处理，块内所有前缀和后缀内逆序对个数，以及对于每个 $k\in[1,n]$，块中有多少大于等于 $k$ 的数。

这样就可以很方便求出 $f_{i,j}$ 表示有多少这样的逆序对，使得第一个数在前缀 $[1,j)$ 中，第二个数在块 $i$ 中；$g_{i,j}$ 表示有多少这样的逆序对，使得第一个数在块 $i$ 中，第二个数在后缀 $[j,n)$ 中。对于每个块我们只需要考虑与其不交的前/后缀即可。

然后我们将所有逆序对分为四种：

• 两个数在同一块内，$O(\frac nB)$ 对所有整块，以及两个散块的前后缀和求和得到；
• 第二个数在整块内，讨论第二个数在哪个整块，那么第一个数就被限制在一个区间内，将区间表示为两个前缀相减，通过 $f$ 求出；
• 第二个数在右端散块内，第一个数在整块内，讨论第一个数在哪个整块，第二个数就被限制在右端散块这个区间内，表示为两个后缀相减，通过 $g$ 求出；
• 第二个数在右端散块内，第一个数在左端散块内，对两端块排序过后的数组双指针统计。

如果询问的区间完全被包含在一个块内，考虑容斥，设块左端点为 $t$，用 $[t,r)$ 内的逆序对数减去 $[t,l)$ 内的逆序对数和左端点在 $[t,l)$ 且右端点在 $[l,r)$ 内的逆序对数集合即可，其中前两部分已经预处理过，第三部分可以对该块排序后的数组进行简单的统计。

转化题意：给定一个图，每条边有边权 $(a,b)$，多次给定 $u,v,x,y$，询问 $u$ 到 $v$ 中是否存在一条路径 $p_0,p_1,\cdots,p_k$，使得 $\max_{i=0}^na_{p_i}=x$ 且 $\max_{i=0}^nb_{p_i}=y$。

首先抛开相等的限制，单是考虑所有所有 $a_i\le x,b_i\le y$ 的边 $i$ 是否能够连接 $u,v$。这是一个类似二维数点的问题，但是它不能将边划分为两个集合，分别求得答案后相加，也即答案在元素集合维不具有可加性。于是无法 CDQ 分治。

考虑分块用并查集维护连通性。边按照 $a$ 排序，分块，并依次处理。将询问按照 $a$ 分到不同的块中，发现所在块之前的所有块内的边 $a$ 限制一定满足，之后的所有块内的边 $a$ 限制一定不满足，所在块内的边可以暴力处理。

先考虑每个块处理时，它前面的所有块。这些块只需要考虑 $b$ 限制。故维护这些块按照 $b$ 排序的结果，每处理完一块就归并进去。块内询问也按照 $b$ 排序，双指针扫，即可线性将每个块之前的所有块中合法的边加入并查集。

对于每个询问，处理完前面所有块之后，加入本块中满足条件的所有边并判别连通性。注意到这些块内边并不具有单调性，在前面询问涉及到的边不一定在后面询问中出现过，所以需要在处理完后撤回（实际上这就是回滚莫队）。

想起来我们起初将“路径上权值最大值等于 $x$”的限制弱化为“路径上所有边权值不超过 $x$”，这里的处理也很简单，并查集维护连通性的同时分别维护连通块内所有边 $a,b$ 的最大值。注意在往并查集中加边时，无论边的两个端点是否连通，都需要更新最大值；只有两个端点不连通时，才更改连通性相关的信息。

教主的魔法（区间加 区间查排名）

分块并维护块内排序后的结果，设块长为 $B$。

区间加时，整块打 tag，散块暴力修改后排序。

区间查询 rank，整块二分，散块暴力统计。

这样时间复杂度为 $O(q\log(B)(\dfrac nB+B))$

---

考虑到区间加时，散块中被修改的和未被修改的部分内部，相对大小关系不变，可以 $O(B)$ 归并。

这样时间复杂度为为 $O(q\log(B)\dfrac nB+qB)$，$B$ 取 $\sqrt{n\log n}$ 以平衡复杂度。

由乃打扑克（区间加 区间查第 k）

类似地，分块维护块内排序内的结果，设块长为 $B$。

区间加时，整块打 tag，散块同样 $O(B)$ 归并。

区间查询第 k，通过二分答案转化为查询 rank。

这样时间复杂度为 $O(q\log(w)(\dfrac nB+B))$。

---

二分后，在散块中查询 rank 时可以将至多两个散块归并到一个新数组，从而将查询 rank 的 $O(B)$ 的时间复杂度变为 $O(\log B)$。

这样时间复杂度为 $O(q\log(w)(\dfrac nB\log B+\log B)+q(\dfrac nB+B))=O(q\log(w)\dfrac nB\log B+qB)$，一般近似地认为 $\log w$ 和 $\log B$ 同阶。取 $\sqrt{n}\log w$ 以平衡时间复杂度。

---

二分时可以使用分散层叠减少二分次数，达到 $O(q\sqrt n)$ 的时间复杂度。

见 gxy001 的博客。