扫描线细节问题求助
查看原帖
扫描线细节问题求助
281668
FOX_konata楼主2022/11/25 09:04
  1. 为什么扫描线pushup部分的ans记录是b[ r + 1 ] - b[ l ],而不是b[ r ] - b[ l - 1 ], 例:
inline void push_up( ll p ){
	ll l = trees[ p ].l , r = trees[ p ].r;
	if( trees[ p ].num )
    trees[ p ].ans = b[ r + 1 ] - b[ l ];
	else
    trees[ p ].ans = ( l == r ) ? 0 : trees[ ls ].ans + trees[ rs ].ans;
	return ;
}

而不是

inline void push_up( ll p ){
	ll l = trees[ p ].l , r = trees[ p ].r;
	if( trees[ p ].num )
    trees[ p ].ans = b[ r ] - b[ l - 1 ];
	else
    trees[ p ].ans = ( l == r ) ? 0 : trees[ ls ].ans + trees[ rs ].ans;
	return ;
}
  1. 为什么扫描线修改部分是修改离散化后的l'~r'-1,而不是在离散化时存进l和r-1,然后处理离散化后的,例:
For( i , 1 , n ){
	read( x_1 ) , read( y_1 ) , read( x_2 ) , read( y_2 );
	b[ ++ len_b ] = x_1;
	b[ ++ len_b ] = x_2;
}
//      离散化
For( i , 1 , cnt - 1 ){
	int l' = ask[ i ].l离散化后,r'同理
	线段树修改区间[ l' , r' )
}

而不是

For( i , 1 , n ){
	read( x_1 ) , read( y_1 ) , read( x_2 ) , read( y_2 );
	b[ ++ len_b ] = x_1;
	b[ ++ len_b ] = x_2 - 1;
}
//      离散化
For( i , 1 , cnt - 1 ){
	int l' = ask[ i ].l离散化后,r'同理
	线段树修改区间[ l' , r' ]
}

各位大佬求助

2022/11/25 09:04
加载中...