POJ 2991線分ツリー

POJ 2991タイトルリンク:http://poj.org/problem?id=2991 題意:n個の初期線分を与え、線分の先頭と末尾がつながっている.最初はy軸にありました今は回転操作をするたびに.操作時には、前u個の点が動かず、第u個の点がu-1点に対して回転し、u点の後ろの点がuに対する位置も動かない.構想:セグメントツリー、区間更新.操作ごとにuおよびuの後のすべての点を更新することに相当するため、x、y、angle、flagの4つの値があり、それぞれ横座標、縦座標、角度、遅延フラグを表す点構造を保存する.更新方法は奇抜で、具体的にはpush_を参照してください.down,push_up,func関数ですが,遅延マーキングの考え方でもあります.ソース:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
const int MAXN = 10000 + 5;
const double PI = acos(-1.0);
int n, q;
double x[MAXN * 4], y[MAXN * 4];
int angle[MAXN * 4];
int flag[MAXN * 4];
int a[MAXN * 4];
void func(int o, int ang)   ///     { double tx = x[o], ty = y[o]; x[o] = tx * cos(ang * PI / 180.0) - ty * sin(ang * PI / 180.0);
    y[o] = tx * sin(ang * PI / 180.0) + ty * cos(ang * PI / 180.0);
    angle[o] = (angle[o] + ang) % 360;
    flag[o] = (flag[o] + ang) % 360;
}
void push_up(int o)
{
    x[o] = x[o << 1] + x[(o << 1) | 1];
    y[o] = y[o << 1] + y[(o << 1) | 1];
}
void push_down(int o)
{
     if(flag[o]){
        func(o << 1, flag[o]);
        func((o << 1) | 1, flag[o]);
        flag[o] = 0;
     }
}
void build(int l, int r, int o)
{
    x[o] = 0;
    angle[o] = flag[o] = 0;
    if(l == r){
        y[o] = a[l];
    }
    else{
        int mid = (l + r) >> 1;
        build(l, mid, o << 1);
        build(mid + 1, r, (o << 1) | 1);
        push_up(o);
    }
}
int query(int u, int l, int r, int o)
{
//    printf("u = %d, l = %d, r = %d, o = %d, angle = %d, flag = %d
", u, l, r, o, angle[o], flag[o]);
    if(l == r) return angle[o];
    else{
        push_down(o);
        int mid = (l + r) >> 1;
        int ang;
        if(u <= mid) ang = query(u, l, mid, o << 1);
        else ang = query(u, mid + 1, r, (o << 1) | 1);
        push_up(o);
        return ang;
    }
}
void update(int l, int r, int ang, int L, int R, int o)
{
//    printf("o = %d, l = %d, r = %d, L = %d, R = %d, ang = %d
", o, l, r, L, R, ang);
    if(l <= L && r >= R){
        func(o, ang);
    }
    else{
        push_down(o);
        int mid = (L + R) >> 1;
        if(l <= mid) update(l, r, ang, L, mid, o << 1);
        if(mid < r) update(l, r, ang, mid + 1, R, (o << 1) | 1);
        push_up(o);
    }
//    printf("o = %d, angle[o] = %d, flag[o] = %d
", o, angle[o], flag[o]);
}
int main()
{
//    freopen("data.txt", "r", stdin);
    int f = 1;
    while(scanf("%d%d", &n, &q) != EOF){
        for(int i = 1 ; i <= n ; i++) scanf("%d", a + i);
        if(f) f = 0;
        else printf("
");
        build(1, n, 1);
//        printf("x[1] = %.2f y[1] = %.2f
", x[1], y[1]);
        while(q--){
            int u, v;
            scanf("%d%d", &u, &v);
            int a1 = query(u, 1, n, 1);
            int a2 = query(u + 1, 1, n, 1);
//            int ang = query(u, 1, n, 1) - 180 + v - query(u + 1, 1, n, 1);
            int ang = (v - (a2 - a1 + 180 + 360) % 360) % 360;
//            printf("ang = %d, a1 = %d, a2 = %d
", ang, a1, a2);
//            ang = (ang + 360) % 360;
            update(u + 1, n, ang, 1, n, 1);
            printf("%.2f %.2f
", x[1], y[1]);
        }
    }
    return 0;
}