社区讨论

扫描线细节问题求助

FFOX_konata
P5490【模板】扫描线 & 矩形面积并参与者 2已保存回复 1

讨论操作

快速查看讨论及其快照的属性，并进行相关操作。

当前回复
1 条
当前快照
1 份
快照标识符
@lo7gvxrh
此快照首次捕获于
2023/10/27 01:37
2 年前
此快照最后确认于
2023/10/27 01:37
2 年前
查看原帖
  1. 为什么扫描线pushup部分的ans记录是b[ r + 1 ] - b[ l ]，而不是b[ r ] - b[ l - 1 ]， 例：
CPP
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 ;
}
而不是
CPP
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，然后处理离散化后的，例：
CPP
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' )
}
而不是
CPP
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' ]
}
各位大佬求助

回复

共 1 条回复，欢迎继续交流。

正在加载回复...