Luogu | P3522 [POI 2011] Temperature | 数据结构 | 单调队列 / 优先队列


Description

The Byteotian Institute of Meteorology (BIM) measures the air temperature daily. The measurement is done automatically, and its result immediately printed. Unfortunately, the ink in the printer has long dried out… The employees of BIM however realised the fact only recently, when the Byteotian Organisation for Meteorology (BOM) requested access to that data.

An eager intern by the name of Byteasar saved the day, as he systematically noted down the temperatures reported by two domestic alcohol thermometers placed on the north and south outside wall of the BIM building. It was established decades ago by various BIM employees that the temperature reported by the thermometer on the south wall of the building is never lower than the actual temperature, while that reported by the thermometer on the north wall of the building is never higher than the actual temperature. Thus even though the exact temperatures for each day remain somewhat of a mystery, the range they were in is known at least.

Fortunately for everyone involved (except Byteasar and you, perhaps), BOM does not require exact temperatures. They only want to know the longest period in which the temperature was not dropping (i.e. on each successive day it was no smaller than on the day before). In fact, the veteran head of BIM knows very well that BOM would like this period as long as possible. To whitewash the negligence he insists that Byteasar determines, based on his valuable notes, the longest period in which the temperature could have been not dropping. Now this is a task that Byteasar did not quite expect on his BIM internship, and he honestly has no idea how to tackle it. He asks you for help in writing a program that determines the longest such period.

某气象研究所连续测定了 $n$ 天的最高气温和最低气温,请你帮忙求出一串最长的,连续的,存在一个非降的温度曲线被这个序列的每天的最高气温和最低气温都包含的序列的长度。


Input Format

In the first line of the standard input there is one integer $n$ that denotes the number of days for which Byteasar took notes on the temperature. The measurements from day $i$ are given in the line $i+1$ . Each of those lines holds two integers, $x$ and $y$. These denote, respectively, the minimum and maximum possible temperature on that particular day, as reported by the two thermometers.


Output Format

In the first and only line of the standard output your program should print a single integer, namely the maximum number of days for which the temperature in Byteotia could have been not dropping.


Input Sample

Sample 01

6
6 10
1 5
4 8
2 5
6 8
3 5


Output Sample

Sample 01

4

Explanation

在第 $2$ 至第 $5$ 天内,存在温度曲线 $3 – 4 – 5 – 6$ ,其中 $3$ 属于 $[1,5]$,$4$ 属于 $[4,8]$,$5$ 属于 $[2,5]$,$6$ 属于 $[6,8]$,长度为 $4$。


Data Range

$-10^9 \le x_i,y_i \le 10^9 $,$1 \le n \le 10^6 $。


Solution

显然对于每个点都可以 $\Theta(n)$ 求以其为起始点的最长连续序列。

考虑计算以点 $i$ 为开头最长能够向后延伸到多远。不难发现,对于 $i$ ,若 $i+1$ 的最高气温 $\ge$ $i$ 的最低气温,则 $i$ 可以连到 $i+1$ 前面。

实际计算时,限制 $i$ 能否连上一长串的瓶颈可能在更后面。设 Ext 为 $i+1$ 能够延伸到的最远的位置。若 $\min{\mathrm{High}[i+1,Ext]} < \mathrm{Low}_i$,则说明 $i$ 不能直接连到 Ext。将这个区间内所有不能与 $i$ 相连的瓶颈全部挑出来之后,则 $i$ 可以和 挑出来的所有结点中的最靠左的一个 $- 1$ 相连,并更新 Ext;反之则 $i$ 可以和 Ext 相连,计算答案。该过程可以用 单调队列 / 优先队列 维护。


Code

std::priority_queue 堆

#include<queue>
#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

using std::priority_queue;

int buf[20];

template <class T> inline void Read(T &x){
    x=0;
    char ch=0;
    bool neg=0;
    while(ch<'0'||ch>'9')
        ch=getchar(),neg|=(ch=='-');
    while(ch>='0'&&ch<='9')
        x=x*10+ch-48,ch=getchar();
    x*=neg?-1:1;
    return;
}

