2016-C24-team2
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
||Run ID||Time||Size||Problem||Language||Result||
||378||4:59:16||2691||J||g++0x||OK||
||377||4:56:47||2685||J||g++0x||Wrong answer||
||358||2:17:07||1498||F||g++0x||OK||
||348||1:18:21||1602||A||g++0x||OK||
||343||0:22:48||356||D||gcc||OK||
||342||0:17:47||268||D||gcc||Wrong answer||
== 流水账 ==
=== TsReaper ===
开始的时候starve学长有课，我和hzf学长先开始。hzf学长很快发现D的做法，我写的时候又忘记了一个特例WA了一次，'''D2y22'''。学长接下来又想到了A的做法，我们用二位偏序改进了一下'''A1y78'''。我写A的时候hzf学长又想到了F的做法，因为我没怎么写过维护凸壳+dp所以敲了一个暴力对拍~~结果暴力写错了浪费了一点时间~~，'''F1y137'''。
然后starve学长来了，似乎想到了E的做法。hzf学长提出了一个反例~~然而这个反例并不符合题目限制，但是我们三个人都没有发现...~~，之后我们分别纠结了一段时间H和E。最后90分钟我看了一下J，想到了并查集的写法。但是因为程序比较难写，时间也比较紧，出现了并查集写错，函数忘记return等错误，好在最后答对了，'''J2y299'''。
== 总结 ==
=== TsReaper ===
* 做得好的地方
* A和F的想法都很不错...
* 做得不好的地方
* E题的反例举错了，我们还没有发现...
* J题出现了很多低级失误，最后时刻也要淡定啊...
== 题解 ==
D题比较简单，略过...
=== A - MEX-Query ===
把询问按右端点从小到大排序，用树状数组维护每种数在当前右端点的左边最后出现的位置。这样只需要求“最后出现的位置在左端点左边的数，最小是多少”，用树状数组维护前缀最小值即可。
我们也可以把这个问题转化为二位偏序。如果序列中有n个x，那么它们会把序列分成n+1个区间。如果有一个询问区间恰好完全被其中某个区间包含，则这个询问的答案至多是x。
也就是说，设这n+1个区间中的某个区间为[L,R]，询问区间为[l,r]。只要L<=l且-R<=-r，则该询问的答案至多是x。这就是一个二位偏序问题，只不过树状数组维护的是前缀最小值，而不是前缀和。
=== F - Just Another Sequence Problem ===
设f[i,j]表示以[i,j]区间为最后一个区间的答案，sum[]表示前缀和，显然有f[i,j] = max(f[k,i-1] + (sum[i-1]-sum[k-1]) * (sum[j]-sum[i-1]))，展开来就是f[i,j] = max(f[k,i-1] - sum[k-1]*(sum[j]-sum[i-1]) + sum[i-1]*(sum[j]-sum[i-1]))。这里面只有f[k,i-1] - sum[k-1]*(sum[j]-sum[i-1])这一部分与k有关。
我们可以把这个部分看成直线，f[k,i-1]是截距，-sum[k-1]是斜率。那么问题就变成了：有i-1条直线（一次函数），还有j-i+1个不同的x值，求对于每个x值的最大函数值。我们只需要维护一个下凸壳，再对于每个x二分一下即可。复杂度O(n^2^logn)
=== J - Dividing Area ===
我们把询问倒过来做，从连线变成擦线。一开始形成同一个三角形的三条有向线段属于一个集合，该集合的答案就是三角形面积的两倍。没有构成三角形的有向线段属于-1集合，答案是-1。接下来每擦掉一条线，两个集合就会合并，合并后集合的答案就是两个集合答案相加（当然如果合并前有一个集合是-1，那么合并后两个集合里的元素都属于-1）。~~是一道说着容易写起来麻烦的题目~~。
== 补题 ==| Run ID | Time | Size | Problem | Language | Result |
| 378 | 4:59:16 | 2691 | J | g++0x | OK |
| 377 | 4:56:47 | 2685 | J | g++0x | Wrong answer |
| 358 | 2:17:07 | 1498 | F | g++0x | OK |
| 348 | 1:18:21 | 1602 | A | g++0x | OK |
| 343 | 0:22:48 | 356 | D | gcc | OK |
| 342 | 0:17:47 | 268 | D | gcc | Wrong answer |
流水账
TsReaper
开始的时候starve学长有课，我和hzf学长先开始。hzf学长很快发现D的做法，我写的时候又忘记了一个特例WA了一次，D2y22。学长接下来又想到了A的做法，我们用二位偏序改进了一下A1y78。我写A的时候hzf学长又想到了F的做法，因为我没怎么写过维护凸壳+dp所以敲了一个暴力对拍结果暴力写错了浪费了一点时间，F1y137。
然后starve学长来了，似乎想到了E的做法。hzf学长提出了一个反例然而这个反例并不符合题目限制，但是我们三个人都没有发现...，之后我们分别纠结了一段时间H和E。最后90分钟我看了一下J，想到了并查集的写法。但是因为程序比较难写，时间也比较紧，出现了并查集写错，函数忘记return等错误，好在最后答对了，J2y299。
总结
TsReaper
- 做得好的地方
- A和F的想法都很不错...
- 做得不好的地方
- E题的反例举错了，我们还没有发现...
- J题出现了很多低级失误，最后时刻也要淡定啊...
题解
D题比较简单，略过...
A - MEX-Query
把询问按右端点从小到大排序，用树状数组维护每种数在当前右端点的左边最后出现的位置。这样只需要求“最后出现的位置在左端点左边的数，最小是多少”，用树状数组维护前缀最小值即可。
我们也可以把这个问题转化为二位偏序。如果序列中有n个x，那么它们会把序列分成n+1个区间。如果有一个询问区间恰好完全被其中某个区间包含，则这个询问的答案至多是x。
也就是说，设这n+1个区间中的某个区间为[L,R]，询问区间为[l,r]。只要L<=l且-R<=-r，则该询问的答案至多是x。这就是一个二位偏序问题，只不过树状数组维护的是前缀最小值，而不是前缀和。
F - Just Another Sequence Problem
设f[i,j]表示以[i,j]区间为最后一个区间的答案，sum[]表示前缀和，显然有f[i,j] = max(f[k,i-1] + (sum[i-1]-sum[k-1]) * (sum[j]-sum[i-1]))，展开来就是f[i,j] = max(f[k,i-1] - sum[k-1]*(sum[j]-sum[i-1]) + sum[i-1]*(sum[j]-sum[i-1]))。这里面只有f[k,i-1] - sum[k-1]*(sum[j]-sum[i-1])这一部分与k有关。
我们可以把这个部分看成直线，f[k,i-1]是截距，-sum[k-1]是斜率。那么问题就变成了：有i-1条直线（一次函数），还有j-i+1个不同的x值，求对于每个x值的最大函数值。我们只需要维护一个下凸壳，再对于每个x二分一下即可。复杂度O(n2logn)
J - Dividing Area
我们把询问倒过来做，从连线变成擦线。一开始形成同一个三角形的三条有向线段属于一个集合，该集合的答案就是三角形面积的两倍。没有构成三角形的有向线段属于-1集合，答案是-1。接下来每擦掉一条线，两个集合就会合并，合并后集合的答案就是两个集合答案相加（当然如果合并前有一个集合是-1，那么合并后两个集合里的元素都属于-1）。是一道说着容易写起来麻烦的题目。
补题
附加文件
- 2016-C24-team2.zip by TsReaper