2017-Sp183-team2

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

 [[Image(1.png,500px)]]
== 流水账 ==
出门各自看题，cjb判断J直接暴力就行了，然而感觉暴力很难写，于是cjb抄了个lct，然后yzc wa了2发，万脸懵逼，痛失一血。cjb和sub确认了G的做法，上机写G，'''G1y66'''。然后cjb抄了个二维最近点对，'''I1y76'''。yzc上机拍J，发现了沙雕错误，'''J3y84'''。然后sub似乎推出了D的模型，cjb继续上机抄Treap，然后wa了一万发，最后发现sub下标推错了一位，'''D4y141'''。然后cjb又被sub赶上机抄最小乘积模型，然后sub上机改写，'''A2y152'''。cjb和sub讨论F，sub上机wa了，下机拍了拍'''F2y203'''。之后yzc尝试推E的模型，上机写了个暴力wa了，之后sub推好了C，上机'''C2y267'''。yzc间隔上机把模型改对了，结果tle了，和sub讨论如何用数据结构正确维护，没有在结束前调出corner case，最后发现做法有点不太对，还是要主席树，然后是维护的式子不是最终正确版。
== 总结 ==
=== chenjb ===
抄了一万个板子，累累。G这种模型非常常见啊，感觉自己写了好多次。yzc的E还是蛮可惜的，不过离通过估计还差至少30min吧，自己没能帮上太多的忙，有点不应该。
=== oipotato ===
=== subconscious  ===

== 题解 ==
 * A：最小乘积模型，对每个人配权值是ax+by，二分a/b往左右递归直到解得形式不再变化，取下凸壳上所有解即可。

 * B：

 * C：分治乘得到原始答案，新增一个数对答案影响是乘上一个p/q，可以发现只有sqrt(n)种不同变化，分母可以用前缀和得到结果，分子只要O(n)加起来就可以得到结果，复杂度为 O(nlog2n+nsqrt(n))

 * D：可以发现原题相当于对区间(l,r)求平方和及将(l+1,r)翻转，Treap维护即可。

 * E：考虑strongly，将串反着插入SAM，则对于每个点，假设其长度区间为[L,R]，则ab串长可以取[L,R]，a的串长可以取[L,R]，统计完即可。接着考虑不满足strongly但是满足weakly的那些串，显然是parent树上的祖先除了当前子树之外最靠后的位置（对应原串为最靠前），则当且仅当ab长度达到这个出现位置+1时，这个ab串合法，于是可以得到贡献的式子。在dfs过程中用主席树维护相应信息即可。注意，dfs建主席树过程中，如果2N个节点产生的主席树节点全都保持，需要4*2NlogN个节点（因为有两次单点修改，一次区间修改），内存不够。所以需要在递归完子树之后重置主席树节点计数器（相当于内存回收），或是用vector维护可撤销的线段树，因为parent树最深深度只有N，所以这样可以节省一半的空间。重置计数器已尝试并通过，vector方法没有尝试，不知道会不会由于实现原因导致内存偏大无法通过。

 * F：2^5^枚举0/1代入，如果有两个mask只有一个2进制位不同且行列式结果不同，可以线性构造出解，否则显然无解。

 * G：按左边点度数分>=sqrt或<sqrt计算，先计算sqrt个大点，枚举所有边统计答案，然后将这些有关大点的边删去，之后枚举右边所有点，枚举其相关的左边的点，然后继续枚举边计数。

 * H：

 * I：二维最近点对输出方案。

 * J：LCT直接维护。

 * [wiki:2016-E30-team1]

 * [https://wiki.icpc.camp/wood-cube/Petrozavodsk%20Winter-2014%20Moscow%20SU%20Tapir Wood Cube]

流水账

出门各自看题，cjb判断J直接暴力就行了，然而感觉暴力很难写，于是cjb抄了个lct，然后yzc wa了2发，万脸懵逼，痛失一血。cjb和sub确认了G的做法，上机写G，G1y66。然后cjb抄了个二维最近点对，I1y76。yzc上机拍J，发现了沙雕错误，J3y84。然后sub似乎推出了D的模型，cjb继续上机抄Treap，然后wa了一万发，最后发现sub下标推错了一位，D4y141。然后cjb又被sub赶上机抄最小乘积模型，然后sub上机改写，A2y152。cjb和sub讨论F，sub上机wa了，下机拍了拍F2y203。之后yzc尝试推E的模型，上机写了个暴力wa了，之后sub推好了C，上机C2y267。yzc间隔上机把模型改对了，结果tle了，和sub讨论如何用数据结构正确维护，没有在结束前调出corner case，最后发现做法有点不太对，还是要主席树，然后是维护的式子不是最终正确版。

总结

chenjb

抄了一万个板子，累累。G这种模型非常常见啊，感觉自己写了好多次。yzc的E还是蛮可惜的，不过离通过估计还差至少30min吧，自己没能帮上太多的忙，有点不应该。

oipotato

subconscious

题解

A：最小乘积模型，对每个人配权值是ax+by，二分a/b往左右递归直到解得形式不再变化，取下凸壳上所有解即可。
B：
C：分治乘得到原始答案，新增一个数对答案影响是乘上一个p/q，可以发现只有sqrt(n)种不同变化，分母可以用前缀和得到结果，分子只要O(n)加起来就可以得到结果，复杂度为 O(nlog2n+nsqrt(n))
D：可以发现原题相当于对区间(l,r)求平方和及将(l+1,r)翻转，Treap维护即可。
E：考虑strongly，将串反着插入SAM，则对于每个点，假设其长度区间为[L,R]，则ab串长可以取[L,R]，a的串长可以取[L,R]，统计完即可。接着考虑不满足strongly但是满足weakly的那些串，显然是parent树上的祖先除了当前子树之外最靠后的位置（对应原串为最靠前），则当且仅当ab长度达到这个出现位置+1时，这个ab串合法，于是可以得到贡献的式子。在dfs过程中用主席树维护相应信息即可。注意，dfs建主席树过程中，如果2N个节点产生的主席树节点全都保持，需要4*2NlogN个节点（因为有两次单点修改，一次区间修改），内存不够。所以需要在递归完子树之后重置主席树节点计数器（相当于内存回收），或是用vector维护可撤销的线段树，因为parent树最深深度只有N，所以这样可以节省一半的空间。重置计数器已尝试并通过，vector方法没有尝试，不知道会不会由于实现原因导致内存偏大无法通过。
F：2⁵枚举0/1代入，如果有两个mask只有一个2进制位不同且行列式结果不同，可以线性构造出解，否则显然无解。
G：按左边点度数分>=sqrt或
H：
I：二维最近点对输出方案。
J：LCT直接维护。
2016-E30-team1
Wood Cube

附加文件

1.png by chenjb