LINK

给定有1e5个线段[l, r] (1 <= l <= r <= 1e9)
给定1e5个查询，对于每个查询K： 求所有包含K的线段里，最短的线段长度
{ [1, 4] [2, 4] [3, 5] [4, 5] }
K=4： 上面的所有的区间，都包含K。 最短的线段长度是[4,5] = 2

线段拆点

这个一个“线段拆点”的套路：
 比如有：interval { [1, 4]   [4, 5] }    Query = [ 3 , 4 ]
 我们拆成 interval.size() * 2 + Query.size() 个 “事件”
 所谓事件是：   {pos,  type,  msg}
 	pos： 坐标轴上的一维点。  {区间lef/rig点  或  query的点}
 	type：  0/1/2   表示{这个pos，是lef、rig、query}
 	msg：  如果是lef/rig点，存入该线段的长度； 否则，存入query的index
 	
		for(auto& v : A){
            events[M ++] = {v[0], 0, v[1] - v[0] + 1};
            events[M ++] = {v[1], 2, v[1] - v[0] + 1};
        }
        FOR(i, 0, Q.size() - 1, 1){
            events[M ++] = {Q[i], 1, i};
        }
  		sort(events, events + M, [](const auto& a, const auto& b) -> bool{
            if(a.pos != b.pos) return a.pos < b.pos;
            return a.type < b.type;
  ' 所以，type的顺序也很重要：[0是lef端点 < 1是query点 < 2是rig点] '
        });
        
  对所有event进行sort后， 用multiset来存 “当前”所有线段的长度：
    type=0：  将该线段的len（即msg），存入multiset里
    type=1：  '此时，multiset里所有的线段长度，其所指的线段 都是包含这个query点的！！ '
    		  输出， multiset.begin()即可
    type=2：  从multiset里，将该线段 清除！！！

VE<int> ans(Q.size(), -1);
multiset<int> lens;
FOR(i, 0, M - 1, 1){
    int pos = events[i].pos, type = events[i].type, msg = events[i].msg;
    if(type == 0){
        lens.insert( msg );
    }else if(type == 1){
        if(lens.size()){
            ans[ msg ] = *lens.begin();
        }
    }else{
        lens.erase( lens.find( msg ) ); ' multiset的erase某个量，是会把所有元素都erase的！！！ '
    }
}

线段树

暗存一个min_len[]数组， 然后遍历所有的线段， [l, r]
将： min_len[l, l+1, l+2, .., r] = min(self,  r-l+1);
最后，再遍历所有query  （即，区间修改  和  单点查询）
' 但： 1，线段长是1e9， 线段树是4e9 '
'  2，即使你把min_len[l,..,r]的过程，转换为： 对于query里的下标  '
'     此时， 就是一个1e5量级的问题。  '
'     但是，重点来了：   即便你对所有线段sort， min_len数组，并不是单调的！！！ '
'    意味着： 你执行“区间min/max”的时间，并不是logN的！！！！ '
'    这是重点！！！！    朴素的线段树 是处理不了的！！！ '


TODO：  动态开点线段树