POJ 2991 Crane - simezi

大体理解した。
完全にソラで書けるように何回か復習すべきである。

問題

N個の線分が接続されたクレーンがある。
それぞれの線分の長さはL[i]で与えられる。

はじめは全ての線分がまっすぐ上を向いて接続されている。

ここにC個の命令がくる。命令iは二つの整数Si,Aiにより与えられ、
線分Siと線分Si+1の間の角度をAiにせよという意味である。

このとき、各命令の後で、クレーンの先端がどこにあるかを出力せよ。

制約条件

N≦10000

方針

蟻本p157〜の解説の通り。
Segment Treeを使う。

ノードは連続する線分の集合に対応し、各情報を持つ。

対応する線分を最初の線分を垂直にしてつなげた際の、最初の端点から最後の端点へのベクトル
子ノードをもつとき、二つの子ノードの対応する部分をつなげる際に右の子ノードを回転させる角度

Segment Treeの更新は次のように行う
changeという関数を、
change(int s,double a,int v,int l,int r)として、
s≦lのときは何もしない。
s＜rのとき（線分が折れ曲がる箇所が区間の内側に入っている）、
左右の子ノードについてchangeを呼び出し再帰的に更新。
その後、sが中間より左ならang[v]にaを足す。
最後にlからrへのベクトルを更新する。

ソースコード

写経なので略。