题目大意

给定 n 个平面坐标系上的矩形，保证矩形不会相交且每个矩形周围至少一个单位不会有矩形，求从(0,0)走到 (x0,y0) 且不经过矩形内部的点的最短曼哈顿距离。

Data Constraint n≤105,x0>0

题解

首先注意到，除了一种情况以外，其他情况都存在一种最优解不需要往右走，那么 x 方向的代价是确定的，现在的问题是如何计算y方向的代价。 考虑扫描线。用线段树维护一个函数，自变量是 y ，函数值就是从起点走到当前扫描线位置的纵坐标为y，在 y 方向上的最小代价。 对于一个矩形的右边界，(x,ly)→(x,ry)，显然我们需要修改 y 在[ly,ry]的函数值。可以二分出一个位置 w ，满足[ly,w]从 ly−1 走过来优， [w+1,ry] 从 ry+1 走过来优。然后只需要在线段树上区间赋值操作来修改即可。

时间复杂度： O(nlogn)

SRC

#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std ; #define N 100000 + 10 #define M 1000000 + 10 const int MINN = -1000001 ; const int MAXN = 1000001 ; struct Note { int a , b ; Note ( int A = 0 , int B = 0 ) { a = A , b = B ; } } ; struct Tree { int Son[2] ; bool flag ; Note tag ; } T[30*N] ; struct Line { int x , ly , ry ; } L[N] ; int n , x0 , y0 ; int Cnt = 1 , Root = 1 , ret ; bool cmp( Line a , Line b ) { return a.x < b.x ; } int NewNode() { ++ Cnt ; T[Cnt].flag = 0 ; return Cnt ; } void Update( int v ) { if ( !T[v].flag ) return ; if ( !T[v].Son[0] ) T[v].Son[0] = NewNode() ; if ( !T[v].Son[1] ) T[v].Son[1] = NewNode() ; int ls = T[v].Son[0] , rs = T[v].Son[1] ; T[ls].tag = T[rs].tag = T[v].tag ; T[ls].flag = T[rs].flag = 1 ; T[v].flag = 0 ; } int DIV( int x ) { int ret = x / 2 ; if ( x % 2 != 0 && x < 0 ) ret -- ; return ret ; } void Modify( int &v , int l , int r , int x , int y , Note tag ) { if ( x > y ) return ; if ( !v ) v = NewNode() ; if ( l == x && r == y ) { T[v].flag = 1 ; T[v].tag = tag ; return ; } Update(v) ; int mid = DIV( l + r ) ; if ( y <= mid ) Modify( T[v].Son[0] , l , mid , x , y , tag ) ; else if ( x > mid ) Modify( T[v].Son[1] , mid + 1 , r , x , y , tag ) ; else { Modify( T[v].Son[0] , l , mid , x , mid , tag ) ; Modify( T[v].Son[1] , mid + 1 , r , mid + 1 , y , tag ) ; } } void Query( int v , int l , int r , int x ) { if ( !v ) return ; if ( l == r ) { ret = T[v].tag.a * x + T[v].tag.b ; return ; } Update(v) ; int mid = DIV( l + r ) ; if ( x <= mid ) Query( T[v].Son[0] , l , mid , x ) ; else Query( T[v].Son[1] , mid + 1 , r , x ) ; } int main() { freopen( "bl.in" , "r" , stdin ) ; freopen( "bl.out" , "w" , stdout) ; scanf( "%d%d" , &x0 , &y0 ) ; scanf( "%d" , &n ) ; for (int i = 1 ; i <= n ; i ++ ) { int x1 , x2 , y1 , y2 ; scanf( "%d%d%d%d" , &x1 , &y1 , &x2 , &y2 ) ; L[i].x = max( x1 , x2 ) + 1 ; L[i].ly = min( y1 , y2 ) ; L[i].ry = max( y1 , y2 ) ; } sort( L + 1 , L + n + 1 , cmp ) ; Modify( Root , MINN , MAXN , 1 , MAXN , Note( 1 , 0 ) ) ; Modify( Root , MINN , MAXN , MINN , 0 , Note( -1 , 0 ) ) ; for (int i = 1 ; i <= n ; i ++ ) { if ( L[i].x > x0 ) break ; ret = 0 ; Query( Root , MINN , MAXN , L[i].ly - 1 ) ; int cost1 = ret , d = L[i].ly - 1 ; ret = 0 ; Query( Root , MINN , MAXN , L[i].ry + 1 ) ; int cost2 = ret , u = L[i].ry + 1 ; int l = L[i].ly , r = L[i].ry , w = L[i].ly - 1 ; while ( l <= r ) { int mid = DIV( l + r ) ; if ( cost1 + (mid - d) <= cost2 + (u - mid) ) l = mid + 1 , w = mid ; else r = mid - 1 ; } Modify( Root , MINN , MAXN , L[i].ly , w , Note( 1 , cost1 - d ) ) ; Modify( Root , MINN , MAXN , w + 1 , L[i].ry , Note( -1 , cost2 + u ) ) ; } ret = 0 ; Query( 1 , MINN , MAXN , y0 ) ; printf( "%d\n" , x0 + ret ) ; return 0 ; }

以上.