[TIOJ 1223] 好想睡覺 之 好累的大頭蕃

作法：

如果考慮 n 條線段 [ 0,t ] ，分別代表 n 個房間，並且把題目給的限制的區間通通挖掉，這樣可以得到 <= m+n 個區間，題目就是要問給定一個點，哪個區間是包含他的而且右端點最右邊的。第一步當然是先把題目給的區間在同一個房間裡先合併好，然後求出「挖掉限制區間後的線段們」。再來對他們依左端點從小到大排序，一樣時依右端點從大到小排序(等一下處理會比較方便)，如果再一樣那就按照房間編號從小到大排序(因為題目要的是「如果有多個右端點都符合條件，那麼取房間編號最小的」)。並且可以知道如果區間A包含了區間B，且B的右端點 < A的右端點，那麼B就廢掉了。同理可以得到其它會讓一個區間廢掉的條件，所以可以用個 stack 作存活下來的區間們有哪些。但還要注意到，如果兩個區間都存活下來了，且他們的右端點不同，但是有交集，那麼在交集的部分一定是選右邊的區間比較好，所以有時候會需要把一個區間的右端點改小。

最後得到了存活下來的區間之後，只要二分搜哪個區間是滿足「左界 <= 詢問的時間」的最大區間，就可以得到答案了。

code :

#include<bits/stdc++.h>
using namespace std;
const int maxn=100000+10 ;
struct P
{
    int id,x,y ;
    bool operator < (const P &rhs) const
    {
        return x==rhs.x ?
            (y==rhs.y ? id<rhs.id : y>rhs.y) : x<rhs.x ;
    }
};
 
P tmp[2*maxn] ;
void cal(vector<P> &v)
{
    sort(v.begin(),v.end()) ;
    int cnt=0 ;
    for(auto i : v)
    {
        if(!cnt) { tmp[cnt++]=i ; continue ; }
        if(tmp[cnt-1].y >= i.y) continue ;
        else if(i.x <= tmp[cnt-1].y)
            tmp[cnt-1].y=max(tmp[cnt-1].y,i.y) ;
        else tmp[cnt++]=i ;
    }
    for(int i=0;i<cnt;i++) v[i]=tmp[i] ;
    v.resize(cnt) ;
}
 
vector<P> v[maxn],seg ;
int n,t ;
 
void cal_seg()
{
    seg.clear() ;
    for(int i=1;i<=n;i++)
    {
        if(v[i].empty())
            {seg.push_back((P){i,0,t}) ; continue ;}
        int sz=v[i].size() ;
        if(v[i][0].x) seg.push_back((P){i,0,v[i][0].x}) ;
        for(int j=0;j<sz-1;j++)
            seg.push_back((P){i,v[i][j].y,v[i][j+1].x}) ;
        if(v[i][sz-1].y < t) seg.push_back((P){i,v[i][sz-1].y,t}) ;
    }
    sort(seg.begin(),seg.end()) ;
    int cnt=0 ;
    for(auto i : seg)
    {
        if(!cnt) { tmp[cnt++]=i ; continue ; }
        if(i.y < tmp[cnt-1].y) continue ;
        if(i.y == tmp[cnt-1].y)
        {
            if(i.x==tmp[cnt-1].x) continue ;
            if(i.id > tmp[cnt-1].id) continue ;
        }
        tmp[cnt++]=i ;
        if(tmp[cnt-2].y < tmp[cnt-1].y)
            tmp[cnt-2].x=min(tmp[cnt-2].x,tmp[cnt-1].x) ;
    }
    for(int i=0;i<cnt;i++) seg[i]=tmp[i] ;
    seg.resize(cnt) ;
}
 
main()
{
    while(scanf("%d%d",&n,&t)==2 && n+t)
    {
        for(int i=1;i<=n;i++) v[i].clear() ;
        int m ; scanf("%d",&m) ;
        while(m--)
        {
            int id,x,y ; scanf("%d%d%d",&id,&x,&y) ;
            v[id].push_back((P){id,x,y}) ;
        }
        for(int i=1;i<=n;i++) if(!v[i].empty()) cal(v[i]) ;
 
        cal_seg() ;
 
        int Q ; scanf("%d",&Q) ;
        while(Q--)
        {
            int x ; scanf("%d",&x) ;
            if(seg.empty()) { printf("Oh, no!\n") ; continue ; }
            else if(seg[0].x > x) { printf("Oh, no!\n") ; continue ; }
            int l=0 , r=seg.size() ;
            while(r-l>1)
            {
                int mid=(r+l)/2 ;
                if(seg[mid].x <= x) l=mid ;
                else r=mid ;
            }
            if(seg[l].y<=x) printf("Oh, no!\n") ;
            else printf("%d %d\n",seg[l].id,seg[l].y-x) ;
        }
    }
}