template <class T> inline void Write(T x){
    if(!x){
        putchar('0');
        putchar('\n');
        return;
    }
    if(x<0){
        x=-x;
        putchar('-');
    }
    int cntr=0;
    while(x)
        buf[++cntr]=x%10,x/=10;
    for(int i=cntr;i;i--)
        putchar(buf[i]+48);
    putchar('\n');
    return;
}

struct data{
    int val;
    int pos;
    friend bool operator < (data a,data b){
        return a.val>b.val;
    }
};

int N;
int Ext;
int Ans;

int ans[1000005];
int lower[1000005];
int upper[1000005];

bool del[1000005];

priority_queue<data>pq;

int main(){
    Read(N);
    rep(i,1,N){
        Read(lower[i]);
        Read(upper[i]);
    }
    Ext=N;
    ans[N]=1;
    pq.push((data){upper[N],N});
    for(int i=N-1;i>=1;i--){
        while(!pq.empty() && pq.top().pos>Ext)
            pq.pop();
        if(!pq.empty() && pq.top().val<lower[i]){
            while(!pq.empty() && pq.top().val<lower[i]){
                Ext=min(Ext,pq.top().pos-1);
                pq.pop();
            }
        }
        if(pq.empty())
            Ext=i;
        ans[i]=Ext-i+1;
        pq.push((data){upper[i],i});
    }
    rep(i,1,N)
        Ans=max(Ans,ans[i]);
    printf("%d\n",Ans);
    return 0;
}

std::deque 单调队列

#include<deque>
#include<cstdio>
#include<cstdlib>
#include<cstring>

#define min(x,y) ((x)<(y)?(x):(y))
#define max(x,y) ((x)>(y)?(x):(y))
#define swap(x,y) {int t=x; x=y,y=t;}
#define wipe(x,y) memset(x,y,sizeof(x))
#define dbgIn(x) freopen(x".in","r+",stdin)
#define rep(x,y,z) for(int x=y,I=z;x<=I;++x)
#define dbgOut(x) freopen(x".out","w+",stdout)
#define file(x) freopen(x".in","r+",stdin); freopen(x".out","w+",stdout)

using std::deque;

int buf[20];

template <class T> inline void Read(T &x){
    x=0;
    char ch=0;
    bool neg=0;
    while(ch<'0'||ch>'9')
        ch=getchar(),neg|=(ch=='-');
    while(ch>='0'&&ch<='9')
        x=x*10+ch-48,ch=getchar();
    x*=neg?-1:1;
    return;
}

template <class T> inline void Write(T x){
    if(!x){
        putchar('0');
        putchar('\n');
        return;
    }
    if(x<0){
        x=-x;
        putchar('-');
    }
    int cntr=0;
    while(x)
        buf[++cntr]=x%10,x/=10;
    for(int i=cntr;i;i--)
        putchar(buf[i]+48);
    putchar('\n');
    return;
}

struct data{
    int val;
    int pos;
};

int N;
int Ext;
int Ans;

int ans[1000005];
int lower[1000005];
int upper[1000005];

bool del[1000005];

deque<data>pq;

int main(){
    Read(N);
    rep(i,1,N){
        Read(lower[i]);
        Read(upper[i]);
    }
    Ext=N;
    ans[N]=1;
    pq.push_back((data){upper[N],N});
    for(int i=N-1;i>=1;i--){
        while(!pq.empty() && pq.front().pos>Ext)
            pq.pop_front();
        if(!pq.empty() && pq.front().val<lower[i]){
            while(!pq.empty() && pq.front().val<lower[i]){
                Ext=min(Ext,pq.front().pos-1);
                pq.pop_front();
            }
        }
        if(pq.empty())
            Ext=i;
        ans[i]=Ext-i+1;
        while(!pq.empty() && pq.back().val>=upper[i])
            pq.pop_back();
        pq.push_back((data){upper[i],i});
    }
    rep(i,1,N)
        Ans=max(Ans,ans[i]);
    printf("%d\n",Ans);
    return 0;
}