ZROI#962-白红宇

ZROI#962

阅读量：5289 次

发布时间：2019-06-14

本文共 9071 字，大约阅读时间需要 30 分钟。

看起来很数据结构的一道题,其实就是很数据结构...

\(\Theta(nmq)\)的暴力很无脑,是个人应该都会.

\(Code:\)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define MEM(x,y) memset ( x , y , sizeof ( x ) )#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)#define pii pair < int , int >#define X first#define Y second#define rint read
                
                 #define int long long#define pb push_backusing std::queue ;using std::set ;using std::pair ;using std::max ;using std::min ;using std::priority_queue ;using std::vector ;using std::swap ;using std::sort ;using std::unique ;using std::greater ;template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ;}const int N = 3e3 + 100 ;int n , m , Q , e[N][N] , dis[N][N] ;bool vis[N][N] ;int fx[] = { 1 , 0 , - 1 , 0 } ;int fy[] = { 0 , 1 , 0 , - 1 } ;queue < pii > q ;inline int bfs (int sx , int sy , int tx , int ty , int val) { if ( sx == tx && sy == ty ) return 0 ; if ( e[sx][sy] > val || e[tx][ty] > val ) return - 1 ; while ( ! q.empty () ) q.pop () ; rep ( i , 1 , n ) rep ( j , 1 , m ) vis[i][j] = dis[i][j] = 0 ; dis[sx][sy] = 0 ; q.push ( { sx , sy } ) ; vis[sx][sy] = true ; while ( ! q.empty () ) { pii cur = q.front () ; q.pop () ; for (int i = 0 ; i < 4 ; ++ i) { int dx = cur.X + fx[i] , dy = cur.Y + fy[i] ; if ( vis[dx][dy] || e[dx][dy] > val || dx < 1 || dy < 1 || dx > n || dy > m ) continue ; vis[dx][dy] = true ; dis[dx][dy] = dis[cur.X][cur.Y] + 1 ; q.push ( { dx , dy } ) ; if ( dx == tx && dy == ty ) return dis[dx][dy] ; } } return - 1 ;}inline void update (int type , int pos) { if ( type == 1 ) for (int i = 1 ; i <= m ; ++ i) e[pos][i] = 0 ; else for (int i = 1 ; i <= n ; ++ i) e[i][pos] = 0 ; return ;}inline void grow () { rep ( i , 1 , n ) rep ( j , 1 , m ) ++ e[i][j] ; return ; }signed main (int argc , char * argv[]) { n = rint () ; m = rint () ; Q = rint () ; while ( Q -- ) { grow () ; int k = rint () ; if ( k != 3 ) { int pos = rint () ; update ( k , pos ) ; } else { int sx = rint () , sy = rint () ; int tx = rint () , ty = rint () , val = rint () ; printf ("%lld\n" , bfs ( sx , sy , tx , ty , val ) ) ; } } return 0 ;}

然后考虑\(\Theta(n^2)\)怎么做,我们可以对每次操作前的整个矩阵加\(1\)操作维护一个全局标记实现.

我们再对行和列分别维护一个数组记录它最近一次被修改的时间\(t\).

若当前时间为\(cur\),询问限制权值为\(val\),则如果一个点存在横坐标纵坐标的\(t\)中至少一个满足\(t-cur\le val\)就是可行点.

我们只需要考虑有多少种连通情况即可.

共八种:

L型:

1.一个点的行和另一个点的列都可行

2.同上,两个点的对应行列都要判

Z型:

3.两个点所在行可行,只需要中间有一列可行即可.

4.两个点所在列可行,只需要中间有一行可行即可.

瞎走型:

5.两点之间所有的行都是可行的

6.两点之间所有的列都是可行的

外绕型:

7.两个点所在行可行,但中间没有可行列,需要到两点纵坐标之外寻找是否存在可行列

8.两个点所在列可行,但中间没有可行行,需要到两点横坐标之外寻找是否存在可行行.

显然,如果两个点连通,那么一定是上面八种情况之一.

于是\(\Theta(n^2)\)就就解决了.

\(\Theta(n^2)\)的暴力没写,我直接写了正解.

我们再来考虑怎么写没有\(2\)操作的部分分.

容易发现,如果不存在\(2\)操作,那么就只需要考虑两个点之间的行是否可行就行了,直接对行建线段树即可.

