seq

https://www.cnblogs.com/HLAUV/p/9871768.html

诈骗，区间长度大于 P 时必为 0。

发现 MP^2 以下的都可以接受，直接 PlogP 地塞入 std::set 中查前驱即可。

另一个抽屉原理

https://www.luogu.com.cn/problem/CF1895G

神秘构造

https://www.luogu.com.cn/problem/AT_arc158_d

sort

一个长为 N 的序列，求构造用最少的栈排序，操作有：

序列里的最后一个元素 pop，进入栈 i；

栈 i pop，进入答案序列；

栈 i pop，进入栈 j；
操作 1、3 进行相邻相同项合并后，总数不得超过 5N。（多组数据，sum N<=3e5）

诈骗题，栈至多 2 个。

一个栈就维护一个单调栈即可，判一下是否有序，没排好就要 2 个栈。

2 个栈的做法：维护一个栈为单调栈，当插入一个元素时，小于它的全部进入第二个，再插入新元素，然后把第二个栈的放回去即可。

然而做题要看数据范围，不能线性找有多少个小于，要用树状数组。

template

在二维平面上，有 N 个黑点和 N 个白点，记第 i 个黑点的位置为 (axi,ayi)，记其权值为 awi；同理，记第 i 个白点的位置为 (bxi,byi)，其权值为 bwi。有 Q 次询问，第 i 次询问的范围用 Li,Ri 表示，对于第 i 次询问，需要选择一个黑点 j 和一个白点 k，在同时满足如下条件时，最大化权值之和，即求 awj+bwk 的最大值。

ayj<byk

\((ax_j<L_i\land bx_k>R_i)\lor(ax_j>L_i\land bx_k<R_i)\)
（N<=1e5,Q<=5e5，所有横坐标互不相同，所有纵坐标互不相同）

先考虑第一条限制，对于每个黑点 i，找 w 最大能匹配的白点 j，形成平面 P 上的点 (i,j)。对于每个白点也是。可以分治。

第二条限制，或运算符的两边其实差不多。

第二条限制的或运算符的意义远不止于此。它使平面 P 上至少有一点被选且是答案，这使这道题成为了撅世郝题。