HZOJ
写在前面
信心场？终于踩线300pts了（虽然重测后差了点）。我竟然还有今天，场切3道。虽然有数据水的原因但是那只有T3。然后现在的状态是饿饿饿饿饿饿，不知道干啥，遂先把这个写了。
《Lullaby》祝今夜好梦
기다리지 않기로 했잖아
不是决定好不等待了吗
울지 않을 거라고 그랬잖아
不是说不会再哭泣了吗
너무 늦은 밤이야
过深的夜呀
오 너무 긴 이별이야
噢 太过漫长的离别呀
잠시만 더 이렇게 있을까
再过一会儿 还会如此吗
그래 잊혀져 버릴 꿈이지만
是啊 虽然是全数忘却的梦
눈을 감아 마지막
闭上双眼 最后一次
잠을 재워 줄게
哄你入睡
My lullaby
Baby sweet goodnight
무서운 꿈은 없을 거야
不会再有可怕的梦了
너의 끝나지 않는 긴긴 하루를
把你没有尽头 漫长的一天
이제는 그만 보내주렴 음
现在都送走吧 Um
가만히 끌어안고 있을까
在静静地拥抱吗
어느 사이 끝나 가는 꿈이지만
虽然是不知道何时结束 消失殆尽的梦
마음 놓아 마지막 노랠 불러 줄게
放下心来 给你唱最后的歌曲
My lullaby baby
Sweet good night
무서운 꿈은 없을 거야
不会再有可怕的梦了
너의 끝나지 않는 긴긴 슬픔을
把你没有尽头 漫长的悲伤
이제는 그만 보내 주렴
现在都送走吧
잠들지 못해
无法入睡
지친 숨소리가 잦아들 때까지
到疲倦的声音归于平静为止
소란한 너의 밤을 지킬게
会守护着你嘈杂的夜晚
I’ll be nearby
Baby sweet goodnight
항상 네 곁에 있을 거야
会一直在你身边的
더 만날 수 없는 지난날들도
把再也无法相遇的 那些过去的日子
이제는 그만 놓아 주렴
现在都放下吧
My edelweiss
Baby sweet good bye
모두 잊어도 돼
把一切都忘记也可以
다 괜찮아 괜찮아 놓아
没关系的 一切都没关系的 放下吧
A. 最小生成树（tree）
算签到题吧？虽然写了一个多小时。题意是每次给出三元组\((l,r,w)\)，代表\([l,r]\) 区间内每个点对间连一条权值为\(w\) 的边。求问这张图的最小生成树的值是多少。
其实算一下子出思路吧？根据定义我们会选\(n-1\) 条边使整张图连通。参克鲁斯卡尔采用并查集的方式维护连通块，再加上显然小权值的边数一定选得多，就是能选必选，所以我们一定是一段一段的合并的。我们就将这道题转化为了区间查询颜色种类数和区间推平的问题。考虑到我们至多合并\(n-1\) 次，我们就可以暴力查找下一个不同颜色的区间。然后在线段树上可以更方便地进行这些操作。
B. 最短路（roads）
神仙题。写了inf分钟的线段树优化建图没写完，回溯代码到树的特殊性质速度太慢了导致差1秒就交上了，喜挂20pts、、、题意是给出一张有向图，给出每条边的\(a,b\)，若该边的前驱的\(a\) 小于了当前边的\(a\)，则该边的边权为\(a-b\)，否则为\(a\)。求问以1为起点到所有点的最短路。
有后效性我真没招了。朝着每个点拆点前后连边的方向想了半天没有一点进展。然后其实正解就算个半裸的dijkstra。首先我们可以知道，对于一个点的两条入边，若前者距离不大于后者，且前者\(a\) 不大于后者\(a\)，那我们肯定选择\(a\) 小的那个。所以我们考虑将一个点多次进队列然后松弛其出边所连的点。然后因为多次遍历到一个点\(dis\) 肯定是增大的，所以我们保证\(a\) 减小即可。然后这样可能通过松弛得到更优解的部分就只有\(a\) 属于当前入边\(a\) 和上一个入边\(a\) 之间的出边，我们只对这部分松弛即可。然后由于我们保证了\(a\) 单减，所以每个点至多只会入队其入度次；然后限制了松弛范围，那么每条边至多被松弛两次，第一次是在初始时，第二次是在松弛区间内。所以这样做的复杂度的正确性是能保证的。然后代码就是个裸的dijkstra改成多次入队松弛即可。
C. 计算任务（mission）
原数据水到暴力能满？题意是给出两种类型操作。1.给出一个任务及其所需时间，限制其在某\(k(k<=3)\) 台计算机上完成；2.给出某台计算机工作的时间。每台计算机可以同时执行多个任务。求问这次工作后能完成多少任务。
因为想写T4，然后写完暴力就跑。其实正解实现也不难，就是个折半警报器。注意到\(k<=3\)，考虑将每个任务平均分配到其对应的计算机，当某个计算机超过了阈值就全部取出判是否还有剩，如果有剩就再平均分配再插进对应计算机的结构。然后我用的是set取begin。为了防止阈值为0的卡死程序所以要开个临时数组存一下重新插的任务，等跑完一组后再插。
D. 树上纯树（ture）
第一次赛时A掉T4。感谢李超树。虽然是原，但是窝竟然一遍写对了动态开点李超树+线段树合并。%%%%%%