缘起
日常浪费生命 poj 2991 Crane
分析
1 | 一台起重机,可视作是N条线段(起重臂)首尾相连, 第i条线段的长度是Li(1<=i<N). 伊始, 所有线段笔直向上. |
此题是线段树的经典题目了. 有一点向量加法知识的童鞋都知——其实最后起重机的末端的坐标=(0, L1)+(第二根线段的末端相对第一根线段的末端的x坐标, 第二根线段的末端相对第一根线段的末端的y坐标)+…+(第N根线段的末端相对第n-1根线段的末端的x坐标, 第N根线段的末端相对第n-1根线段的末端的y坐标)
其中(x,y)坐标系使用的是题目中(0,0)对应的坐标系. 所以需要维护每根线段相对(x,y)坐标系的x轴旋转的角度. 一开始都是90度. 如果S+1相对S逆时针旋转了alpha角度的话, 则从S+1根开始往后所有的线段相对x轴都逆时针旋转了alpha角度. 而如果一根线段的末端相对它前一根线段的末端在(x,y)坐标系下的坐标是(x,y)的话, 则假设变成了(x1,y1), 则有

$$
\begin{cases}
cosx = x/l, sinx = y/l \
cos(x+alpha) = x1/l, sin(x+alpha) = y1/l
\end{cases}
$$
其中l是第S+1根的长度. 利用上述方程组是不难解出(其实(x+iy)*e^(i*alpha)就知道了)
$$
x1=xcos(alpha)-ysin(alpha) \
y1 = ycos(alpha)+xsin(alpha)
$$
所以一旦更新S+1和S之间的逆时针角度的话,则从S+1开始,一直到n,这n-S根线段的端点在(x,y)坐标系中的坐标都要更新. 而我们要求的起重机最末端的坐标其实就是这些x们的和以及y们的和. 如果更新完毕之后,再遍历n求和的话. 可以给出如下代码
1 | //#include "stdafx.h" |
然后被无情的T掉了 (测试数据见 【1】和【2】)
Status | Time Limit Exceeded |
---|---|
Length | 1074 |
Lang | C++ |
Submitted | 2019-09-03 11:11:04 |
Shared | |
RemoteRunId | 20827796 |
但是使用测试数据进行校验, 答案是正确无误的. 所以仅仅是因为算法性能不够(而不是算法错误或者陷入死循环导致T)
那么, 上述算法哪里浪费了时间呢? 显然,你每次更新 [s+1,n]区间上的数据的时候, 你都更新完毕之后使用for循环求和endx和endy. 等于说回答一次询问的复杂度是O(n).而共有c次询问. 所以一个用例的复杂度是O(NC)的——破亿了~ 所以肯定被T掉. 后来注意到,我根本没必要更新s+1之前的呀~ 我完全只需要记录s+1以后的增量即可. 于是优化了一版
1 | //#include "stdafx.h" |
悲剧的是,还是被T掉了. 上面的代码耗时的部分就在while(c–)的内层里面还有一个循环 for (int i = s+1; i<=n; i++) 这个for循环太耗时了——如果s较小的话, 就将近O(n)代价更新一次. 所以要想过掉此题, 必须要想O(logn)的方法来更新一次 怎么做呢? 区间的问题使用线段树是一种高效的做法. 其次每个坐标分量的增量虽然不一样,但是角度是可以叠加的. 所以可以使用线段树的延迟更新(貌似线段树都需要使用延迟更新才能过)。 本题使用点线段树. 并且采用了延迟更新技巧(完全仿照【3】,线段树延迟更新的技巧说白了就是如果恰好就是入参区间的话,打上标记就返回,并不真正更新,否则的话,就要真正更新当前节点,而且是老账新账一起算.)
1 | //#include "stdafx.h" |
很不幸~ 还是被T掉了(我明显感觉比之前暴力快, 就差那么一点就可以A掉了)
Status | Time Limit Exceeded |
---|---|
Length | 3734 |
Lang | C++ |
Submitted | 2019-09-03 20:48:01 |
Shared | |
RemoteRunId | 20829712 |
那么上面浪费时间的地方在哪里呢? 在pushdown方法中的getsumx(y) 调用. 它虽然O(logn)但是还是比较耗时,而且多多少少给人一种冗余的赶脚.
那么getsumx和getsumy分别是干什么的呢? 是用于算新账用的, 但是新账一定要再次递归求解吗?(这将导致算法的复杂度变成O(logn*logn)) 不需要, 上面线段树算法算新账的时候太急了~ 完全可以把算新账融入到递归中去. 就像下面这个样子(所以getsumx和getsumy就不需要了)
1 | //#include "stdafx.h" |
重点看上面的代码的updata的83、84行. 在那里把新账通过递归算好了. 这样将复杂度真正的降低到了O(logn)
Status | Accepted |
---|---|
Time | 875ms |
Memory | 1408kB |
Length | 4603 |
Lang | C++ |
Submitted | 2019-09-03 22:10:00 |
Shared | |
RemoteRunId | 20830177 |
通过此题. 我们了解到了线段树延迟更新的一般套路
- 如果遇到刚刚好的区间, 则直接更新延迟标记并返回.
- 如果不是刚刚好的区间的话, 就不能延迟更新了,而要立即更新. 即新账老账一起算. 老账是好算的. 新账如果能像【3】那样好算, 就立即算出来. 如果不好算的话, 则就像本题一样融入到递归中来算(这样比直接暴力算——getsumx、getsumy快).
参考
【1】https://contest.felk.cvut.cz/05prg/solved/c.in
【2】https://contest.felk.cvut.cz/05prg/solved/c.out
v1.5.2