ByteDance - Moscow Workshops ICPC Programming Camp 2019. Day 4, Div A.

ABCDEFGHIJK

复盘人：rxd

开场看了看题，发现K是个裸Treap，写之。

0h17min，K +0。

然后gt告诉我A是个裸LCT，写之。

0h37min，A +0。

然后gt告诉我E的题意，是个大模拟，我们讨论了下。此时没有别的题可以写，于是我开始写E。叶队在想I。

写到一半我发现有点难写，决定先咕了，gt和叶队告诉我C的大概做法，大概是个三维数点。我开始写C的暴力。

写完暴力gt上机重写E，我思考了下F，叶队想出了I并表示还有点小问题。

我上机把C的暴力改成扫描线树套树，先写了个扫描线，过不了样例，打印眼调。

gt继续写E、叶队写I。

我改了若干次C仍然过不了样例。

3h22min，叶队交了2发I，WA。打印眼调。

我和gt讨论了下会了G。

大概4h的时候，我C过了样例，交上去WA。叶队上机拍I。我和gt眼调C。

经历了抄板子、改了若干个错误，C交了3发还是WA。

最后10min叶队发现了I的错误。

4h58min，I +2。

A：LCT。

B：

C：讨论回文中点在[L,Mid]还是[Mid+1,R]，然后就是个二维数点了。

D：

E：欧洲杯，首先最多4对球队打了2场，2^4枚举哪场是小组赛哪场是淘汰赛，然后根据度为3的球队来确定分组关系，再模拟下就行了。写出了若干小错误，但最关键的是题意里淘汰赛的赛制看错了。WA了6发。

F：

G(by yjn)：Sol(1): segmentree of time + LCT. Cover-tag does not work, since it's unrevertable. But insteadly, we can use a tag record how many times had this interval been coverd, and the remaining edges are those coverd by 0 times. This kind of tag can easily be reverted. $O(T\log T \log n )$.

      Sol(2): LCT for maximum spanning tree of the expired time of edges. Thus the deleted edge would non-tree-edges, or uncoverd tree-edges. $O(T\log n)$.

      upd by rxd: 补题写的是Sol2，好多地方把q写成n了，调了好久。总用时~1h，+0。

H:(by fz)对每个点$i$直接询问到根路径上$b_j \geq b_i$的所有$j$,它们$a_j$的中位数.直接树套树上,题解用的是树状数组套平衡树3个log.线段树套线段树会MLE,用bit套线段树就行了.

I(by yjn)：Transform the problem, i.e. find a plane(3d) passing the origin, maximum the number of points on one side(strictly). No 2 points collinear with the origin, no 3 points coplane with the origin.

      Sol(1): Like fhq problem ctsc 2017. Time complexity?

      Sol(2): Iterate points A,B. Check plane OAB for answer. O(n^3).

                  To make it faster, iterate A. Rotating the plane crossing the line OA around OA. Fix the axis OA, project other points to the plane perpendicular to OA, sort them by polar angle. Iterate B in this order, and simply calculate the answer.

      Note: when doing coordinate system transformation, do use inner production for each axis. Don't do one inner-production, then substract the component and calculate the length, cause you don't know the direction(positive or negative), for which I had 2 WAs,

J：

K：Treap。