LP3522 [POI2011]TEM-Temperature [尺取法/单调队列]

ajcxsu
ajcxsu 2018年10月24日
  • 52 次阅读

嘛又是看错题了...话说回来网上的题解都是些啥..

Problem

https://www.luogu.org/problemnew/solution/P3522 $n\leq 10^6$

Solution

因为是连续一段区间所以尺取。 发现区间合法的条件是对于任意$i< j$,有$l_i\leq r_j$。
这里请自己手画一下图,当然应该都会发现这个规律。

然后移动$R$指针的话,查询区间$[L, R)$的最大的$l$是不是大于$r_R$就行了。

这玩意可以用单调队列维护。

是傻逼题呢,但我为什么没想出来呢。

因为我太菜了呀。

// Code by ajcxsu
// Problem: TEM

#include<bits/stdc++.h>
using namespace std;

const int N=1e6+10;
int qu[N], pos[N];

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n;
    cin>>n;
    int l=1;
    int nl, nr, h, t, ans=0;
    h=t=0;
    for(int i=1;i<=n;i++) {
        cin>>nl>>nr;
        while(l<i && qu[h]>nr) {
            l++;
            while(h!=t && pos[h]<l) h++;
        }
        while(h!=t && nl>qu[t-1]) t--;
        qu[t]=nl, pos[t++]=i;
        ans=max(i-l+1, ans);
    }
    cout<<ans<<endl;
    return 0;
}

本文链接:https://acxblog.site/archives/sol-luogu-3522.html
本文采用 CC BY-NC-SA 3.0 协议进行许可