Fork me on GitHub

ZROI#962

Posted on | | Views:

ZROI#962

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#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<int>
#define int long long
#define pb push_back

using 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<=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:$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <cmath>
#include <ctime>
#include <map>
#include <set>
#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<int>
#define int long long
#define pb push_back

using 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 ;
}

分享到： 收藏夹 复制网址 邮件 微信 QQ空间 腾讯微博 豆瓣 一键分享 更多