poj 2991 Crane 线段树

缘起

日常浪费生命 poj 2991 Crane

分析

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
一台起重机，可视作是N条线段（起重臂）首尾相连, 第i条线段的长度是Li（1<=i<N）. 伊始, 所有线段笔直向上.
第一条线段在最下面, 第N条线段在最上面. 起重机的根部（即第一条线段的一个端点）坐标是(0,0)
有C条控制起重机的指令. 指令i给出两个整数S和A，效果是使得S和S+1的角度变成A（都是旋转上面的起重臂做到的）. 
所谓角度指的是从线段S开始沿逆时针方向旋转到S+1所经过的角度. 显然,伊始所有的角度都是180度
按顺序执行这C条指令. 在每条指令执行之后,输出起重机末端点（即第N条线段的一个端点）的坐标.

【输入】
多样例,每个样例包含n和c, 然后是n行，每行一个[1,100]的正整数表示第i条线段的长度. 然后是c行，每行
2个整数(s,a),表示指令
1<=n,c<=10000
1 ≤ s < n, 0 ≤ a ≤ 359

【输出】
对于每个样例，输出c行，每行2个浮点数（四舍五入小数点后2位）表示执行完指令之后起重机末端的坐标

【样例输入】
2 1
10 5
1 90

3 2
5 5 5
1 270
2 90

【样例输出】
5.00 10.00

-10.00 5.00
-5.00 10.00

【限制】
2s

此题是线段树的经典题目了. 有一点向量加法知识的童鞋都知——其实最后起重机的末端的坐标=（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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
//#include "stdafx.h"

#include <stdio.h>
#include <math.h>
#include <string.h>
//#define LOCAL

const double PI = atan(1.0)*4;
const int maxn = 10005;
int n,c,s;
double a ,x[maxn],y[maxn],alpha[maxn],endx, endy; // (x[i],y[i])是第i根线段的末端的相对第i-1根线段的末端的偏移的xy坐标

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int kase = 0;
	while(~scanf("%d%d", &n ,&c))
	{
		if (kase++)
		{
			puts("");
		}
		for (int i = 1; i<=n;i++)
		{
			scanf("%lf", y+i);
			x[i] = 0;
			alpha[i] = PI; //alpha[i]是第i根线段与第i-1根线段逆时针夹角
		}
		while(c--)
		{
			scanf("%d%lf", &s, &a); // 第s+1根和第s根的逆时针角度变成a度
			double beta = a/180*PI-alpha[s+1]; // 此次逆时针旋转的角度
			alpha[s+1] = a/180*PI; // 更新第s+1根线段和第s根线段的夹角
			for (int i = s+1; i<=n; i++) // 从s+1起,更新每根线段的末端相对它前一根线段末端的(x,y)坐标
			{
				double tx=x[i],ty=y[i];
				x[i] = tx*cos(beta)-ty*sin(beta);
				y[i] = ty*cos(beta)+tx*sin(beta);
			}
			endx = 0, endy = 0;
			for (int i = 1; i<=n;i++)
			{
				endx+=x[i];
				endy+=y[i];
			}
			printf("%.2lf %.2lf\n",endx, endy);
		}
	}
	return 0;
}

然后被无情的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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
//#include "stdafx.h"

#include <stdio.h>
#include <math.h>
#include <string.h>
//#define LOCAL

const double PI = atan(1.0)*4;
const int maxn = 10005;
int n,c,s;
double a ,x[maxn],y[maxn],alpha[maxn],endx, endy; // (x[i],y[i])是第i根线段的末端的相对第i-1根线段的末端的偏移的xy坐标

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int kase = 0;
	while(~scanf("%d%d", &n ,&c))
	{
		if (kase++)
		{
			puts("");
		}
		endx = 0, endy = 0;
		for (int i = 1; i<=n;i++)
		{
			scanf("%lf", y+i);
			x[i] = 0;
			endy+=y[i];
			alpha[i] = PI; //alpha[i]是第i根线段与第i-1根线段逆时针夹角
		}
		while(c--)
		{
			scanf("%d%lf", &s, &a); // 第s+1根和第s根的逆时针角度变成a度
			double beta = a/180*PI-alpha[s+1]; // 此次逆时针旋转的角度
			alpha[s+1] = a/180*PI; // 更新第s+1根线段和第s根线段的夹角
			for (int i = s+1; i<=n; i++) // 从s+1起,更新每根线段的末端相对它前一根线段末端的(x,y)坐标
			{
				double tx=x[i],ty=y[i];
				x[i] = tx*cos(beta)-ty*sin(beta);
				y[i] = ty*cos(beta)+tx*sin(beta);
				endx+=x[i]-tx;
				endy+=y[i]-ty;
			}
			printf("%.2lf %.2lf\n",endx, endy);
		}
	}
	return 0;
}

