学步园

http://poj.org/problem?id=2991

题意：

有N根杆子，前后两根杆子通过一个节点连接，每个节点可以旋转一定的角度，每次给你一个操作（s,a）表示将第s与s+1之间的角度修改为a度，并且每次操作之后都需要求出第N个节点的位置。 

思路：

线段树。直观的想法是这样的， 如果第s与s+1之间的角度被修改为a的话，其前面的（1-s）是不会发现改变的， 但是其后的（s+1,N）都会发生改变， 也就是说如果我们知道了s与s+1之间的角度增加了一个角度aa， 那么他后面的所有的线段的角度都要增加这个角度aa。这样我们就很容易会想到线段树的做法，成段地去更新后面的所有的线段的角度。最后要询问的终点的坐标也就是所有线段（看作向量）的和了。

代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#define LL(a) ( (a)<<1 )
#define RR(a) ( (a)<<1|1 )
#define PI (4*atan(1.0))
#define eps  (1e-8)
const int MAXN = 10010 ;
int N , C ;
int len[MAXN] ;

int angle[MAXN<<2] ;
double x[MAXN<<2] ,y[MAXN<<2] ;
int lazy[MAXN<<2] ;

void up(int l ,int r, int idx){
    x[idx] = x[ LL(idx) ] + x[ RR(idx) ] ;
    y[idx] = y[ LL(idx) ] + y[ RR(idx) ] ;
}

void build(int l ,int r, int idx){
    lazy[idx] = angle[idx] = 0 ;
    if(l == r){
        x[idx] = 0 ;
        y[idx] = len[l] ;
        return ;
    }
    int mid = (l + r) >> 1 ;
    build(l , mid , LL(idx));
    build(mid+1 , r , RR(idx) ) ;
    up(l ,r, idx);
}

void down(int l ,int r, int idx){
    if( lazy[idx] ){
        angle[ LL(idx) ] = ( angle[ LL(idx) ] + lazy[idx] ) % 360;
        angle[ RR(idx) ] = ( angle[ RR(idx) ] + lazy[idx] ) % 360;
        double a = x[ LL(idx) ] , b = y[ LL(idx) ] ;
        x[ LL(idx) ] = cos( lazy[idx]/180.0*PI )*a - sin( lazy[idx]/180.0*PI )*b ;
        y[ LL(idx) ] = sin( lazy[idx]/180.0*PI )*a + cos( lazy[idx]/180.0*PI )*b ;

        a = x[ RR(idx) ]  ; b = y[ RR(idx) ] ;
        x[ RR(idx) ] = cos( lazy[idx]/180.0*PI )*a - sin( lazy[idx]/180.0*PI )*b ;
        y[ RR(idx) ] = sin( lazy[idx]/180.0*PI )*a + cos( lazy[idx]/180.0*PI )*b ;

        lazy[ LL(idx) ] = ( lazy[ LL(idx) ] + lazy[idx] ) % 360 ;
        lazy[ RR(idx) ] = ( lazy[ RR(idx) ] + lazy[idx] ) % 360 ;
        lazy[idx] = 0 ;
    }
}

double query(int l ,int r , int idx, int x){
    if(l == r)  return angle[idx] ;
    down(l ,r , idx);
    int mid = (l + r) >> 1 ;
    if( x <= mid )  return query(l ,mid , LL(idx) ,x ) ;
    else            return query(mid+1 , r , RR(idx) , x ) ;
}



void update(int l ,int r, int idx , int a, int b , int aa ){
    if(l==a && r==b){
        angle[idx] = ( angle[idx] + aa ) % 360 ;
        lazy[idx] = ( lazy[idx] + aa ) % 360 ;
        double xx = x[idx] , yy = y[idx] ;
        x[idx] = cos( aa/180.0*PI )*xx - sin( aa/180.0*PI ) * yy ;
        y[idx] = sin( aa/180.0*PI )*xx + cos( aa/180.0*PI ) * yy ;
        return ;
    }
    down(l ,r , idx) ;
    int mid = (l + r) >> 1;
    if( b<=mid )    update(l , mid ,LL(idx) , a , b , aa );
    else if( mid<a )    update(mid+1, r, RR(idx) ,a , b, aa ) ;
    else{
        update( l ,mid , LL(idx) , a,  mid , aa ) ;
        update( mid+1, r, RR(idx) ,mid+1, b, aa ) ;
    }
    up(l ,r, idx);
}

void solve(){
    int s, a ;
    for(int i=1;i<=C;i++){
        scanf("%d %d",&s ,&a );
        int a1 = query(1 , N , 1 ,s ) ;
        int a2 = query(1 , N , 1 ,s+1);
        int aa = (a - ( 180 +  ( a2  - a1 + 360 )%360)%360 + 360 ) % 360 ;
        update(1 ,N ,1 , s+1, N , aa ) ;
        printf("%.2lf %.2lf\n",x[1] , y[1]) ;
    }
}

int main(){
    bool f = true ;
    while(scanf("%d%d",&N,&C) == 2){
        for(int i=1;i<=N;i++){
            scanf("%d",&len[i]);
        }
        build(1,N,1);
        if( !f )    puts("");
        f = false ;
        solve() ;
    }
    return 0 ;
}