# 单调队列

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

# P3088 拥挤的奶牛

# 题面

NN 头奶牛沿着一维的栅栏吃草,第 ii 头奶牛在目标点 xix_i,它的身高是 hih_i 。当一头奶牛左边 DD 距离内而且右边 DD 距离内有身高至少是它的两倍的奶牛,它就会觉得拥挤。

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

#

(单调队列模板?)

当一奶牛将要入队时:

  • 从后往前,将身高小于该奶牛的弹出( --tail ),因为将要进队的奶牛更加靠后,影响范围一定更大,对答案的贡献也一定更大。
  • 从前往后,将与该奶牛距离已超过 DD 的奶牛弹出( ++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

# 题面

nn 个段,第 ii 个为 [li,ri][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;
}
更新于