_序列の题解_

思路

大牛一眼看出滑动窗口,这里给出详细解释(本人纯蒟蒻)大牛可以走了。

解法1(暴力)

纯暴力理论 40pts, 实际得分 70pts@xw_qwq 大佬使用暴力加优化拿了 100pts

解法2(滑动窗口)

Q:为什么要用滑动窗口?

显然的,我们的温度区域是一个线性结构,为了保证我们选出的最长上升序列是最优的,我们可以考虑维护一个双端队列, 在时间复杂度 O(n) 的时间内得出一个最好的选择

Q:如何维护这个滑动窗口?

首先,> b_i 的肯定不可以选择了,需要把他们踢出队列,然后 < a_i 的也需要被踢出,因为如果继续延续的话后面全部会变成 a_i,显然我们需要踢出去。

具体的说:先从队列前端移除所有L > b[i]的区间,因为这些区间的最小温度大于当前天的最大可能温度,无法与当前天组成不下降序列,如果队列不为空,计算当前天到队列前端区间起始索引的长度,更新最大长度,然后从队列后端移除所有L <= a[i]的区间,因为当前天的最小温度a[i]更大,能形成更优的下界,合并这些区间并记录起始索引,最后将当前天形成的新区间加入队列后端

这么说的话,这个代码实际上已经很好写了,我们给出核心 code

while (!qu.empty() && qu.front().L > b[i])
{
    qu.pop_front();
}
if (!qu.empty())
    ans = max(ans, i - qu.front().L + 1);

while (!qu.empty() && qu.back().L <= a[i])
{
    tmp = qu.back().idx;
    qu.pop_back();
}
qu.push_back({a[i], b[i], tmp});

可以双指针+st表

怎么暴力,我之前写dp 50分 wa了。