[HOJ 76][POI 18 Stage 2] 邪惡表格

一開始還沒看到「連續」，想說這題怎麼那麼難阿.......QQ

作法：

每到一條線段的時候，把他前面線段的起點太高的線段都砍掉，記被砍掉的線段們的最大坐標是 L ，那麼從 L+1 一直到現在這條線段的這個區間就可以取到一個遞增的子數列。

code :

#include<bits/stdc++.h>
using namespace std;
struct P
{
    int id,val ;
    bool operator < (const P &rhs) const
    {
        return val<rhs.val ;
    }
};
priority_queue<P> pq ;
main()
{
    int n ; scanf("%d",&n) ;
    int ans=0 , L=0 ;
    for(int i=1;i<=n;i++)
    {
        int x,y ; scanf("%d%d",&x,&y) ;
        while(!pq.empty() && pq.top().val>y)
        {
            L=max(L,pq.top().id) ;
            pq.pop() ;
        }
        ans=max(ans,i-L) ;
        pq.push((P){i,x}) ;
    }
    printf("%d\n",ans) ;
}