题目

题意

某国进行了连续$n$天的温度测量，测量存在误差，测量结果是第$i$天的温度在$[l_i, r_i]$范围内，求温度不下降的最长连续天数。

更清晰的题意：有一个长度为$n$的序列$a$，其中对于每个$i, l_i \leq a_i \leq r_i$，你可以在这个范围内指定$a_i$的值，从而确定这个序列，然后求最长不降子段的长度

数据范围

$1 \leq n \leq 10^6$

$-10^9 \leq l_i, r_i \leq 10^9$

题解

思路

解法1

显然，我们可以枚举答案子段的左端点，然后尝试向后延伸延伸过程中尽量让当天的温度最小

举个例子

$[1, 5], [2, 3], [1, 6], [0, 1]$，第一天的温度确定为1，第二天的温度虽然最小值是2，但是我们要单调不降，所以第二天温度取2，同理第三天也取2，第四天就没有正确的取值了，所以对于$i = 1$，答案是3

但是复杂度是$O(n^2)$，会t

优化

那我们的优化思路有两个

考虑$i, i + 1$的答案能不能通过某种$O(log)$之内的方法转移

枚举左端点的时候能不能通过$O(log)$之内的方法找到右端点

第一种优化

我们发现从$i + 1$出发到不了的右端点，那么$1, 2, …, i$肯定也到不了； $i$出发能到达的右端点， $i + 1$出发一定也能达到，而且有可能更远

看起来没什么用

第二种优化

对于$i$而言，如果有$r_{i + 1}, r_{i + 2}, … r_j \geq l_i$，那么$i$就可以到达$j$，所以对于每个$i$，我们只需要向右找到第一个小于$l_i$的$r_i$就可以了，单调栈可以解决这个问题， $O(1)$的

正解

第二种优化里面说的其实是错的，举个例子

$[1, 2], [2, 3], [4, 5], [2, 3]$， $r_2, r_3, r_4$都大于等于$l_1$，但是从1开始只能到达3

这是不是说我们的优化策略不对？

其实这里出现的问题，就是第一种优化里我们提到的， 3不能到达4，那么1， 2肯定也不能到达4，也就是说如果$i$只能到$j$，那么$j$之后的就可以全删掉了，我们只在保留的区间里执行第二种优化策略就可以了

我们倒序枚举左端点$i$, 过程中通过单调栈找到最远的右端点，记录答案，然后把到不了的区间都删了就可以了

代码

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>

int n;
struct Seg
{
    int l, r;
    int pos;

    bool operator < (Seg tmp) const // 重载， 给lower_bound看的
    {
        return r > tmp.r;
    }
} seg[1000006];
std:: deque<Seg> dq; // 这个题并不是常规的单调栈， 因为栈内维护的是r， 但实际上我们查找的时候查的是比l小的第一个， 所以不能像普通单调栈一样删元素
int ans = 1;

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i ++)
        scanf("%d%d", &seg[i].l, &seg[i].r), seg[i].pos = i;

    int end = n; // 能到达的最远的右端点
    for(int i = n; i >= 1; i --)
    {
        if(dq.empty())
        {
            dq.push_front(seg[i]);

            continue;
        }

        auto it = upper_bound(dq.begin(), dq.end(), (Seg){seg[i].l, seg[i].l, 0}); // 查询第一个比l小的

        if(it != dq.end())
        {
            end = it->pos - 1; // 更新最远右端点

            while((! dq.empty()) && dq.back().pos != it->pos) dq.pop_back(); // 后边的删了
            dq.pop_back(); // 别忘了这个也要删
        }
      
        while((! dq.empty()) && dq.front().r >= seg[i].r) dq.pop_front();// 维护单调栈
        dq.push_front(seg[i]);

        ans = std:: max(ans, end - i + 1); // 统计答案
    }

    printf("%d\n", ans);

    return 0;
}

Update

想了想，那个lower_bound没有必要，因为可以直接从队尾往前扫，边扫边找边删就可以了

Zth's Blog

测温 Namomo 每日一题div1 04-01

题目

题意

数据范围

题解

思路

解法1

优化

第一种优化

第二种优化

正解

代码

Update