描述

有一台起重机，我们把起重机看成由N条线段依次首尾相接而成。第i条线段的长度为Li。最开始，所有的线段都笔直连接，指向上方。
有C条操纵起重机的指令。指令i给出两个整数Si和Ai，效果是使线段Si和Si+1之间的角度变成Ai度。其中角度指的是从线段Si开始延逆时针方向旋转到Si+1所经过的角度。最开始时所有角度都是180度。
按顺序执行这C条指令。在每条指令执行之后，输出起重机的前端（第N条线段的端点）的坐标。假设起重机的指点的坐标是（0,0）

解题报告

以（2,3,4,5,6,7,8,9）为例，建立的线段树如下所示：

每个节点维持存储：1）序号；2）权值；3）所管理的范围
更新时，维持下面两个值。
1）从第一条线段的起点指向最后一条线段的终点的向量(其为左右儿子节点对应坐标之和)
2）两个儿子节点对应的部分连接之后，右儿子需要转动的角度

向量(x,y)顺时针旋转B度，该向量变成：
x=xcos(B)+ysin(B)
y=ycos(B)-xsin(B)

代码

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

#define M_PI acos(-1.0)
#define N 10000
#define C 100000
#define ST_SIZE 1<<15

int n,c;
int L[N];//线段长度
int S[C],A[N];//指定要转的线段和角度
double vx[ST_SIZE],vy[ST_SIZE];//各节点的向量
double ang[ST_SIZE];//各节点的角度
double prv[N];//为了查询角度的变化而保存的当前角度的数组

void init(int k, int l, int r)//节点编号，左右区间下标
{
    ang[k]=vx[k]=0.0;
    if (r-l==1)//叶子节点
        vy[k]=L[l];//初始状态下都是竖直向上的
    else//非叶子节点
    {
        int chl=k*2+1, chr=k*2+2;
        init(chl,l,(l+r)/2);
        init(chr,(l+r)/2,r);
        vy[k]=vy[chl]+vy[chr];
    }
}

void change(int s,double a,int k,int l,int r)//将s和s+1的角度变为a,k是节点编号，lr是左右区间范围
{
    if (s<=l) return;
    else if (s<r)
    {
        int chl=k*2+1,chr=k*2+2;
        int m=(l+r)/2;//中点
        change(s,a,chl,l,m);
        change(s,a,chr,m,r);
        if (s<=m)
        {
            ang[k]+=a;
        }
        double si=sin(ang[k]),co=cos(ang[k]);
        vx[k]=vx[chl]+(co*vx[chr]-si*vy[chr]);
        vy[k]=vy[chl]+(si*vx[chr]+co*vy[chr]);
    }
}
void solve()
{
    init(0,0,n);
    for (int i=1; i<n; i++)
        prv[i]=M_PI;
    for (int i=0; i<c; i++)
    {
        scanf("%d%d",&S[i],&A[i]);
        int s=S[i];
        double a=A[i]/360.0*2*M_PI;//把角度转换成弧度
        change(s,a-prv[s],0,0,n);//a-prv[s]表示要转的角度减去当前的角度
        prv[s]=a;//更新当前的角度
        printf("%.2f %.2f\n", vx[0],vy[0]);
    }
}

int main()
{
    while(cin>>n>>c)//输入数量和查询次数
    {
        for (int i=0; i<n; i++)
            scanf("%d",&L[i]);//输入长度
        solve();
        cout<<endl;
    }
    return 0;
}