单调数据结构小结

复建的第一步!虽然仅仅水了一些单调栈和单调队列的题

abc262 F

https://atcoder.jp/contests/abc262/tasks/abc262_f
根据字典序,找出k能到达的范围内最小值lead.如果选择转动操作,需要转动的点仅在lead后方.这样仅用分两种情况讨论,直接删和转后再删.对于直接删的情况,维护一个单调栈,每次更新时执行删除操作.

For(i,1,n){
        while(p&&ar[i]<ar[sta1[p]]&&r)--r,--p;
        ++p,sta1[p]=i;
    }

如果旋转,旋转后的点删除不需要花费

1
2
3

while(p&&ar[i]<ar[sta2[p]]&&(r>=(sta2[p]<ld)))
    r-=(sta2[p]<ld),--p;
++p,sta2[p]=i;

最后比较两个答案的大小即可

某大佬原创题

长度为n的数组 q个询问每次询问给出一个长度L，最大化长度为L的连续子序列的最小值,$n,q\leq5e6,a_i\leq1e9$

对于每个点,可以记录成为min值的区间左右端点并更新答案,同时短区间的答案可由长区间继承.
关于这个做法的正确性,就是考虑是否每个点都对每个区间的答案进行过更新.对于长度大于$len=r-l+1$的区间,即使更新也不会使答案更优,没有必要考虑.对于长度短于$len$的区间,直接从比较过后的长区间继承,可以保证所有短区间都被更新到.
这样答案满足完全覆盖,不存在漏解的情况

1 2	For(i,1,n) ans[r[i]-l[i]+1]=max(ans[r[i]-l[i]+1],h[i]); iFor(i,n-1,1) ans[i]=max(ans[i],ans[i+1]);

luoguP1250

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

首先可以发现若将每一行分别作为常规单调栈矩形计数的问题,并不会影响上下层的结果,并且可以直接继承高度信息.于是就转化为做n次单调栈.
值得注意的是对于相连的等高项的处理,如果l[i],r[i]均只记录第一个更低位置,那么对于等高的i,i+1,这个区间内的矩形会重复计数.所以需要一个严格单调一个不严格来保证不重

while(tp2&&h[st2[tp2]]>=h[j]){
                l[st2[tp2]]=j+1,--tp2;
            }
while(tp1&&h[st1[tp1]]>h[j]){
                r[st1[tp1]]=j-1,--tp1;
            }

HNOI2008水平可见直线

https://vijos.org/d/newbzoj/p/590c9879d3d8a13210993730
这题的本质就是半平面交.先按照斜率对全部直线排序,再依次塞入单调栈.被遮挡可以分为两种情况:1.k相同.那么b更大者一定更优;2.当前直线比栈顶直线位置更优,计算交点位置判断即可.

luoguP2216

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

这题很显然是一个二维的滑动窗口.用n个单调队列维护每一行合法值,再将每一行最值塞进一个维护列的单调队列,每次移动后重置.每个点只会被扫描一次,复杂度$O(n^2)$

xq.reset(),nq.reset();
For(i,1,a) mxq[i].pb(ar[i][rt],rt),mnq[i].pb(ar[i][rt],rt);
For(i,1,n-1) xq.pb(mxq[i].vl(),i),nq.pb(mnq[i].vl(),i);
For(i,n,a){
    xq.pb(mxq[i].vl(),i),nq.pb(mnq[i].vl(),i);
    ans=min(ans,xq.vl()-nq.vl());
}