关于双向链表在一道题中的实际应用

link
最后对于数 \(x\)，令 \(x\) 左边第一个比它大的 位置在 \(lft0\)，第二个比它大的 位置在 \(lft1\)。
令 \(x\) 右边第一个比它大的 位置在 \(rgt0\)，第二个比它大的位置在 \(rgt1\)。
那 \(lft1+1\leqslant p\leqslant rgt0-1\)，或 \(lft0+1\leqslant p\leqslant rgt1-1\)。
又 \(rgt0-1 \leqslant lft0+1\)，所以 \(lft1+1\leqslant p \leqslant rgt1-1\)。现在就要找出 \(lft1\) 和 \(rgt1\) 可持久化 trie 即可。然后到这个我们可以冲 \(2\) 棵线段树，也可以开 \(2\) 个 set（我第一次打的），当然这里有 \(\mathcal {O}(n)\) 的双向链表解法。
玛德先咕着，明天中午来搞。