挑战程序竞赛系列（33）：POJ 2991 Crane
挑战程序竞赛系列（33）：POJ 2991 Crane
版权声明：本文为博主原创文章，未经博主允许不得转载。 https://cloud.tencent.com/developer/article/1434661
挑战程序竞赛系列（33）：POJ 2991 Crane*
详细代码可以fork下Github上leetcode项目，不定期更新。
练习题如下：
POJ 2991: Crane
一道线段树题，在《挑战》中刷到了，就和之前理解的线段树拿来对比下，关于线段树可以参看【算法细节系列（28）：线段树】。
先来分析下题目，对于每个线段的更新，我们的目的在于记录终点的位置，此题的一个trick在于能否想到更新中的相对不变量【向量】，何以理解？
首先，旋转位置s，那么必然终点的位置会发生变化，所带来的结果是s后续的每个顶点都会发生相对变化，而s之间的顶点则没有改变。这种更新模式就特别符合线段树的性质了，因为线段树的提出就是基于对更新的优化，使得它在O(logn)O(\log n)的时间复杂度内完成。当然最幼稚的做法是，从s->终点，每旋转一次更新后续所有坐标。
这种模拟的做法必然会超时。那么问题来了，如何让这些更新规则去符合线段树的构造规则呢？
就拿上述方案来说，如果每个顶点维护一个坐标变量，那么就无法用区间来表示，因为每个顶点相互独立，它们的信息无法共享，所以区间合并所带来的问题是并不知道选谁作为该区间的代表。理论上来说，是终点坐标，可是却无法从几个孩子结点得到终点坐标的信息，得换换思路了。
向量，每个区间l,r维护一个起点指向终点r的向量，这和题目有关，因为我们只需要维护终点信息，而无需关注其它顶点的位置，那么我们就把问题抽象成了区间，每个区间维护一个向量，由此，区间与区间就能根据向量来合并了，合并规则为：当前向量加上右区间向量和所需旋转的角度。
这样一来，根结点必然永远都是从起点指向终点的向量，也就是答案x和y。
具体更新规则为：
x′=xchl+(cos(α)⋅xchr−sin(α)⋅ychr)
x' = x_{chl} + (\cos (\alpha) \cdot x_{chr} - \sin(\alpha) \cdot y_{chr})
y′=ychl+(sin(α)⋅xchr+cos(α)⋅ychr)
y' = y_{chl} + (\sin (\alpha) \cdot x_{chr} + \cos(\alpha) \cdot y_{chr})
代码如下：
import java.util.Scanner;
public class Main{
static class SegementTree{
int size;
double[] vx;
double[] vy;
double[] angle;
public SegementTree(int n){
this.size = (1 << n) - 1;
vx = new double[size];
vy = new double[size];
angle = new double[size];
}
public void init(int s, int l, int r){ //对应的区间为[l,r)
angle[s] = vx[s] = 0;
//叶子结点 和非叶子结点
if (r - l == 1){
vy[s] = len[l]; //表示区间叶子结点与下一段的向量
}
else{
int chl = s * 2 + 1;
int chr = s * 2 + 2;
init(chl, l, (l + r) / 2); //天然的划分所有区间
init(chr, (l + r) / 2, r);
vy[s] = vy[chl] + vy[chr]; //对于非叶子结点，vy表示合并后，终点向量距离原点的（x,y）
}
}
//从s开始，更新与s+1的角度，逆时针旋转角度a，当前线段树的结点为v，对应的区间为l和r
//由题意得，线段树中的每个左区间的向量需要变换，但右区间作为整体不需要做任何计算。
public void change(int s, double a, int v, int l, int r){
if (s <= l) return; // 如果需要旋转的s,对应当前的区间为右孩子，则不需要更新，因为它们隶属于一个整体
else if (s < r){
int chl = v * 2 + 1, chr = v * 2 + 2;
int m = (l + r) / 2;
//分治求解
change(s, a, chl, l, m);
change(s, a, chr, m, r);
//区间合并
if (s <= m) angle[v] += a; // 右儿子需要转动的角度,如果s 在右侧，则只需要更新当前状态ang[v]
double sin = Math.sin(angle[v]);
double cos = Math.cos(angle[v]);
vx[v] = vx[chl] + (cos * vx[chr] - sin * vy[chr]);
vy[v] = vy[chl] + (sin * vx[chr] + cos * vy[chr]);
}
}
}
static int[] len;
static double[] prv;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
while (in.hasNext()){
int n = in.nextInt();
int c = in.nextInt();
len = new int[n];
prv = new double[n];
for (int i = 0; i < n; ++i){
len[i] = in.nextInt();
prv[i] = Math.PI;
}
SegementTree tree = new SegementTree(15);
tree.init(0, 0, n);
for (int i = 0; i < c; ++i){
int s = in.nextInt();
int A = in.nextInt();
double a = A / 360.0 * 2 * Math.PI;
tree.change(s, a - prv[s], 0, 0, n);
prv[s] = a;
System.out.println(String.format("%.2f %.2f", tree.vx[0], tree.vy[0]));
}
}
in.close();
}
}