2019-Sp039-lyk
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(1.png,700px)]]
[[Image(2.png,700px)]]
[wiki:2019-team2 返回Runespoor]
[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=001509 contest]
== 流水账 ==
== 总结 ==
'''zqq: ''' 今天开场就十分难受。我的F题把n和m读反了，然后RE，调了半个多小时。'''还好中途放下了去想别的题'''
A题写错了一个地方，但是对拍的时候暴力写错了3次，所以搞了一个小时。对于启发式合并还是太不熟练了。我写A的时候lyk好像一直再想H，可惜我没有时间和他讨论，圆方树的细节他又不是很清楚
B题本来是非常简单的，开始没有仔细想就觉得是三维数点。直到后来发现矩形面积求并cdq做不了，才发现有很简单的一个logn的做法。
幸运的是，D题几天前见过非常类似的，知道结论。最后1个半小时过了4题，勉强赶上了一些。
'''但是，总体来说，今天我们状态挺糟糕的。H和J题都各需要一个小时多才能搞出来。我们前面犯的错误太多了。'''
'''E是一个很经典的十字链表，但是我们完全想歪了。这道题一定要补一下。最好再去做几道类似的题'''
== 题解 ==
[wiki:2017-Sp160-team2 legilimens]
A : 树上最长上升子序列。维护以当前子树根结尾的最长上升/下降子序列DP数组：长度为i的最小结尾。每加入一个元素只会更新一次。然后利用长链剖分的性质合并，O(nlogn),查找二分
B ：求一些以原点为左下角的长方体的体积并。按x排序，从大到小加入。我们需要维护一个y,z平面上的轮廓：y递增，z递减。每次二分查询当前（0,0）- (y,z)的矩形已经被覆盖的面积。用set维护
E (from jsb)
题意：有一个 N∗N(N≤1000) 的方形矩阵。有 Q(Q≤2000) 个操作，每次给出一个正方形，要求把里面的值逆时针旋转90°。输出最后矩阵的样子。
题解：此题算是今年ZOJ新手上路某题的弱化版>_<。
为了方便，可以在正方形矩阵外面再加一圈点；值得注意的是，我们维护的是边（一个点 (x,y) 连出去的四条边）。
每一条边上都会有一个旋转标记 rev（注意，这是永久标记！！！）。当我们要去find一个固定位置的点时，我们从任意某个不变的起点出发（即外围的某个点），每经过一条边，都把当前累计的Sumrev并上该边的rev。每次我们想向上下左右一个方向d走的时候，d要经过Sumrev的调整。我们需要的做到的是，对于每一个操作，都实时维护一些边，使得从不变起点沿任意一条路径，都能确实地“定位”一个点 (x,y) 的id。
对于一次旋转操作，我们暴力找到目前正方形四周的那些点S以及它们外围一圈的点T（顺便得到了它们的Sumrev)，并先根据旋转90°将它们放到新的位置上。现在的问题是：里面的点本质是没有转的，所以每当我们从T跨越到S时，要求 Sumrev 发生一些变化，接着在这个矩阵里走的话就能重定向成实际的方向。
然后，为了保证结构正确，对于所有S->T和T->S的边，我们要重构它们的 rev ；即计算出它应该打什么标记，使得从 i 走到 j 时，Sumrevi 会变成 Sumrevk 。
F ：离散化后线段树每个点要维护成其表示区间的长度。加入它加一、减一来维护
== 补题 ==
* E: [lyk] 学了一下十字链表。它的关键在于：1.标记在边上 2.从(0,0)经过任意路径，走到某个点时，通过累加边上的标记后的状态（方向旋转标记或是加减/乘除标记）总是相同的。加减与乘除不能同时出现，因为标记不满足交换率。
* H: []
* J: []
流水账
总结
zqq: 今天开场就十分难受。我的F题把n和m读反了，然后RE，调了半个多小时。还好中途放下了去想别的题
A题写错了一个地方，但是对拍的时候暴力写错了3次，所以搞了一个小时。对于启发式合并还是太不熟练了。我写A的时候lyk好像一直再想H，可惜我没有时间和他讨论，圆方树的细节他又不是很清楚
B题本来是非常简单的，开始没有仔细想就觉得是三维数点。直到后来发现矩形面积求并cdq做不了，才发现有很简单的一个logn的做法。
幸运的是，D题几天前见过非常类似的，知道结论。最后1个半小时过了4题，勉强赶上了一些。
但是，总体来说，今天我们状态挺糟糕的。H和J题都各需要一个小时多才能搞出来。我们前面犯的错误太多了。
E是一个很经典的十字链表，但是我们完全想歪了。这道题一定要补一下。最好再去做几道类似的题
题解
A : 树上最长上升子序列。维护以当前子树根结尾的最长上升/下降子序列DP数组：长度为i的最小结尾。每加入一个元素只会更新一次。然后利用长链剖分的性质合并，O(nlogn),查找二分
B ：求一些以原点为左下角的长方体的体积并。按x排序，从大到小加入。我们需要维护一个y,z平面上的轮廓：y递增，z递减。每次二分查询当前（0,0）- (y,z)的矩形已经被覆盖的面积。用set维护
E (from jsb)
题意：有一个 N∗N(N≤1000) 的方形矩阵。有 Q(Q≤2000) 个操作，每次给出一个正方形，要求把里面的值逆时针旋转90°。输出最后矩阵的样子。
题解：此题算是今年ZOJ新手上路某题的弱化版>_<。
为了方便，可以在正方形矩阵外面再加一圈点；值得注意的是，我们维护的是边（一个点 (x,y) 连出去的四条边）。
每一条边上都会有一个旋转标记 rev（注意，这是永久标记！！！）。当我们要去find一个固定位置的点时，我们从任意某个不变的起点出发（即外围的某个点），每经过一条边，都把当前累计的Sumrev并上该边的rev。每次我们想向上下左右一个方向d走的时候，d要经过Sumrev的调整。我们需要的做到的是，对于每一个操作，都实时维护一些边，使得从不变起点沿任意一条路径，都能确实地“定位”一个点 (x,y) 的id。
对于一次旋转操作，我们暴力找到目前正方形四周的那些点S以及它们外围一圈的点T（顺便得到了它们的Sumrev)，并先根据旋转90°将它们放到新的位置上。现在的问题是：里面的点本质是没有转的，所以每当我们从T跨越到S时，要求 Sumrev 发生一些变化，接着在这个矩阵里走的话就能重定向成实际的方向。
然后，为了保证结构正确，对于所有S->T和T->S的边，我们要重构它们的 rev ；即计算出它应该打什么标记，使得从 i 走到 j 时，Sumrevi 会变成 Sumrevk 。
F ：离散化后线段树每个点要维护成其表示区间的长度。加入它加一、减一来维护
补题
- E: [lyk] 学了一下十字链表。它的关键在于：1.标记在边上 2.从(0,0)经过任意路径，走到某个点时，通过累加边上的标记后的状态（方向旋转标记或是加减/乘除标记）总是相同的。加减与乘除不能同时出现，因为标记不满足交换率。
- H: []
- J: []