首先考虑暴力:枚举所有的 (x,y)(x,y)(x,y),同时包含 x,yx,yx,y 的区间mex必然不变,因此我们只需考虑仅含其中一个的区间。
设 lmilm_ilmi 为 [1,i][1,i][1,i] 的mex,rmirm_irmi 为 [i,n][i,n][i,n] 的mex,这两个数组可以通过正逆序枚举 O(n)O(n)O(n) 得出。那么简单推导可知成立的充要条件为:
rmi+1≠ai,lmj−1≠aj,lmj−1<ai,rmi+1<ajrm_{i+1} \neq a_i,lm_{j-1} \neq a_j,lm_{j-1}<a_i,rm_{i+1}<a_jrmi+1 =ai ,lmj−1 =aj ,lmj−1 <ai ,rmi+1 <aj 。
其中前两个条件只与一个量有关,可以 O(n)O(n)O(n) 预处理打tag标记(即不满足的直接不考虑)。对于第三个条件,不难注意到一旦 lmk≥ajlm_k \ge a_jlmk ≥aj ,则对于所有的 l≥kl \ge kl≥k 都有 lml≥ajlm_l \ge a_jlml ≥aj ,这时 k−1k-1k−1 就是对于这个数能够满足要求的极限位置。因此我们可以预处理出数组 limilim_ilimi 表示每个数的极限位置(方法是桶排记录 aia_iai 下标后双指针处理)。对于 rmrmrm 同理。处理完后,对于每个 aia_iai 只有
[i+1,limi][i+1,lim_i][i+1,limi ] 这段区间的点可能满足条件(即与之形成稳定化子)。
接着考虑最后一个条件。不难发现我们要求的是 j∈[i+1,limi]j\in[i+1,lim_i]j∈[i+1,limi ] 中满足 aj>rmi+1a_j>rm_{i+1}aj >rmi+1 的个数,我们可以用值域树状数组记录每个合法的 aia_iai ,扫描线处理。注意这只能统计到半边的答案,需要倒序再扫描线一遍,这时我们需要以最后一个条件为基础,将第三个条件扫描线。