悲剧的是，还是被T掉了. 上面的代码耗时的部分就在while(c–)的内层里面还有一个循环 for (int i = s+1; i<=n; i++) 这个for循环太耗时了——如果s较小的话, 就将近O(n)代价更新一次. 所以要想过掉此题, 必须要想O(logn)的方法来更新一次 怎么做呢? 区间的问题使用线段树是一种高效的做法. 其次每个坐标分量的增量虽然不一样，但是角度是可以叠加的. 所以可以使用线段树的延迟更新(貌似线段树都需要使用延迟更新才能过)。 本题使用点线段树. 并且采用了延迟更新技巧（完全仿照【3】，线段树延迟更新的技巧说白了就是如果恰好就是入参区间的话，打上标记就返回，并不真正更新，否则的话，就要真正更新当前节点，而且是老账新账一起算.）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
//#include "stdafx.h"

#include <stdio.h>
#include <math.h>
#include <string.h>
//#define LOCAL

const double PI = atan(1.0)*4, eps = 1e-6;
const int maxn = 10005;
int n,c,s;
double a ,x[maxn],y[maxn],alpha[maxn],endx, endy;

struct SegNode
{
	int l, r; // [l,r]区间
	double sumx, sumy, alpha; // sumx是本区间上所有的x的和, sumy是本区间上所有的y的和, alpha是本区间上所有点都需要逆时针旋转的角度
}segTree[maxn<<2];

void build(int begin, int end, int cur) // 递归建树, segTree[cur]是当前节点
{
	segTree[cur].l = begin;
	segTree[cur].r = end;
	segTree[cur].alpha = 0;
	if (begin==end)
	{
		segTree[cur].sumx = 0;
		segTree[cur].sumy = y[begin];
		return;
	}
	int mid = (begin+end)>>1;
	build(begin, mid, cur<<1);
	build(mid+1, end, cur<<1|1);
	segTree[cur].sumx = 0;
	segTree[cur].sumy = segTree[cur<<1].sumy+segTree[cur<<1|1].sumy;
}

double getsumx(int begin, int end, int cur, double alpha) // 算x坐标的部分和, cur是当前节点, alpha是当前节点累计的旋转角度
{
	double t = alpha+segTree[cur].alpha;
	if (begin==segTree[cur].l && end ==segTree[cur].r)
	{
		return segTree[cur].sumx*cos(t) - segTree[cur].sumy*sin(t); // 注意, 要把延迟加载的部分也算上
	}
	int mid = (segTree[cur].l+segTree[cur].r)>>1;
	if (end<=mid)
	{
		return getsumx(begin, end, cur<<1, t);
	}
	else if (begin>mid)
	{
		return getsumx(begin, end, cur<<1|1,t);
	}
	else
	{
		return getsumx(begin, mid, cur<<1,t)+getsumx(mid+1, end, cur<<1|1, t);
	}
}

double getsumy(int begin, int end, int cur,double alpha) // 算y坐标的部分和, cur是当前节点
{
	double t = alpha+segTree[cur].alpha;
	if (begin==segTree[cur].l && end ==segTree[cur].r)
	{
		return segTree[cur].sumy*cos(t)+segTree[cur].sumx*sin(t); // 注意, 要把延迟加载的部分也算上
	}
	int mid = (segTree[cur].l+segTree[cur].r)>>1;
	if (end<=mid)
	{
		return getsumy(begin, end, cur<<1,t);
	}
	else if (begin>mid)
	{
		return getsumy(begin, end, cur<<1|1,t);
	}
	else
	{
		return getsumy(begin, mid, cur<<1,t)+getsumy(mid+1, end, cur<<1|1,t);
	}
}

