gui vfk. 在hdsdfz听讲过的题. 可持久化seg tree优化建边.好像一句话就能说清楚啊. 然后证明了我的网络流的姿势严重不科学ovo 然后bzoj上样例居然是图片ovo于是附上手打的样例ovo 10 0 1 7 3 9 2 7 4 0 9 10 5 1 0 4 2 10 2 7 9 1 5 7 2 6 3 5 3 6 2 6 6 4 1 8 1 6 1 6 0 6 5 2 2 5 0 9 3 5 1 3 0 2 5 5 6 7 1 1 2
有点像xyz在wc的时候讲的动态图连通性问题.不过这个看上去要水些啊. 考虑建一棵生成树,那么所有剩余的边覆盖了的边就不是桥.如果没有被覆盖就是桥. 于是这个题可以倒过来,支持加边和查询两点间没有被覆盖的边数. 似乎挺水. 完了.
idy又开坑辣,虽然是个无聊的无聊题. 考虑每条路径会被哪些路径包含.那条路径的两个端点一定是在条路径的两个端点的子树上.(如果这两个点有祖先关系,那么需要重新makeroot一下) 当然我不是说要用Lct.直接用可持久化线段树在dfs序上把路径存下来就完了.
迷之数据结构.我的想法比较简单,确定一个值b,对所有小于b的k建线段树维护,对大于b的k直接朴素找. 于是时间复杂度算起来比较迷. 试了一下发现b取20的时候能过.虽然还是跑得最慢的一个.无语喽.大概我不是正解.
又是idy开的坑。感觉回去要被他吊打致残。 树分治。最开始想用二分，然后直接去每个分治点上查询。这样的总复杂度是O(n*log3n)的。不过感觉常数比较小而且绝对省代码，只用二分不用数据结构。然后发现要输出所有的边。这个算法要用容斥一样的东西来减，根本搞不定。 于是向mhy学习。使用类似noi那个超级钢琴的思路，每次把最大的一条路径找出来，然后找它的替代品。树分治后，对于每一个树上的团，算出它的dfs序。默认一个点与dfs序在它前面的区间中最深的连边。这样就可以保证不重，也比较好写。然后用堆来维护。堆中一个点需要记录的信息是这个点的答案，线段树的根，左右端点，这个点到分治团的根的距离。然后每次找出一个最大的之后把它的区间再折成两半扔回堆里就好啦。 比较神的做法。感觉我自己是想不出来的。要是考场上遇到还真会出事呢。郁闷ing。
迷一样的欧拉序列的题。然后似乎只有岛君的题解能看啊233。 其实就是在欧拉序列上，两点u,v之间的距离=(dfb[u], dfe[v]]之间未匹配的括号数（左开右闭）。其中dfb表示左括号的位置，dfe表示右括号的位置。 然后就是写一个线段树去维护了。写得比较丑，把所有数对都记下来了。其实只用记和跟差就行了。然后要强制如果一端是空的那么这个点就不能作为端点。完了。 然后dfs这一步越写越短了，开心hhh。 于是代码巨长还巨丑还巨慢。
很早之前就看过的题。一直被数据范围吓到，然后感觉也比较难写所以都没写。后来发现还是挺好的。 就重链dfs序维护一下每个位置的和，然后可持久化一下就完了。然后一个常数优化是如果这个点是在这次修改的时候建的，那么就直接覆盖而不是新建点。然后跑得就比较快了。
水水的cdq。久了不写练一下手。然后发现犯了一堆逗错。幸好没过样例不然就do big die了。
原来备案还没过。那之前是怎么成功访问的囧。 写了一晚上。教训还是之前那个，写之前要想清楚。写完再去改就很烦。自己yy了很久，虽然最初是听了mhy的一句提醒。好有危机感。 首先这个东西可以离线。之前一直在想在线怎么做然后也觉得没法做。 把询问按右端点排序之后问题就转化成了左端点在一个范围里的时候的最大子段。 然后用一个线段树表示从i到current right的时候的和，这个玩意可以直接区间加。然后再去维护这个东西的历史最大值。于是就变成了每个位置上接了一个add序列，要找它的前缀最大值。那么只需要存两个东西：当前的和以及当前的最大前缀和，就可以合并了。 然后线段树上维护两个add序列，分别是对整个线段的lazy tag of add和max value of son。就可写了。 然后好像跑得很慢啊TT。
自己出的题还要写题解。 就是化成可以二分的形式，然后发现是找凸壳上x=x0的时候的最大值的和，看它是否大于0。 于是就写呗。据说很难写。我觉得写起来还行啊。 其实主要是为了测试系统用的。