删帖秒置顶。
WD与地图
好题，喵喵题，但是代码有一些毒瘤。
看看题面。要求我们维护 333 个操作。
> 1 a b 表示政府废弃了从 aaa 连向 bbb 的边，保证这条边存在。
> 2 a b 表示政府把钱用于建设城市 aaa，使其发达程度增加 bbb。
> 3 a b 表示政府希望知道 aaa 城市所在地区发达程度前 bbb 大城市的发达程度之和。如果地区中的城市不足 bbb 个输出该地区所有城市的发达程度总和。
删除边是图一个很恶心的性质，考虑转化。注意到后面两个性质一个是查询，一个是可逆修改，因此可以把时间倒转，第二个操作变成将发达程度减少 bbb ，废弃边改为添加边。
以下是该题的难点。
> 两个点 u,vu,vu,v 在一个地区当且仅当 u,vu,vu,v 可以互相到达。
如果在同一地区的定义是两点互相连通，有向边改为无向边，那么这题就是一道水到不能再水的水紫，用线段树合并维护后面两个操作就行了，基本和 [HNOI2012] 永无乡 一样，不能 0s0s0s 想出做法、60min60min60min 写出代码、5min5min5min 调试完的小朋友们 NOIp\text{NOIp}NOIp 死灭洄游记得远离盘子汗、通锐气等人。
但是要求 u,vu,vu,v 可以互相到达，也就是说我们要确保两点在同一个强连通分量里。可以转化成上面的简化版问题吗？如果我们知道每一条边的两个端点什么时候被缩进同一个强连通分量里，将这些边作为无向边，出现时间改成两点缩进同一个强连通分量的时间就可以按上面的做法做了。接下来考虑怎么求两点什么时候在同一个强连通分量里。注意到如果暴力加边、Tarjan\text{Tarjan}Tarjan 和查询，时间复杂度是 O(nm)O(nm)O(nm) 的，但是这个答案是可二分的，因此：
（或者 ）
先考虑暴力整体二分，每次直接将所有出现时间大于 midmidmid 的边加入。明显是正确的，那么如何优化？
注意到每次二分的查询区间 [ql,qr][ql,qr][ql,qr] 里的边才是有效的。为什么？因为进入缩点更早的边可以在前面整体二分时先用并查集缩点，然后就不用考虑了。进入缩点更晚的边是没有用的，根据强连通分量的性质这些边不会为更多点在 midmidmid 以前进入强连通分量做出任何贡献。然后这个进入缩点的时间在整体二分中按照答案区间 [ql,qr][ql,qr][ql,qr] 刻画。这样我们只用加入当前询问区间中出现时间小于 midmidmid
的边（询问和修改是一体的），时间复杂度正确，剩下的就是用并查集跑缩点，但是我们这个整体二分在跑左边（原顺序，没有打乱）时需要右区间被缩点，而跑右区间时又需要右区间不被缩点，然后整体区间也要先缩一次小于等于 midmidmid 的点，所以需要先求解左儿子，然后撤销缩点求右儿子，这样就需要可撤销并查集，时间复杂度为 O((n+m)log2(n+m)+mlogV)O((n+m)\log^2 (n+m)+m\log V)O((n+m)log2(n+m)+mlogV).
还能再优化。可撤销并查集很难看，能够省略它吗？考虑 hopebetter 启动注意到我们需要维护的性质比并查集好，并不需要资瓷集合的再次合并，因此只需要在每次整体二分中把左区间的所有点替换成所属的强连通分量的编号即可，右区间不做这个操作。这样你就得到了一个 O((n+m)log(n+m)+mlogV)O((n+m)\log (n+m)+m\log V)O((n+m)log(n+m)+mlogV)， 同时也是世界上最可爱的猫娘。
代码贴一下，不要认真研读，格式很难看并且基本是题解写法并且思路很不清晰，这一道题截至 2026/5/2 已经有 1.20k1.20k1.20k 提交了，用来 ctj 也容易被逮捕的。
Ps：这题的时间限制很宽松，没有人单个测试点卡到 1.5s1.5s1.5s 以上。空间限制是为线段树合并准备的。我在第二页不用找了。
第一发 NOI/NOI+/CTSC,果然是献给了整体二分呢。整体二分好可爱啊！
因为曼城茶座太可爱了，下面放几只曼城茶座。
