「Gym102759B」Cactus Competition

题目

点这里看题目。

分析

非常好的一道题目。

我们不妨先考虑一个弱化的问题：根据题目给定的数据，如何判断 ((1,1)) 能否到达 ((n,m))。

通过各种手玩可以得到下面四种情况会导致无解：

  1. 存在某一行无法通行，也即 (exist 1le xle n)，使得 (forall 1le yle m, A_x+B_y<0)；

  2. 存在某一列无法通行，也即 (exist1le yle m)，使得 (forall 1le xle n,A_x+B_y<0)；

  3. 起点被堵住，也即 (exist(x,y),1le xle n,1le yle m)，使得 (forall 1le ile x,A_i+B_y<0)，以及 (forall 1le jle y,A_x+B_j<0)。

  4. 终点被堵住，也即 (exist(x,y),1le xle n,1le yle m)，使得 (forall xle ile n,A_i+B_y<0)，以及 (forall yle jle m,A_x+B_j<0)。

但是，似乎所有无解的情况都可以被归纳到上面四类中的一类或者多类。

如果仅仅是简单地完成题目，那么我们可以通过多检测几组数据来验证这一性质；经过多种验证，大可认为它是对的。

作为一份并不会那么严谨的题解，这里将给出证明，读者自可略过：

证明：如果上面四类情况均不成立，则 ((1,1)) 一定可以到达 ((n,m))。

注：证明过程的图片均来自于比赛的官方题解。

如果情况 1,2 均不成立，那么容易得到 (min_x A_x+max_y B_yge 0,max_xA_x+min_yB_yge 0)。

注意到，如果我们取出 (p,A_p=max_xA_x) 和 (q,B_q=max_y B_y)，那么 ((p,q)) 所在的一行和一列必然都可以互相到达：

Figure1.png

那么这个时候，一条合法的路径一定会从 ((1,1)) 到达蓝色区域的某一个位置，最后一定会从黄色区域的某一个位置到达 ((n,m))。

由于从 ((1,1)) 到蓝色区域和从黄色区域到 ((n,m)) 是完全对称的，所以我们可以使用同样的方法证明；下面我们说明，((1,1)) 一定可以到达蓝色区域。

如果我们不能到达蓝色区域，那么在 ((1,1)) 到 ((p-1,q-1)) 这 ((p-1) imes (q-1)) 的区域中，一定存在一行和一列不能通过：

Figure2.png

但是注意到，如果选取 ((x,y)) 为不能通过的一行一列的交点，那么这就可以被归入情况 3，不符合条件；或者，如果仅存在不能通过的一行或者一列，并且它覆盖了 ((1,1))，那么也可以被归入情况 3，不符合条件。

由于不能通过的一行和一列不能同时存在，不妨假设不存在不能通过的一行，那么就满足 (forall 1le x<p,exist 1le y<q,A_x+B_yge 0)，转化一下得到 (min_{1le x<p}A_x+max_{1le y<q}B_yge 0)。这个时候取出 (max_{1le y<q}B_y) 所在的一列，就可以发现这一列是可以互相到达的，而不存在不能通过的一列的情况同理：

Figure3.png

此时 (max_{1le y<q}B_y) 所在的一列也一定可以到达原先的蓝色区域，所以也可以将这一行看作蓝色。

这个时候，我们就可以缩减问题的规模，只保留最靠左的蓝色列和最靠上的蓝色行；循环这个步骤，直到 ((1,1)) 被覆盖，那么能得出 ((1,1)) 可以到达蓝色区域，证明结束。

现在我们得知情况数有限，我们就可以将这四种情况一一转化为对于起终点的限制。

  1. 如果从 ((S,1)) 到 ((T,m)) 存在一行无法通行，不妨为 (i) 这一行，那么就有 (A_i+max_y B_y<0)，此时所有 (1le Sle ile Tle n) 都无法通行。

  2. 如果从 ((S,1)) 到 ((T,m)) 存在一列无法通行，就说明 (exist 1le yle m,forall Sle xle T,A_x+B_y<0)，转化一下得到 (forall {Sle xle T},min_yB_y+A_x<0)。所以，我们可以算出若干个 (x) 的区间 ([l_1,r_1],[l_2,r_2],dots,[l_k,r_k])，在区间 (i) 中有 (forall xin [l_i,r_i],A_x+min_yB_y<0)。这样，如果 (S,T) 落在了一个区间里面，它们就一定会被一列阻隔。

  3. 如果从 ((S,1)) 到 ((T,m)) 的时候，起点被一个十字的左上角堵住了。由于十字由它的中心 ((x,y)) 来确定，并且我们只需要让十字阻挡第一列，我们可以枚举 (x)，并尝试最大化十字的竖边。

    即，我们首先需要找到最小的 (j)，使得 (A_x+B_jge 0)，这样 (y<j)；为了最大化竖边，我们可以直接取 (B_y=min_{1le k<j}B_k) 的 (y)。接着，我们就可以找到最大的 (i)，使得 (A_i+B_yge 0)。那么，当十字的中心在第 (x) 行上的时候，最小能被覆盖的行就是第 (i+1) 行。

  4. 这个情况与情况 3 完全对称，可以相似地解决。

注意到，四种情况经过转化，其覆盖的起点和终点都是一段区间。如果将 ((S,1),(T,m)) 转化为平面上的点 ((S,T))，每种情况的限制会变成一个矩形。此时矩形限制就可以用扫描线拆开，用线段树计算合法的点。

注意，扫描线计算矩形面积并的时候，不需要下放标记，但是需要及时地清空被覆盖的点的贡献。

小结：

  1. 一定要注意对问题的初步感知，各种手玩可以帮助找出很多可能有用的性质；
  2. 问题存在明显的几何形式和代数形式，并且两种形式都比较简洁的话，注意数形结合；
  3. 可以欣赏一下这种递归式的证明方法；

代码

#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( '
' );
	return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/crashed/p/15145360.html