好了,终于到了正解了!

其实上面的部分分都会了的话,正解就一目了然了.

对行和列分别建一棵线段树,直接维护即可.

但你会发现\(7,8\)两种操作你不能直接线段树解决,因为你还要最小化距离.

所以我们考虑二分+线段树或线段树上二分.二者的区别在于实现和复杂度一个为\(\Theta(log_2^2n)\)而另一个为\(\Theta(log_2n)\).

显然,二分+线段树是两个\(log\)的,而线段树上二分是一个\(log\)的.我写的是两个\(log\)的,反正能过,谁管是啥呢.

因为你需要一段连续能走的,所以你要固定一个端点不动,你二分的是另一个端点的位置.

以点\((a,b)\)为例,如果你要往左找,那你应该查询的区间是\([mid,a-1]\),而向左向右缩短/扩张区间需要移动的端点是不一样的,要注意.

\(Code:\)

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              #include 
               
                #define MEM(x,y) memset ( x , y , sizeof ( x ) )#define rep(i,a,b) for (int i = (a) ; i <= (b) ; ++ i)#define per(i,a,b) for (int i = (a) ; i >= (b) ; -- i)#define pii pair < int , int >#define one first#define two second#define rint read
                
                 #define int long long#define pb push_backusing std::queue ;using std::set ;using std::pair ;using std::max ;using std::min ;using std::priority_queue ;using std::vector ;using std::swap ;using std::sort ;using std::unique ;using std::greater ;template < class T > inline T read () { T x = 0 , f = 1 ; char ch = getchar () ; while ( ch < '0' || ch > '9' ) { if ( ch == '-' ) f = - 1 ; ch = getchar () ; } while ( ch >= '0' && ch <= '9' ) { x = ( x << 3 ) + ( x << 1 ) + ( ch - 48 ) ; ch = getchar () ; } return f * x ;}const int inf = 0x7f7f7f7f ;class segment { #define ls ( rt << 1 ) #define rs ( rt << 1 | 1 ) #define mid ( ( l + r ) >> 1 ) private : static const int M = 1e5 + 100 ; private : struct seg { int left , right , maxn , minn ; } t[(M<<2)] ; private : inline void pushup (int rt) { t[rt].maxn = max ( t[ls].maxn , t[rs].maxn ) ; t[rt].minn = min ( t[ls].minn , t[rs].minn ) ; return ; } public : inline void build (int rt , int l , int r) { t[rt].left = l ; t[rt].right = r ; if ( l == r ) { t[rt].maxn = t[rt].minn = 0 ; return ; } build ( ls , l , mid ) ; build ( rs , mid + 1 , r ) ; pushup ( rt ) ; return ; } public : inline void coverp (int rt , int pos , int val) { int l = t[rt].left , r = t[rt].right ; if ( l == pos && pos == r ) { t[rt].minn = t[rt].maxn = val ; return ; } if ( pos <= mid ) coverp ( ls , pos , val ) ; else coverp ( rs , pos , val ) ; pushup ( rt ) ; return ; } public : inline int qmax (int rt , int ll , int rr) { int l = t[rt].left , r = t[rt].right ; if ( l == ll && r == rr ) return t[rt].maxn ; if ( rr <= mid ) return qmax ( ls , ll , rr ) ; else if ( ll > mid ) return qmax ( rs , ll , rr ) ; else return max ( qmax ( ls , ll , mid ) , qmax ( rs , mid + 1 , rr ) ) ; } public : inline int qmin (int rt , int ll , int rr) { int l = t[rt].left , r = t[rt].right ; if ( l == ll && r == rr ) return t[rt].minn ; if ( rr <= mid ) return qmin ( ls , ll , rr ) ; else if ( ll > mid ) return qmin ( rs , ll , rr ) ; else return min ( qmin ( ls , ll , mid ) , qmin ( rs , mid + 1 , rr ) ) ; } #undef ls #undef rs #undef mid} line , row ;int n , m , Q , cur ;inline int mabs (int x) { return x < 0 ? - x : x ; }inline int Manhattan (int sx , int sy , int tx , int ty) { return mabs ( sx - tx ) + mabs ( sy - ty ) ; }inline int deal (int a , int b , int c , int d , int val) { // 行全行 int lines = line.qmin ( 1 , min ( a , c ) , max ( a , c ) ) ; if ( cur - lines <= val ) return Manhattan ( a , b , c , d ) ; // 列全行 int rows = row.qmin ( 1 , min ( b , d ) , max ( b , d ) ) ; if ( cur - rows <= val ) return Manhattan ( a , b , c , d ) ; // L 型-下左 int Arow = row.qmax ( 1 , b , b ) , Bline = line.qmax ( 1 , c , c ) ; if ( cur - Arow <= val && cur - Bline <= val ) return Manhattan ( a , b , c , d ) ; // L 型-上右 int Aline = line.qmax ( 1 , a , a ) , Brow = row.qmax ( 1 , d , d ) ; if ( cur - Brow <= val && cur - Aline <= val ) return Manhattan ( a , b , c , d ) ; // 内 Z 型-两行一列 rows = row.qmax ( 1 , min ( b , d ) , max ( b , d ) ) ; if ( cur - Aline <= val && cur - Bline <= val && cur - rows <= val ) return Manhattan ( a , b , c , d ) ; // 内 Z 型-两列一行 lines = line.qmax ( 1 , min ( a , c ) , max ( a , c ) ) ; if ( cur - Arow <= val && cur - Brow <= val && cur - lines <= val ) return Manhattan ( a , b , c , d ) ; // 外 Z 型-两行+外绕 if ( cur - Aline <= val && cur - Bline <= val && cur - rows > val ) { int res = inf ; if ( b > d ) swap ( b , d ) ; int l = 1 , r = b - 1 , pos = - 1 ; while ( l <= r ) { int mid = ( l + r ) >> 1 ; if ( cur - row.qmax ( 1 , mid , b - 1 ) <= val ) { pos = mid ; l = mid + 1 ; } else r = mid - 1 ; } if ( pos != - 1 ) res = min ( res , mabs ( pos - b ) * 2 ) ; l = d + 1 ; r = m ; while ( l <= r ) { int mid = ( l + r ) >> 1 ; if ( cur - row.qmax ( 1 , d + 1 , mid ) <= val ) { pos = mid ; r = mid - 1 ; } else l = mid + 1 ; } if ( pos != - 1 ) res = min ( res , mabs ( pos - d ) * 2 ) ; if ( pos != - 1 ) return Manhattan ( a , b , c , d ) + res ; } // 外 Z 型-两列+外绕 if ( cur - Arow <= val && cur - Brow <= val && cur - lines > val ) { int res = inf ; if ( a > c ) swap ( a , c ) ; int l = 1 , r = a - 1 , pos = - 1 ; while ( l <= r ) { int mid = ( l + r ) >> 1 ; if ( cur - line.qmax ( 1 , mid , a - 1 ) <= val ) { pos = mid ; l = mid + 1 ; } else r = mid - 1 ; } if ( pos != - 1 ) res = min ( res , mabs ( pos - a ) * 2 ) ; l = c + 1 ; r = n ; while ( l <= r ) { int mid = ( l + r ) >> 1 ; if ( cur - line.qmax ( 1 , c + 1 , mid ) <= val ) { pos = mid ; r = mid - 1 ; } else l = mid + 1 ; } if ( pos != - 1 ) res = min ( res , mabs ( pos - c ) * 2 ) ; if ( pos != - 1 ) return Manhattan ( a , b , c , d ) + res ; } // 不连通 return - 1 ;}signed main (int argc , char * argv[]) { n = rint () ; m = rint () ; Q = rint () ; line.build ( 1 , 1 , n ) ; row.build ( 1 , 1 , m ) ; while ( Q -- ) { int k = rint () ; ++ cur ; if ( k != 3 ) { int pos = rint () ; if ( k == 1 ) line.coverp ( 1 , pos , cur ) ; if ( k == 2 ) row.coverp ( 1 , pos , cur ) ; } else { int sx = rint () , sy = rint () ; int tx = rint () , ty = rint () , val = rint () ; if ( sx == tx && sy == ty ) { puts ("0") ; continue ; } printf ("%lld\n" , deal ( sx , sy , tx , ty , val ) ) ; } } return 0 ;}

转载于:https://www.cnblogs.com/Equinox-Flower/p/11536244.html

你可能感兴趣的文章