void pushdown(int begin, int end, int cur,double beta)
{
	double tx = segTree[cur].sumx, ty = segTree[cur].sumy;
	segTree[cur].sumx = tx*cos(segTree[cur].alpha)-ty*sin(segTree[cur].alpha);
	segTree[cur].sumy = ty*cos(segTree[cur].alpha)+tx*sin(segTree[cur].alpha); // 这两行是老账——迟来的旋转
	double dx = getsumx(begin, end, cur,0); // 在不改变子节点的alpha属性的前提下求sumx和sumy(所以子节点的alpha属性要放到本代码的后面去改变)
	double dy = getsumy(begin, end, cur,0); // 原先 [begin, end]的部分和
	segTree[cur].sumx += (dx*cos(beta)-dy*sin(beta)-dx);
	segTree[cur].sumy += (dx*sin(beta)+dy*cos(beta)-dy);  // 此次旋转beta之后的增量, 这是新账
	segTree[cur<<1].alpha+=segTree[cur].alpha;
	segTree[cur<<1|1].alpha+=segTree[cur].alpha; // 下推父节点cur的延迟标记到两个子节点
	segTree[cur].alpha = 0; // 账算清楚了, 没有延迟的了
}

void updata(int begin, int end, double beta, int cur) // [begin,end]上旋转角度beta,延迟更新线段树, cur是当前节点
{
	if (segTree[cur].l == begin && segTree[cur].r == end)
	{
		segTree[cur].alpha+=beta; // 如果区间刚好重合的话, 就仅仅更新一下区间的角度就返回,而不做实质性的更新(延迟更新)
		return;
	}
	pushdown(begin, end, cur,beta); // 如果不能延迟更新的话, 就要下推延迟标记,而且本节点就要更新了(因为不能延迟更新, cur节点自然要真实更新咯~)
	int mid = (segTree[cur].l+segTree[cur].r)>>1;
	if (end<=mid)
	{
		updata(begin,end, beta, cur<<1);
	}
	else if (begin>mid)
	{
		updata(begin, end, beta, cur<<1|1);
	}
	else
	{
		updata(begin, mid, beta, cur<<1);
		updata(mid+1, end, beta, cur<<1|1);
	}
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int kase = 0;
	while(~scanf("%d%d", &n ,&c))
	{
		if (kase++)
		{
			puts("");
		}
		for (int i = 1; i<=n;i++)
		{
			scanf("%lf", y+i);
			x[i] = 0;
			alpha[i] = PI;
		}
		build(1, n,1); // 建树
		while(c--)
		{
			scanf("%d%lf", &s, &a);
			double beta = a/180*PI-alpha[s+1]; // [s+1,...,n]都要旋转的角度
			alpha[s+1] = a/180*PI;  // 更新当前角度
			updata(s+1, n, beta,1);
			printf("%.2lf %.2lf\n",segTree[1].sumx, segTree[1].sumy);
		}
	}
	return 0;
}

很不幸~ 还是被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
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
//#include "stdafx.h"

#include <stdio.h>
#include <math.h>
#include <string.h>
//#define LOCAL

const double PI = atan(1.0)*4, eps = 1e-6;
const int maxn = 10005;
int n,c,s;
double a ,x[maxn],y[maxn],alpha[maxn],endx, endy;

struct SegNode
{
	int l, r; // [l,r]区间
	double sumx, sumy, alpha; // sumx是本区间上所有的x的和, sumy是本区间上所有的y的和, alpha是本区间上所有点都需要逆时针旋转的角度
}segTree[maxn<<2];

void build(int begin, int end, int cur) // 递归建树, segTree[cur]是当前节点
{
	segTree[cur].l = begin;
	segTree[cur].r = end;
	segTree[cur].alpha = 0;
	if (begin==end)
	{
		segTree[cur].sumx = 0;
		segTree[cur].sumy = y[begin];
		return;
	}
	int mid = (begin+end)>>1;
	build(begin, mid, cur<<1);
	build(mid+1, end, cur<<1|1);
	segTree[cur].sumx = 0;
	segTree[cur].sumy = segTree[cur<<1].sumy+segTree[cur<<1|1].sumy;
}

