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;
}
网友评论