Petrozavodsk Summer-2017. JOI TST 2012 Selection.

复盘人：rxd

开场我看了F，想了下感觉是傻逼题，于是直接开写。
叶队和gt表示A是之前做过的，B有点像洲阁出过的一个题。

0h18min：F(+0)，一血。

然后gt上去写A了。写之前交代给我说C是傻逼题，我看了感觉确实是傻逼题。
叶队给我讲了下G，我想了想感觉不太会。
我看了H，是个推箱子，跟叶队讨论了下感觉做是能做的，好像要搞个割点，决定先放着。
我看了J，是个傻逼题。看完gt刚好过A，就给他讲了下J确认了下。

0h43min：A(+0)。

然后我上机写C。gt和叶队讨论出了I，又在讨论E。过了C之后我先写了一点点J，然后感觉要有点久，就让gt先写I，这里我好像划了一会儿。

0h57min：C(+0)。
1h34min：I(+0)。

之后我写了好久J，不过200排一发了还是有点爽。其间gt秒了G并和叶队确认了下。叶队搞出了H的简单做法。

2h08min：J(+0)。
2h15min：G(+0)。

我想了个E的做法，感觉好像很对就上去写了。写了80%发现好像是错的，凄凉下机，gt上去写H。我和叶队讨论出了B，我想了下细节。
gt被这个H胖住了，一直过不了样例，大概3h27min的时候决定先下机调，我写B。
我写完有点细节问题搞错了WA了2发才过。gt也差不多同时过了H。

3h56min：H(+0)。
3h59min：B(+2)。

最后继续想E，突然灵光一闪会了，但是感觉写起来很麻烦。后来感觉只要在原先代码上改一点就行了。改完一发过了样例，调了个小错误交上去过了。

4h32min：E(+0)。

最后半个小时叶队会了D，就让他单刷了，我和gt挂机了。最后WA了。
然后就虐场了。

A：

B：枚举最大值，然后变成若干个三维前缀矩形求并的体积。枚举第一维，相当于加一个二维矩形、询问面积并，任意时刻一定是一个折线状物，拿个set维护下就行了。

C：直接枚举所有情况，只有一个分支要算下去，每层的和是\(O(n)\)的。总复杂度\(O(n \log n)\)。

D(by yjn)：自己的树相交的话可以调整。考虑Tutte's Thm的那种setting，凭直觉只要判断凸包上的点。于是求出凸包分类罗干一下即可。比赛时漏看了一个“每种点至少要有一个”的条件wa了。如果有三点共线可能还真不知道怎么做。

感觉这个题还是比较妙的。赛后仔细证了一下。首先Tutte是一个必要条件。然后对多边形三角剖分，每次在黑白交界的地方切出一个三角形。证明递降到三角形的情况。设底边是黑白，顶点是黑。底边左边的点顺时针扫一条射线卡住第一个白点，底边右边的点逆时针扫一条射线卡住第一个白点。然后对这两个白点的连线作为基准轴，拿出轴上方所有白点的上凸壳。对于两条扫描线略过的点以及白点上凸壳以上的黑点，全部向顶点连边。因为凸性，剩下的点相互连边不会影响到已连的边。由于拿出了白点的一个凸壳，删掉黑色顶点，证明递降到一个点数更少的多边形。

E：考虑用十字链表维护格子之间的相对关系，这样每次只要修改\(O(n)\)个点。问题是旋转之后怎么处理朝向。注意到如果已知A往下走到了B，那么根据B的4个方向里哪个是A就可以得出B哪个方向是朝上的。那么直接模拟就行了。\(O(nq)\)。

upd by yjn:

多个log还有个（可能）比较好写的做法。对每个行和列开一个treap。每次旋转的时候暴力把所有相关的行和列的treap裂开，然后行treap拼到列treap里，列treap拼到行treap里。

F：离散+扫描线+线段树。

G：

H：

I：

J：加入一个点就把包含它的区间拿出来处理掉，这个用两个线段树就行。处理就是再用两个线段树区间赋max、询问全局最大值。然后注意到离散之后同一段只会被做两次，第二次就只有答案的贡献了。所以直接离散后暴力就行了。\(O(n \log n)\)。

总结 (by rxd)：

回顾今天比赛经过发现是严格我写一个gt写一个的。感觉这样节奏还挺好的，之前有的时候我连续上机，然后就会放弃思考，想题的陷入僵局的时候也会萎住。轮流换着想题、写题容易让大家都保持着状态。（叶队委屈一下，就想题多一点吧）