挑战程序设计竞赛的一道题

最近刚学了三角变换。于是就构造了个矩阵，没想到正是向量旋转的矩阵（不知道具体叫什么qwq

然后网上一半的题解是左闭右开的，另一部分是懒标记的。

于是便自己yy了一个左闭右闭的线段树，方法和挑战程序设计竞赛是一样的。当然代码不是一样的

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<iostream>

#include<cmath>

const double PI=3.1415926535897931;//M_Pi poj用不了

const int maxn=10101;

struct node

{

    double x;

    double y;

    double dir;//右儿子旋转的角度

};

node T[maxn<<2];

int L[maxn];

double pre[maxn];

void build(int R,int l,int r)

{

    T[R].dir=0;//多组数据，然后我就以为只有一组，遂wa了许多次

    T[R].x=0;

    T[R].y=0;

    if(l==r)

    {

        T[R].y=L[l];

        return ;

    }

    int mid=(l+r)>>1;

    build(R<<1,l,mid);

    build(R<<1|1,mid+1,r);

    T[R].x=T[R<<1].x+T[R<<1|1].x;

    T[R].y=T[R<<1].y+T[R<<1|1].y;

    return ;

}

void change(int R,int l,int r,int s,double D)

{

    if(s>r||s<l)  return ;//所修改的向量不在当前区间

    if(l==r)//正是一个点

    {    //直接修改

        double s=sin(D),c=cos(D),X=T[R].x,Y=T[R].y;

        T[R].x=c*X-s*Y;

        T[R].y=s*X+c*Y;

        //printf("%lf,%lf",T[R].x,T[R].y);

        return ;

    }

    int mid=(l+r)>>1,Ls=R<<1,Rs=R<<1|1;

    change(Ls,l,mid,s,D);

    change(Rs,mid+1,r,s,D);

    if(s<=mid)  T[R].dir+=D;//因为两端都是闭的，所以是大于等于号

    double S=sin(T[R].dir),C=cos(T[R].dir);

    T[R].x=T[Ls].x+(C*T[Rs].x-S*T[Rs].y);

    T[R].y=T[Ls].y+(S*T[Rs].x+C*T[Rs].y);//一样的方法

    return ;

}

int main()

{

    //printf("%.16lf",PI);

    int n,m;

    while(scanf("%d%d",&n,&m)!=EOF)

    {

        for(int i=1;i<=n;i++)   scanf("%d",&L[i]),pre[i]=PI;

        build(1,1,n);

        for(int i=1,a,b;i<=m;i++)

        {

            scanf("%d%d",&a,&b);

            double D=1.0*b/180*PI;

            change(1,1,n,a+1,D-pre[a+1]);

            pre[a+1]=D;

            printf("%.2lf %.2lf\n",T[1].x,T[1].y);

        }

    }

    return 0;

}