单调队列

单调队列是一种特殊维护的队列。一般地，当一新值准备入队时，须先从后向前，将对后来答案没有了影响的点弹出，再从前向后，将所有超出了统计范围的点弹出。对于大多数问题，求解过程中会锁定很多答案区间，在线求最值。

P3088 拥挤的奶牛

题面

有 $N$ 头奶牛沿着一维的栅栏吃草，第 $i$ 头奶牛在目标点 $x_i$，它的身高是 $h_i$ 。当一头奶牛左边 $D$ 距离内而且右边 $D$ 距离内有身高至少是它的两倍的奶牛，它就会觉得拥挤。

请计算觉得拥挤的奶牛的数量。

解

当一奶牛将要入队时：

• 从后往前，将身高小于该奶牛的弹出（--tail），因为将要进队的奶牛更加靠后，影响范围一定更大，对答案的贡献也一定更大。
• 从前往后，将与该奶牛距离已超过 $D$ 的奶牛弹出（++head）
• 将该奶牛入队。
• 与队头奶牛比较身高，若符合则打上标记，若左右两次统计均符合，则计入答案。

每次统计的是该奶牛左侧的合法性，从后到前再做一遍就可以了。

按照以上规则就可以统计答案了。显然该队列一定为单调递降队列。

代码

#include <stdio.h>
#include <algorithm>
using namespace std;

const int N = 55000;

struct node {
    int x, h;
} a[N];

int n, d, queue[N];
bool l[N], r[N];

bool cmp(node a, node b) {
    return a.x < b.x;
}
int main() {
    
    freopen("p3088.in", "r", stdin);
    
    scanf("%d%d", &n, &d);
    for(int i=1; i<=n; ++i) 
        scanf("%d%d", &a[i].x, &a[i].h);
    
    sort(a+1, a+n+1, cmp);
    
    int head = 0, tail = 1;
    queue[head] = 1;
    
    for(int i=2; i<=n; ++i) {
        while(head < tail and a[queue[tail-1]].h <= a[i].h) --tail;
        queue[tail++] = i;
        while(head < tail and a[i].x - a[queue[head]].x > d) ++head;
        
        if(a[queue[head]].h >= (a[i].h << 1)) l[i] = true;
    }
    
    head = 0, tail = 1;
    queue[head] = n;
    
    for(int i=n-1; i>=1; --i) {
        while(head < tail and a[queue[tail-1]].h <= a[i].h) --tail;
        queue[tail++] = i;
        while(head < tail and a[queue[head]].x - a[i].x > d) ++head;
        
        if(a[queue[head]].h >= (a[i].h << 1)) r[i] = true;
    }
    
    int ans = 0;
    for(int i=1; i<=n; ++i) 
        if(l[i] and r[i]) ++ans;
        
    printf("%d\n", ans);
    
    return 0;
}

P3522 Temperature

题面

有 $n$ 个段，第 $i$ 个为 $[l_i, r_i]$，现要在几个连续的段中，每段中各取一个值，构成一序列，要求该序列不能下降，求序列的最大长度。

解

以段的左端点维护单调序列。

当一新段将要入队时：

• 从后向前，将所有左点比新段的左点小的段弹出。
• 从前向后，将所有右点比新段的左点小的段弹出。
• 统计答案：用当前位置减去队头的上一段的位置
  • $\because$ 队头的上一段已被弹出
  • $\therefore$ 从队头的上一段的下一段起（可能已被弹出）至当前位置均属于合法序列

代码

#include <stdio.h>

const int N = 1100000;

int max(int a, int b) { return a > b ? a : b; }

int n, l[N], r[N], queue[N], ans = -1;
int main() {
    
    freopen("p3522.in", "r", stdin);
    
    scanf("%d", &n);
    for(int i=1; i<=n; ++i) scanf("%d%d", l+i, r+i);
    
    int head = 0, tail = 1;
    queue[head] = 0;
    
    for(int i=1; i<=n; ++i) {
        
        while(head < tail and l[i] >= l[queue[tail-1]]) --tail;
        queue[tail++] = i;
        
        while(head < tail and l[queue[head]] > r[i]) ++head;
        
        ans = max(ans, i - queue[head-1]);
        
    }
    
    printf("%d\n", ans);
    
    return 0;
}