【数字_ID】POJ-2991-Crane(线段树+向量)

• 编辑：数字_ID
• 时间：2018年5月19日

1.写在题前

• 之前做过几次省赛的题，碰巧连续遇到了两道和线段树有关的题，然而蒟蒻不会数据结构，卒
• 之后痛定思痛，开始努力补习数据结构，线段树就是第一个要先解决的内容
• 发现大佬们都爱写博客，我发现其实写给别人看，也是写给自己看的过程，帮助自己更深入的理解题目和题目中的知识点，所以以后在简书上应该会比较勤奋的更新，不只限于算法题解，还有CTF的write-up或者各种各样的教程。

2. 题意

• 有许多线段，每个线段首尾相连，初始x坐标均为0（所有线段均在y轴，且以此相连），现在又这么一种操作，输入i,k可以对第i个线段进行旋转操作，使其与它底下的那个线段（第i-1个线段）形成的角度为k，同时，第i个上面的所有线段也要跟着旋转，问最后点的坐标

3. 关于线段树

• 线段树是一种对区间操作很方便的数据结构，类似平衡二叉树的操作，用来对一个区间的某个值进行管理，具体教程网上很多，在这里就不说太多
• 这道题是挑战程序设计那本白书上的经典例题，所以也是很多人又来入门练习线段树的必做题，我自己也是费了不少功夫在理解这道题和它的做法

4. 关于这道题

• 当拿到一道题，先看这道题的一些特征
  • 首先，对于一个线段进行操作，这条线段之后的操作也会跟着进行改变，是不是很像区间修改呢
  • 其次，求某个点坐标，只需要将这之前的线段进行向量求和，得到一个“大”的向量即可，是不是非常区间求和呢？只不过这里的“和”是两条向量的和
  • 同时，求一段向量的向量和，是不是也就同时知道这个大向量的角度了？对于每次旋转，我们不也就知道到应该旋转多少角度？不也就知道了这个点之后的每个向量最后新的向量坐标？
  • 好，我们大概想到了用线段树，那么，应该怎么做呢？
• 对于每个节点，我们需要维护两个最基本的量，一个是向量坐标（x,y),即这一段区间的线段的向量和是多少，然后维护一个角度
• 之所以要维护角度，因为操作是基于旋转的，而且题目不是直接给出旋转角度，而是与它上一个线段形成夹角，所以角度要可查询
• 那么，需要一个查询，用来查询某一些向量和之后的向量的角度
• 同时需要一个函数修改向量坐标及之后的角度
• 对于最后的输出，是所有向量之和的坐标，也就是线段树中根节点的值
• 可以用lazy来延迟这个修改，达到不错的优化

5. 代码

//感谢demian详细的代码和教程
//http://www.cnblogs.com/demian/p/6164613.html

#include<iostream>
#include<math.h>

using namespace std;

const int maxn = 10002;
const int root = 1;
const int MAXN = maxn;
const int ROOT = 1;
const double PI = acos(-1.0);  
const double EPS = 1e-8;  

#define LSon(x)((x)<<1)//x*2
#define RSon(x)((x)<<1|1)//x*2+1


struct Seg{
    double x,y;
    int flag;
    int degree;
};

void Rotate(Seg& node,int degree);
double GetRad(int x);  

struct SegTree{
    Seg node[maxn<<2];
    void Update(int pos)
    {
        node[pos].x = node[LSon(pos)].x+node[RSon(pos)].x;
        node[pos].y = node[LSon(pos)].y+node[RSon(pos)].y;
    }
    void Build(int l,int r,int pos)
    {
        node[pos].x = node[pos].y = 0;
        node[pos].flag = 0;
        node[pos].degree = 0;
        if(l == r){
            scanf("%lf", &node[pos].y);  
            return;
        }
        int m = l+r>>1;
        Build(l,m,LSon(pos));
        Build(m+1,r,RSon(pos));
        Update(pos);
    }
    void Push(int pos)
    {
        Seg& father = node[pos];
        Seg& lson = node[LSon(pos)];
        Seg& rson = node[RSon(pos)];
        if(father.flag)
        {
            Rotate(lson,father.flag);
            Rotate(rson,father.flag);
            lson.flag += father.flag;
            rson.flag += father.flag;
            father.flag = 0;
        }
    }
    void Modify(int l,int r,int pos,int x,int y,int z)
    {
        if(x<=l&&r<=y)//修改区间包含当前区间
        {
            Rotate(node[pos],z);
            node[pos].flag += z;
            return;
        }
        Push(pos);
        int m = l+r >> 1;
        if(x<=m)Modify(l,m,LSon(pos),x,y,z);
        if(y>m)Modify(m+1,r,RSon(pos),x,y,z);
        Update(pos);
    }
    int Query(int l,int r,int pos,int x)
    {
        if(l == r)return node[pos].degree;
        Push(pos);//之前对于区间的修改，不是对于叶子节点全部修改，所以有一个flag用来表示，这个节点的子节点要加上对应的值，对如果有时候要具体的查询，必定不能只改变非叶子节点，所以在查询过程中也加入Push操作，将当前节点的改变push到其叶子节点，算是一种优化吧
        int m = l+r >> 1;
        if(x<=m)return Query(l,m,LSon(pos),x);
        else return Query(m+1,r,RSon(pos),x);
    }
};

int n,c;
int s,a;

SegTree tree;

int main()
{
    bool first = true;
    while(cin>>n>>c)
    {
        tree.Build(0,n-1,root);
        printf("%s",first?first = false,"":"\n");
        for(int i = 0;i<c;i++)
        {
            cin>>s>>a;
            int degree = tree.Query(0,n-1,root,s-1)+180+a-tree.Query(0,n-1,root,s);
            tree.Modify(0,n-1,root,s,n-1,degree);
            printf("%.2lf %.2lf\n", tree.node[root].x + EPS, tree.node[root].y + EPS);
        }
    }
    return 0;
}

double GetRad(int x)
{
    return x*PI/180;
}

void Rotate(Seg&node,int degree)
{
    double rad = GetRad(degree);  
    double x = node.x; double y = node.y;  
    node.x = x * cos(rad) + y * -sin(rad);  
    node.y = x * sin(rad) + y * cos(rad);  
    node.degree = (node.degree + degree) % 360;  
}