第一遍审题：
T1：？？？暴力似乎也不可做
T2：暴力暴力暴力！
T3：嗯，扫描线？线段树会被卡，于是——
一般人：离散化
本蒟蒻：平衡树
另：看T2时：欸怎么交的这么晚？略略一翻：提交时间和结束时间一样可海星
切题ing
于是我愉快的抄起我从没拿来写过题的Treap头铁平衡树。
实际模板上几乎都没写过，还边写边想FHQ Treap更好写-
但没关系，反正只需要支持加点和查询。 没错我不会删除
2h后：我平衡树调出来了！！！ （然并不
噢时间调过来了，我只剩一小时了qwq。
光速写完T2 \(O(n^3q)\) 暴力
看看第一题，嗯好像可以迭代加深套一个最短路？
写了一点：欸好像不用迭代加深直接跑？
欸好像是正解！
然没得时间写Dijkstra了，于是果断选择SPFA，赌吧！
并意会了有效T的上界 \(\max{\{m_i\}/C/2}\) （然也是错的
于剩5分钟时交完了3道题。
T1：期望：30 我是有多不信任SPFA 实际：90.9 噢，卡SPFA （然并不是
T2：期望：30 实际：6.7 emm
T3：期望：100 我是有多信任自己的Treap 实际：26.7 （意料之中，希望之外
T1：有效T的上界 \(\max{\{m_i\}/C/2}\) 是错的，正确的是 \(\max{\{m_i\}/C/2+1}\)
? +1！！！坑了我9.1分qwq
T2：神奇DP（递推？），emm
T3：然后我继续头铁平衡树 头都烂了 肝了2h后，我对了！我对了！！
然后我去翻了翻题解，离散化？树状数组？？
原地爆炸
emm，就当练习平衡树。
原文：https://www.cnblogs.com/groundwater/p/12682710.html