【CF1080F】Katya and Segments Sets


题意

给出\(k\)条线段,位于区间\([l,r]\)且属于集合\(x\),每次询问在集合\([a,b]\)中的所有集合是否存在至少一个线段被\([l,r]\)包含。

分析

对题目做一个转换,变成对于所有右端点\(\le r\)的区间中的左端点的最大值是否\(\ge l\),如果是的,那么显然至少存在一个区间被包含。

那么对于区间\([a,b]\),显然是这个区间中每个集合左端点最大值的最小值应该要\(\ge l\)。

我们不妨用线段树中的结点来记录。线段树的单点记录一个集合的左端点的最大值,于是询问一个集合的区间,直接询问线段树的区间最小值。

而对于所有右端点\(\le r\)的区间的处理办法就是用主席树,按照所有区间\(r\)的生序依次插入线段树即可。

  • 数组下标越界返回了 WA ,自闭了好久。

 

You may also like

【BZOJ3545】Peaks

【CEOI2011】Matching

LEAVE A COMMENT

Statistics

  • 0
  • 8,099

Categories

Archive

Comments