P4259 [Code+#3]寻找车位

考虑对行建线段树。对于线段树的每个节点,设节点代表区间为 $[l,r]$ ,对于所有的 $m$ 列在这个区间维护贴紧左、右端点的连续段长度。同时维护对于每列,在这个区间能得到的最大的右端点在这一列的正方形大小。

由于我们维护了这个东西,合并的时候大概就有这样一个图:

JGGNMM__S_4_@BCXJTV___H.png

首先,连续段长度是非常好合并的。

合并时,只需要考虑跨过了 $mid$ 的正方形。考虑怎么维护每列作为正方形的右边在区间能得到的正方形大小。考虑从左往右枚举右端点 $i$ 。如果左右端点固定,那么竖直的边长就是在区间的上下区间分别的最小值的差。考虑左端点右移的过程,可以发现能构成的正方形最大的水平的边长在变小,竖直的边长在变大(因为区间最小值随着数被删除只会增大)。而右端点向右移动时,竖直的边长在单调变小,水平的边长增加了 $1$ 。

可以发现,右端点向右移动的过程中左端点是单调向右移动的。如果右端点移动导致当前左右端点构不成正方形了,也就是竖直的边长被减得太小了或者水平的边长太长了,这种情况下左移左端点明显只会让竖直边长与水平边长更劣。

维护上下区间之内的最小值可以上下分别维护单调队列解决。具体来说,如果当前水平的长度超过了上下的长度,那么就左移左端点,更新单调队列即可。

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
#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 4000006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m , q;

struct poi {
int a[MAXN * 4]; // a[SIZE/m][m]
int* operator[] ( int x ) {
return a + x * m;
}
} up , dw , ans , G ;

int q1[MAXN] , q2[MAXN] , hd1 , hd2 , tl1 , tl2;

inline void merge( int rt , int ls , int rs , int llen , int rlen ) {
hd1 = hd2 = 0 , tl1 = tl2 = -1;
int j = 1;
rep( i , 1 , m ) {
while( hd1 <= tl1 && up[rs][i] <= up[rs][q1[tl1]] ) -- tl1;
while( hd2 <= tl2 && dw[ls][i] <= dw[ls][q2[tl2]] ) -- tl2;
q1[++ tl1] = i , q2[++ tl2] = i;
while( j <= i && i - j + 1 > up[rs][q1[hd1]] + dw[ls][q2[hd2]] ) {
++ j;
while( hd1 <= tl1 && q1[hd1] < j ) ++ hd1;
while( hd2 <= tl2 && q2[hd2] < j ) ++ hd2;
}
ans[rt][i] = max( i - j + 1 , max( ans[ls][i] , ans[rs][i] ) );
}
rep( i , 1 , m ) {
up[rt][i] = up[ls][i] + ( up[ls][i] == llen ? up[rs][i] : 0 );
dw[rt][i] = dw[rs][i] + ( dw[rs][i] == rlen ? dw[ls][i] : 0 );
}
}

void build( int rt , int l , int r ) {
if( l == r ) {
rep( i , 1 , m ) up[rt][i] = dw[rt][i] = ans[rt][i] = G[l][i];
return;
}
int m = l + r >> 1 , len = r - l + 1;
build( rt << 1 , l , m ) , build( rt << 1 | 1 , m + 1 , r );
merge( rt , rt << 1 , rt << 1 | 1 , len - ( len >> 1 ) , len >> 1 );
}

void flip( int rt , int l , int r , int p , int x ) {
if( l == r ) {
up[rt][x] ^= 1 , dw[rt][x] ^= 1 , ans[rt][x] ^= 1; return;
}
int m = l + r >> 1 , len = r - l + 1;
if( p <= m ) flip( rt << 1 , l , m , p , x );
else flip( rt << 1 | 1 , m + 1 , r , p , x );
merge( rt , rt << 1 , rt << 1 | 1 , len - ( len >> 1 ) , len >> 1 );
}

void que( int rt , int l , int r , int L , int R ) {
if( L <= l && R >= r ) {
merge( 0 , 0 , rt , l - L , r - l + 1 );
return;
}
int m = l + r >> 1;
if( L <= m ) que( rt << 1 , l , m , L , R );
if( R > m ) que( rt << 1 | 1 , m + 1 , r , L , R );
}

namespace IO {
const int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc() \
(p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
? EOF \
: *p1++)
inline int rd() {
int x = 0, f = 1;
char c = gc();
while (!isdigit(c)) {
if (c == '-') f = -1;
c = gc();
}
while (isdigit(c)) x = x * 10 + (c ^ 48), c = gc();
return x * f;
}
char pbuf[1 << 20], *pp = pbuf;
inline void push(const char &c) {
if (pp - pbuf == 1 << 20) fwrite(pbuf, 1, 1 << 20, stdout), pp = pbuf;
*pp++ = c;
}
inline void write(int x) {
static int sta[35];
int top = 0;
do {
sta[top++] = x % 10, x /= 10;
} while (x);
while (top) push(sta[--top] + '0');
push( 10 );
}
}

void solve() {
using namespace IO;
cin >> n >> m >> q;
rep( i , 1 , n ) rep( j , 1 , m ) G[i][j] = rd();
build( 1 , 1 , n );
int op , x , y , xx , yy , re;
rep( i , 1 , q ) {
op = rd() , x = rd() , y = rd();
if( op == 0 )
flip( 1 , 1 , n , x , y ) , G[x][y] ^= 1;
else {
xx = rd() , yy = rd();
rep( i , 1 , m ) up[0][i] = dw[0][i] = ans[0][i] = 0;
que( 1 , 1 , n , x , xx );
// rep( i , 1 , m ) printf("%d\n",ans[0][i]);
re = 0;
rep( i , y , yy ) re = max( re , min( i - y + 1 , ans[0][i] ) );
write( re );
}
}
fwrite( pbuf , 1 , pp - pbuf , stdout );
}

signed main() {
// int T;cin >> T;while( T-- ) solve();
solve();
}

文章作者: yijan
文章链接: https://yijan.co/p4259-code3xun-zhao-che-wei/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Yijan's Blog