2017-Sp260-team2

从 Trac 迁移的文章

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

原文章内容如下：

 [[Image(1.png,500px)]]

== 流水账 ==
cjb上机签到'''B10y1'''，yzc上机'''C1y14'''，cjb上机'''G2y20'''。之后写A，悬线法搞了之后tle了，fix的过程中发现做法有点问题，fix之后'''A4y79'''。之后sub上机写J，'''J1y98'''。yzc上机写E，'''E1y116'''。cjb上机试图kdt，yzc想到了很好写的三维树状数组，'''D1y141'''。三人一起开I，发现题意有偏差，实际上是sb题，yzc上机'''I1y189'''。sub上机写F，cjb和yzc开出了H，封榜后'''F1y270'''，赛后10min过H AK。
=== chenjb ===
今天总体都不错，赛后10minAK有点可惜，但是中间时间利用也没啥问题。
=== oipotato ===

=== subconscious  ===

== 题解 == 
 * A：如果一个人的下面的左右区间和它一样，这个点就不是极大，如果它上一个和它高度一样的人左右区间和它一样，那它就重复，不然就统计答案。

 * B：枚举每个人，考虑它的贡献区间是[1,nxt-1]。

 * C：分成4块，右下角取反。

 * D：三维树状数组。

 * E：线段树将存活区间分成log段，然后用可撤销的并查集维护连通性。

 * F：把容斥式拆开，化简得到一个有关于所有线段上下分别有多少点的式子，注意贡献。

 * G：暴力贪心用stack维护。

 * H：考虑矩阵乘法维护，在树链剖分上跳的时候，最后一次是dfs序上一个矩阵的积，这个可以通过线段树预处理拿出log个矩阵，除此之外，每次跳跃都是当前重链的一个前缀或者后缀的矩阵积，也可以用n*40^3^预处理，最后拿出初始向量依次乘上这log个矩阵，复杂度是n*40^3^+qlogn*40^2^。

 * I：对于一个点x，相当于x的dfs序的那个位置，在[l,r]这个区间中+1，每个询问相当于x的子树的dfs序区间[l,r]的和，这是个裸的二维数点。

 * J：O(l)预处理出组合数，然后m^2^dp容斥。

流水账

cjb上机签到B10y1，yzc上机C1y14，cjb上机G2y20。之后写A，悬线法搞了之后tle了，fix的过程中发现做法有点问题，fix之后A4y79。之后sub上机写J，J1y98。yzc上机写E，E1y116。cjb上机试图kdt，yzc想到了很好写的三维树状数组，D1y141。三人一起开I，发现题意有偏差，实际上是sb题，yzc上机I1y189。sub上机写F，cjb和yzc开出了H，封榜后F1y270，赛后10min过H AK。

chenjb

今天总体都不错，赛后10minAK有点可惜，但是中间时间利用也没啥问题。

oipotato

subconscious

题解

• A：如果一个人的下面的左右区间和它一样，这个点就不是极大，如果它上一个和它高度一样的人左右区间和它一样，那它就重复，不然就统计答案。
• B：枚举每个人，考虑它的贡献区间是[1,nxt-1]。
• C：分成4块，右下角取反。
• D：三维树状数组。
• E：线段树将存活区间分成log段，然后用可撤销的并查集维护连通性。
• F：把容斥式拆开，化简得到一个有关于所有线段上下分别有多少点的式子，注意贡献。
• G：暴力贪心用stack维护。
• H：考虑矩阵乘法维护，在树链剖分上跳的时候，最后一次是dfs序上一个矩阵的积，这个可以通过线段树预处理拿出log个矩阵，除此之外，每次跳跃都是当前重链的一个前缀或者后缀的矩阵积，也可以用n*40³预处理，最后拿出初始向量依次乘上这log个矩阵，复杂度是n*40³+qlogn*40²。
• I：对于一个点x，相当于x的dfs序的那个位置，在[l,r]这个区间中+1，每个询问相当于x的子树的dfs序区间[l,r]的和，这是个裸的二维数点。
• J：O(l)预处理出组合数，然后m²dp容斥。

附加文件

• 1.png by chenjb