void pushdown(int begin, int end, int cur,double beta)
{
	segTree[cur<<1].alpha+=segTree[cur].alpha;
	segTree[cur<<1|1].alpha+=segTree[cur].alpha; // 下推父节点cur的延迟标记到两个子节点
	segTree[cur].alpha = 0; // 账算清楚了, 没有延迟的了
}

struct Complex
{
	double x,y;
	Complex(double x, double y):x(x),y(y){}
	Complex(){}
	Complex operator+(const Complex &o)
	{
		return Complex(x+o.x, y+o.y);
	}
};

Complex updata(int begin, int end, double beta, int cur) // [begin,end]上逆时针旋转角度beta,延迟更新线段树, cur是当前节点
{
	Complex ans;
	if (segTree[cur].l == begin && segTree[cur].r == end)
	{
		double ta = segTree[cur].alpha;
		segTree[cur].alpha+=beta; // 如果区间刚好重合的话, 就仅仅更新一下区间的角度就返回,而不做实质性的更新(延迟更新)
		double deltax = segTree[cur].sumx*cos(segTree[cur].alpha)-segTree[cur].sumy*sin(segTree[cur].alpha) - (segTree[cur].sumx*cos(ta)-segTree[cur].sumy*sin(ta));
		double deltay = segTree[cur].sumx*sin(segTree[cur].alpha)+segTree[cur].sumy*cos(segTree[cur].alpha) - (segTree[cur].sumx*sin(ta)+segTree[cur].sumy*cos(ta));
		return Complex(deltax, deltay); // 要返回到父节点去的,给父节点算新账用的增量
	}
	double tx = segTree[cur].sumx, ty = segTree[cur].sumy;
	segTree[cur].sumx = tx*cos(segTree[cur].alpha)-ty*sin(segTree[cur].alpha);
	segTree[cur].sumy = tx*sin(segTree[cur].alpha)+ty*cos(segTree[cur].alpha); // 这是老账
	pushdown(begin, end, cur,beta); // 如果不能延迟更新的话, 就要下推延迟标记,而且本节点就要更新了(因为不能延迟更新, cur节点自然要真实更新咯~)
	int mid = (segTree[cur].l+segTree[cur].r)>>1;
	if (end<=mid)
	{
		ans = updata(begin,end, beta, cur<<1);
	}
	else if (begin>mid)
	{
		ans = updata(begin, end, beta, cur<<1|1);
	}
	else
	{
		ans = updata(begin, mid, beta, cur<<1) + updata(mid+1, end, beta, cur<<1|1);
	}
	segTree[cur].sumx += ans.x; // 通过递归把新账算好,而不是太直接(通过getsumx(y))的去算新账
	segTree[cur].sumy += ans.y;
	return ans;
}

int main()
{
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	freopen("d:\\my.out", "w", stdout);
#endif
	int kase = 0;
	while(~scanf("%d%d", &n ,&c))
	{
		if (kase++)
		{
			puts("");
		}
		for (int i = 1; i<=n;i++)
		{
			scanf("%lf", y+i);
			x[i] = 0;
			alpha[i] = PI;
		}
		build(1, n,1); // 建树
		while(c--)
		{
			scanf("%d%lf", &s, &a);
			double beta = a/180*PI-alpha[s+1]; // [s+1,...,n]都要旋转的角度
			alpha[s+1] = a/180*PI;  // 更新当前角度
			updata(s+1, n, beta,1);
			printf("%.2lf %.2lf\n",segTree[1].sumx, segTree[1].sumy);
		}
	}
	return 0;
}

重点看上面的代码的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

通过此题. 我们了解到了线段树延迟更新的一般套路

  1. 如果遇到刚刚好的区间, 则直接更新延迟标记并返回.
  2. 如果不是刚刚好的区间的话, 就不能延迟更新了，而要立即更新. 即新账老账一起算. 老账是好算的. 新账如果能像【3】那样好算, 就立即算出来. 如果不好算的话, 则就像本题一样融入到递归中来算（这样比直接暴力算——getsumx、getsumy快）.

参考

【1】https://contest.felk.cvut.cz/05prg/solved/c.in

【2】https://contest.felk.cvut.cz/05prg/solved/c.out

【3】https://yfsyfs.github.io/2019/07/13/%E7%BA%BF%E6%AE%B5%E6%A0%91-fzu-2171-%E9%98%B2%E5%AE%88%E9%98%B5%E5%9C%B0-II/