「Codeforces 1080F」Katya and Segments Sets-主席树

发布于 12 天前  56 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「Codeforces 1080F」Katya and Segments Sets-主席树

Description

给定$n$个线段集,求$[a,b]$中的每个线段集中是否都存在一条线段$[l,r]$满足$[l,r] \in [x,y]$。

Solution

用主席树维护将所有左端点 $\leq x$ 的线段插入后,每个集合的右端点的最小值的最大值。

查询时判断$[a,b]$的最大右端点是否小于等于$y$即可。

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「Codeforces 1080F」Katya and Segments Sets-主席树


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前, 相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!