level 1
给定n个区间[lbk]x，y[rbk]
m个查询区间[lbk]st，ed[rbk]
对于每个查询，输出单个线段能覆盖该区间的最大长度
应该怎么解这个题？
2025年04月28日 16点04分
1
level 1
尝试了线段树区间合并
但是发现由于询问区间同时只能被一条线段覆盖
才疏学浅想不到合适的合并方案
2025年04月28日 16点04分
2
level 1
随后我有想对同一个查询区间，把线段分为三种类型
从询问区间左端点跨入右侧的
从询问区间右端点跨入左侧的
和完全包含于询问区间的
通过将这三种线段的覆盖最大长度取大得到该询问区间的答案
前两种跨过区间的可以通过将询问区间和线段排序后用单调队列求出
但包含于询问区间的线段的最大长度怎么求呢？
2025年04月28日 16点04分
3
level 1
今天想了一天只想到个错解：
线段按左端点排序，建立维护右端点的主席树。
通过二分合法左端点的范围，求主席树上的区间[l，r]中r+1的前缀
但这样不能保证拥有最大右端点的线段是最长的，因为其左端点可能离右端点很近
2025年04月28日 16点04分
4
吧务
level 10
3楼已解决了la≤lb/ra≥rb的情况,只剩lb<(≤)la≤ra<(≤)rb的情况,用二维数点
所有区间按(-l,r)升排,A组(n个那组)使树状数组的点r对其区间长度,B组(m个那组)查询树状数组[1,r]中的最大值即答案
2025年05月01日 01点05分
5