题目
点这里看题目。
分析
非常好的一道题目。
我们不妨先考虑一个弱化的问题：根据题目给定的数据，如何判断 \((1,1)\) 能否到达 \((n,m)\)。
通过各种手玩可以得到下面四种情况会导致无解：
-
存在某一行无法通行，也即 \(\exist 1\le x\le n\)，使得 \(\forall 1\le y\le m, A_x+B_y<0\)；
-
存在某一列无法通行，也即 \(\exist1\le y\le m\)，使得 \(\forall 1\le x\le n,A_x+B_y<0\)；
-
起点被堵住，也即 \(\exist(x,y),1\le x\le n,1\le y\le m\)，使得 \(\forall 1\le i\le x,A_i+B_y<0\)，以及 \(\forall 1\le j\le y,A_x+B_j<0\)。
-
终点被堵住，也即 \(\exist(x,y),1\le x\le n,1\le y\le m\)，使得 \(\forall x\le i\le n,A_i+B_y<0\)，以及 \(\forall y\le j\le m,A_x+B_j<0\)。
但是，似乎所有无解的情况都可以被归纳到上面四类中的一类或者多类。
如果仅仅是简单地完成题目，那么我们可以通过多检测几组数据来验证这一性质；经过多种验证，大可认为它是对的。
作为一份并不会那么严谨的题解，这里将给出证明，读者自可略过：
证明：如果上面四类情况均不成立，则 \((1,1)\) 一定可以到达 \((n,m)\)。
注：证明过程的图片均来自于比赛的官方题解。
如果情况 1,2 均不成立，那么容易得到 \(\min_x A_x+\max_y B_y\ge 0,\max_xA_x+\min_yB_y\ge 0\)。
注意到，如果我们取出 \(p,A_p=\max_xA_x\) 和 \(q,B_q=\max_y B_y\)，那么 \((p,q)\) 所在的一行和一列必然都可以互相到达：
那么这个时候，一条合法的路径一定会从 \((1,1)\) 到达蓝色区域的某一个位置，最后一定会从黄色区域的某一个位置到达 \((n,m)\)。
由于从 \((1,1)\) 到蓝色区域和从黄色区域到 \((n,m)\) 是完全对称的，所以我们可以使用同样的方法证明；下面我们说明，\((1,1)\) 一定可以到达蓝色区域。
如果我们不能到达蓝色区域，那么在 \((1,1)\) 到 \((p-1,q-1)\) 这 \((p-1)\times (q-1)\) 的区域中，一定存在一行和一列不能通过：
但是注意到，如果选取 \((x,y)\) 为不能通过的一行一列的交点，那么这就可以被归入情况 3，不符合条件；或者，如果仅存在不能通过的一行或者一列，并且它覆盖了 \((1,1)\)，那么也可以被归入情况 3，不符合条件。
由于不能通过的一行和一列不能同时存在，不妨假设不存在不能通过的一行，那么就满足 \(\forall 1\le x<p,\exist 1\le y<q,A_x+B_y\ge 0\)，转化一下得到 \(\min_{1\le x<p}A_x+\max_{1\le y<q}B_y\ge 0\)。这个时候取出 \(\max_{1\le y<q}B_y\) 所在的一列，就可以发现这一列是可以互相到达的，而不存在不能通过的一列的情况同理：
此时 \(\max_{1\le y<q}B_y\) 所在的一列也一定可以到达原先的蓝色区域，所以也可以将这一行看作蓝色。
这个时候，我们就可以缩减问题的规模，只保留最靠左的蓝色列和最靠上的蓝色行；循环这个步骤，直到 \((1,1)\) 被覆盖，那么能得出 \((1,1)\) 可以到达蓝色区域，证明结束。
现在我们得知情况数有限，我们就可以将这四种情况一一转化为对于起终点的限制。
-
如果从 \((S,1)\) 到 \((T,m)\) 存在一行无法通行，不妨为 \(i\) 这一行，那么就有 \(A_i+\max_y B_y<0\)，此时所有 \(1\le S\le i\le T\le n\) 都无法通行。
-
如果从 \((S,1)\) 到 \((T,m)\) 存在一列无法通行，就说明 \(\exist 1\le y\le m,\forall S\le x\le T,A_x+B_y<0\)，转化一下得到 \(\forall {S\le x\le T},\min_yB_y+A_x<0\)。所以，我们可以算出若干个 \(x\) 的区间 \([l_1,r_1],[l_2,r_2],\dots,[l_k,r_k]\)，在区间 \(i\) 中有 \(\forall x\in [l_i,r_i],A_x+\min_yB_y<0\)。这样，如果 \(S,T\) 落在了一个区间里面，它们就一定会被一列阻隔。
-
如果从 \((S,1)\) 到 \((T,m)\) 的时候，起点被一个十字的左上角堵住了。由于十字由它的中心 \((x,y)\) 来确定，并且我们只需要让十字阻挡第一列，我们可以枚举 \(x\)，并尝试最大化十字的竖边。
即，我们首先需要找到最小的 \(j\)，使得 \(A_x+B_j\ge 0\)，这样 \(y<j\)；为了最大化竖边，我们可以直接取 \(B_y=\min_{1\le k<j}B_k\) 的 \(y\)。接着，我们就可以找到最大的 \(i\)，使得 \(A_i+B_y\ge 0\)。那么，当十字的中心在第 \(x\) 行上的时候，最小能被覆盖的行就是第 \(i+1\) 行。
-
这个情况与情况 3 完全对称，可以相似地解决。
注意到，四种情况经过转化，其覆盖的起点和终点都是一段区间。如果将 \((S,1),(T,m)\) 转化为平面上的点 \((S,T)\)，每种情况的限制会变成一个矩形。此时矩形限制就可以用扫描线拆开，用线段树计算合法的点。
注意，扫描线计算矩形面积并的时候，不需要下放标记，但是需要及时地清空被覆盖的点的贡献。
小结：
- 一定要注意对问题的初步感知，各种手玩可以帮助找出很多可能有用的性质；
- 问题存在明显的几何形式和代数形式，并且两种形式都比较简洁的话，注意数形结合；
- 可以欣赏一下这种递归式的证明方法；
代码
#include <cstdio>
#include <vector>
#include <utility>
#include <iostream>
#define rep( i, a, b ) for( int i = (a) ; i <= (b) ; i ++ )
#define per( i, a, b ) for( int i = (a) ; i >= (b) ; i -- )
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int MAXN = 2e5 + 5, MAXR = 1e6 + 5, MAXLOG = 18;
template<typename _T>
void read( _T &x )/*{{{*/
{
x = 0; char s = getchar(); int f = 1;
while( ! ( ‘0‘ <= s && s <= ‘9‘ ) ) { f = 1; if( s == ‘-‘ ) f = -1; s = getchar(); }
while( ‘0‘ <= s && s <= ‘9‘ ) { x = ( x << 3 ) + ( x << 1 ) + ( s - ‘0‘ ), s = getchar(); }
x *= f;
}/*}}}*/
template<typename _T>
void write( _T x )/*{{{*/
{
if( x < 0 ) putchar( ‘-‘ ), x = -x;
if( 9 < x ) write( x / 10 );
putchar( x % 10 + ‘0‘ );
}/*}}}*/
struct Rectangle/*{{{*/
{
int x1, y1, x2, y2;
Rectangle(): x1( 0 ), y1( 0 ), x2( 0 ), y2( 0 ) {}
Rectangle( int X1, int Y1, int X2, int Y2 ): x1( X1 ), y1( Y1 ), x2( X2 ), y2( Y2 ) {}
};/*}}}*/
typedef std :: pair<int, int> Range;
int contri[MAXN << 2], su[MAXN << 2], cov[MAXN << 2];
std :: vector<Range> vec[MAXN];
Rectangle restri[MAXR];
int mx[MAXN][MAXLOG], lg2[MAXN];
int preMn[MAXN], preMx[MAXN], sufMn[MAXN], sufMx[MAXN];
int A[MAXN], B[MAXN];
int N, M, tot;
int Query( const int l, const int r )/*{{{*/
{
if( l > r ) return - INF; int k = lg2[r - l + 1];
return std :: max( mx[l][k], mx[r - ( 1 << k ) + 1][k] );
}/*}}}*/
inline void Upt( const int x )/*{{{*/
{
su[x] = contri[x << 1] + contri[x << 1 | 1];
contri[x] = cov[x] ? 0 : su[x];
}/*}}}*/
inline void Add( const int x, const int delt )/*{{{*/
{
contri[x] = ( cov[x] += delt ) ? 0 : su[x];
}/*}}}*/
void Build( const int x, const int l, const int r )/*{{{*/
{
if( l > r ) return ;
if( l == r ) { contri[x] = su[x] = 1; return ; }
int mid = ( l + r ) >> 1;
Build( x << 1, l, mid );
Build( x << 1 | 1, mid + 1, r );
Upt( x );
}/*}}}*/
void Update( const int x, const int l, const int r, const int segL, const int segR, const int delt )/*{{{*/
{
if( segL <= l && r <= segR ) { Add( x, delt ); return ; }
int mid = ( l + r ) >> 1;
if( segL <= mid ) Update( x << 1, l, mid, segL, segR, delt );
if( mid < segR ) Update( x << 1 | 1, mid + 1, r, segL, segR, delt );
Upt( x );
}/*}}}*/
int Query( const int x, const int l, const int r, const int segL, const int segR )/*{{{*/
{
if( cov[x] ) return 0;
if( segL <= l && r <= segR ) return contri[x];
int mid = ( l + r ) >> 1, ret = 0;
if( segL <= mid ) ret += Query( x << 1, l, mid, segL, segR );
if( mid < segR ) ret += Query( x << 1 | 1, mid + 1, r, segL, segR );
return ret;
}/*}}}*/
int main()
{
read( N ), read( M );
int mxB = - INF, mnB = INF;
rep( i, 1, N ) read( A[i] );
rep( i, 1, M )
{
read( B[i] );
mxB = std :: max( mxB, B[i] );
mnB = std :: min( mnB, B[i] );
}
rep( i, 1, N )
if( A[i] + mxB < 0 )
restri[++ tot] = Rectangle( 1, i, i, N );
for( int i = 1, j ; i <= N ; i ++ )
if( A[i] + mnB < 0 )
{
for( j = i ; j <= N && A[j] + mnB < 0 ; j ++ );
restri[++ tot] = Rectangle( i, i, j - 1, j - 1 );
i = j - 1;
}
preMn[0] = sufMn[M + 1] = INF, preMx[0] = sufMx[M + 1] = - INF;
rep( i, 1, M )
preMn[i] = std :: min( preMn[i - 1], B[i] ),
preMx[i] = std :: max( preMx[i - 1], B[i] );
per( i, M, 1 )
sufMn[i] = std :: min( sufMn[i + 1], B[i] ),
sufMx[i] = std :: max( sufMx[i + 1], B[i] );
lg2[0] = -1; rep( i, 1, N ) lg2[i] = lg2[i >> 1] + 1;
for( int i = 1 ; i <= N ; i ++ ) mx[i][0] = A[i];
for( int j = 1 ; j <= lg2[N] ; j ++ )
for( int i = 1 ; i + ( 1 << j - 1 ) <= N ; i ++ )
mx[i][j] = std :: max( mx[i][j - 1], mx[i + ( 1 << j - 1 )][j - 1] );
rep( i, 1, N )/*{{{*/
{
int rMost = M, up = 1, l, r, mid;
if( A[i] + mxB >= 0 )
{
l = 1, r = M;
while( l < r )
{
mid = ( l + r ) >> 1;
if( A[i] + preMx[mid] >= 0 ) r = mid;
else l = mid + 1;
}
rMost = l - 1;
}
if( rMost > 0 )
{
if( preMn[rMost] + Query( 1, i ) >= 0 )
{
l = 1, r = i;
while( l < r )
{
mid = ( l + r + 1 ) >> 1;
if( preMn[rMost] + Query( mid, i ) >= 0 ) l = mid;
else r = mid - 1;
}
up = l + 1;
}
if( up <= i ) restri[++ tot] = Rectangle( up, 1, i, N );
}
int lMost = 1, dn = N;
if( A[i] + mxB >= 0 )
{
l = 1, r = M;
while( l < r )
{
mid = ( l + r + 1 ) >> 1;
if( A[i] + sufMx[mid] >= 0 ) l = mid;
else r = mid - 1;
}
lMost = l + 1;
}
if( lMost <= M )
{
if( sufMn[lMost] + Query( i, N ) >= 0 )
{
l = i, r = N;
while( l < r )
{
mid = ( l + r ) >> 1;
if( sufMn[lMost] + Query( i, mid ) >= 0 ) r = mid;
else l = mid + 1;
}
dn = l - 1;
}
if( i <= dn ) restri[++ tot] = Rectangle( 1, i, N, dn );
}
}/*}}}*/
rep( i, 1, tot )
vec[restri[i].x1].push_back( std :: make_pair( restri[i].y1, restri[i].y2 ) ),
vec[restri[i].x2 + 1].push_back( std :: make_pair( - restri[i].y1, restri[i].y2 ) );
LL ans = 0;
Build( 1, 1, N );
rep( i, 1, N )
{
for( int j = 0 ; j < ( int ) vec[i].size() ; j ++ )
{
int l = vec[i][j].first, r = vec[i][j].second;
int coe = l < 0 ? -1 : 1; l *= coe;
Update( 1, 1, N, l, r, coe );
}
ans += Query( 1, 1, N, i, N );
}
write( ans ), putchar( ‘\n‘ );
return 0;
}