有一个序列，序列中的每一个元素有两个值$h_i$与$val_i$。你需要回答若干次询问，每一次询问针对于一个区间$[l,r]$，设$l\le p_1<p_2\cdots p_k\le r$，其中$p_k$是$[l,r]$中$h_i$最大的位置，$p_{k-1}$是$[l,p_k-1]$中$h_i$最大的位置……你需要回答出这些位置的$val_i$的某些可以区间合并的信息（和/最大最小值……）。
可以对序列中元素的$h_i,val_i$进行修改。
序列中一个区间的$p_1,p_2\cdots p_k$（我们暂且称这个东西为单调栈吧），和整个序列的单调栈，相比起来唯一的区别，就是这个区间的单调栈中最左边的若干个元素（甚至有可能是所有的元素），可能在原序列中由于在这个区间的左边有更大的元素而被弹掉了。
设$query(l,r,p)$表示对于区间$[l,r]$，我们在它的单调栈左边加入$p$之后，会得到的单调栈信息。设$mxh(l,r)$表示$[l,r]$中$h_i$的最大值。
1）假设$mxh(l,mid)<p$，那么我们需要的信息是$query(mid+1,r,p)$。
2）否则，我们需要的信息是$query(l,mid,p)+query(mid+1,r,mxh(l,mid))$。
注意到这里的$query(mid+1,r,mxh(l,mid))$和$p$并没有任何关系，所以我们在线段树的每个节点上存下来就可以了。这样对线段树上的一个完整区间（线段树上有一个节点恰好表示这个区间）查询的复杂度是$T(n）=T(n/2)+O(1)=O(\log n)$的。
然而我们最终要查询的区间不一定是一个完整的区间。它在线段树上会被划分成$O(\log n)$的完整的区间。我们按照从左到右的顺序依次处理这些区间。对于第一个区间我们的$p$取$0$（比所有的$h_i$都要小的值），对于第$i$个区间，我们取第$i-1$个区间我们取的$p$和第$i-1$个区间的$maxh$两者中的较大值。这样查出来的信息的和就是整个区间的单调栈的信息。查询每个完整区间的复杂度是$O(\log n)$，所以查询的总复杂度是$O(log^2 n)$。
对于单点的修改，直接暴力改就可以了。然后我们需要重新计算$O(\log n)$个区间的$query(mid+1,r,mxh(l,mid))$。因此，修改的复杂度是$O(\log ^2 n)$的。
模板与例题
jzoj5402 God knows
有一个$1$到$n$的排列$p_1,p_2\cdots p_n$。平面内有$2n$个点，它们（像二分图一样）排成两排。第一排的点的坐标是$(1,0),(2,0)\cdots (n,0)$，第二排的点的坐标是$(1,1),(2,1),\cdots (n,1)$。第一排的第$i$个点和第二排的第$p_i$个点之间有一条线段。你可以花费$c_i$的代价删除第$i$个点与第$p_i$个点之间的连线，并且删除所有与这条线有交的线段。问最少需要多少的代价，才能够把所有的线段全部删掉。$n\le 10^5$
Solution：
考虑一种$O(n^2)$的$dp$：设$f[i]$表示前$i$条线全部被删除，并且我们选择了第$i$条线的最小代价，那么有
那么，我们对于$i$，我们可行的转移点$j$一定满足对于所有的$p_k\in (p_j,p_i)$，$k$一定都小于$j$。这是一个区间$[1,p_i]$的单调栈，可以用线段树维护。
1 |
|
练习题：
HNOI2018 转盘
排序二叉树