题解 P4436 【[HNOI/AHOI2018]游戏】

· · 题解

两年前的题了，今天补一下复杂度正确的搞法.svg

题意：

给定 n,m,p，有 n 个房间，i 与 i+1 相邻，构成一个序列。

存在 m 个门，连接 x 与 x+1 的门在 y 房间处。

$\rm Sol:

容易发现：

我们先将可以互相达到的点连起来，缩成若干个联通块，对于每扇门 i，如果其一定不能从右边走到左边，那么连接左边 \to 右边的一条边，表示左边可能走到右边。

最后生成的图一定形如：

>><<<<>>><<>><<<>>>

那么对于一个 <<< 我们直接暴力拓展，同时利用继承的性质，容易发现这里的复杂度均摊为 O(n)

对于一个峰顶 <> 我们暴力对两边同时拓展并同样继承，容易发现这里的复杂度仍然均摊为 O(n)

于是总体复杂度可以做到 O(n)

复杂度为 O(n) 的理由是每扇门最多只会被打开一次，当然你需要通过继承的性质来保证这一点。

不过由于需要查出来更新顺序（从 '><' 往外处更新），所以可能要top排序一下，不过应该也有办法可以不需要top排序吧/fad

#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
int gi() {
    char cc = getchar() ; int cn = 0, flus = 1 ;
    while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
    while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
    return cn * flus ;
}
const int N = 1e6 + 5 ; 
int n, m, p, cnt, top, L[N], R[N], Go[N] ;
int Id[N], ke[N], deg[N], Deg[N], st[N] ;  
queue<int> q ; 
signed main()
{
    n = gi(), m = gi(), p = gi() ; int x, y ; 
    rep( i, 1, m ) {
        x = gi(), y = gi(), ke[x] = y ;
        if( y > x ) Go[x] = -1, ++ deg[x] ;
        else Go[x] = 1, ++ deg[x + 1] ; 
    } memset( L, 63, sizeof(L) ), cnt = 1 ; 
    rep( i, 1, n ) {
        if( Go[i - 1] ) ++ cnt ;
        Id[i] = cnt, Deg[cnt] += deg[i] ; 
        L[cnt] = min( L[cnt], i ), R[cnt] = max( R[cnt], i ) ;
    }
    rep( i, 1, cnt ) if( !Deg[i] ) q.push(i) ;
    while( !q.empty() ) {
        int u = q.front() ; q.pop(), st[++ top] = u ;
        if( u > 1 && Go[L[u] - 1] == -1 ) {
            -- Deg[u - 1] ; if( !Deg[u - 1] ) q.push(u - 1) ;
        }
        if( u < cnt && Go[R[u]] == 1 ) {
            -- Deg[u + 1] ; if( !Deg[u + 1] ) q.push(u + 1) ; 
        }
    }
    for( re int i = top; i >= 1; -- i ) {
        int u = st[i], l = L[u], r = R[u], fl = 1 ;
        while( fl ) {
            fl = 0 ; 
            if( ( r < n ) && ( ke[r] >= l ) && ( ke[r] <= r ) ) r = R[Id[r + 1]], fl = 1 ;
            if( ( l > 1 ) && ( ke[l - 1] >= l ) && ( ke[l - 1] <= r ) ) l = L[Id[l - 1]], fl = 1 ;
        }
        L[u] = l, R[u] = r ;
    }
    while( p-- ) {
        x = gi(), y = gi() ;
        if( y <= R[Id[x]] && y >= L[Id[x]] ) puts("YES") ;
        else puts("NO") ;
    }
    return 0 ;
}