题意:
起重机的机械臂, 由n段组成, 对某一些连接点进行旋转, 询问每次操作后的末端坐标.
思路:
由于旋转会影响到该点之后所有线段的角度, 因此容易想到用线段树记录角度, 成段更新. (但是不是每一次操作都要询问一次么? 那么懒惰标记还有用么? 如果使用懒惰标记, 将一些线段视为整体, 那么这些线段岂不是又要用一个线段树记录一段区间的总长? 树状数组亦可...)
将向量视为数量整体加和, 融入到线段树的操作中, 就可以避免角度和坐标分离的麻烦事..
旋转角度与坐标的关系:
根据位移向量绕原点旋转的表达式, 借助三角函数公式, 可推得矩阵形式的向量旋转公式.
[ x1 ] = [ cos a sin a ] [ x0 ]
[ y1 ] [ -sin a cos a] [ y0 ]
思维上的不足:
对线段树的求和理念理解不深, 只是想到了角度的加和, 殊不知向量本身也可以加和, 而且"和向量"与"分向量"的关系是层层细分下去的.
有了这样的思维框架, 就不难照顾好 sx, sy, sd 这三个数组了. 因为要表示一个"位移向量", 使用这三个参数是自然的.
#include<cstdio>
#include<cmath>
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
///把所有的区间看做等效的一条线段
///旋转的时候认为是只旋转宏观的!中间的细节是不考虑的
using namespace std;
const int mm=11111;
int sd[mm<<2],degree[mm];
double sx[mm<<2],sy[mm<<2];
void rotate(int rt,int sd)
{
double d=sd*asin(1.0)/90.0;//degrees in rad
double x=cos(d)*sx[rt]-sin(d)*sy[rt];
double y=sin(d)*sx[rt]+cos(d)*sy[rt];
sx[rt]=x,sy[rt]=y;// rotate the sub-tree as a whole~!
}
void pushdown(int rt)//!
{//认为每一条线段都是一个[偏移量], 最终是加和嘛
rotate(rt<<1,sd[rt]);
rotate(rt<<1|1,sd[rt]);
sd[rt<<1]+=sd[rt];//将标记落在下一层
sd[rt<<1|1]+=sd[rt];
sd[rt]=0;//清除本层标记
}
void pushup(int rt)
{
sx[rt]=sx[rt<<1]+sx[rt<<1|1];
sy[rt]=sy[rt<<1]+sy[rt<<1|1];
}
void build(int l,int r,int rt)
{
sd[rt]=0;//segment delta degree (must as a whole)
if(l==r)
{
scanf("%lf",&sy[rt]);
sx[rt]=0;//segment coordinates
return;
}
int m=(l+r)>>1;
build(lson);
build(rson);
pushup(rt);//only coordinates
}
void updata(int p,int d,int l,int r,int rt)
{
if(p<l)//if this sub-tree is completely in the rorated range, rotate.
{
rotate(rt,d);
sd[rt]+=d;
return;
}
if(sd[rt])pushdown(rt);//修正儿子的delta degree
int m=(l+r)>>1;
if(p<m)updata(p,d,lson);//如果[涉及]左儿子,就更新
updata(p,d,rson);///[一定][涉及]右儿子!
pushup(rt);///再更新总体的坐标
}
int main()
{
int i,j,n,m,flag=0;
while(~scanf("%d%d",&n,&m))
{
if(flag)puts("");else flag=1;//判断第一个
build(1,n,1);
for(i=0;i<n;++i)degree[i]=180;//degree after ith segment
while(m--)
{
scanf("%d%d",&i,&j);
updata(i,j-degree[i],1,n,1);//(index, delta degree, tree)
degree[i]=j;
printf("%.2lf %.2lf\n",fabs(sx[1])<1e-8?0:sx[1],fabs(sy[1])<1e-8?0:sy[1]);
}//output root's coordinates, caution: precision
}
return 0;
}
自己敲一遍:
#include <cstdio>
#include <cmath>
#define lson l, m, rt<<1
#define rson m+1, r, rt<<1|1
//892K 985MS
const double EPS = 1e-8;
const int MAXN = 11111;
int degree[MAXN],sd[MAXN<<2];
double sx[MAXN<<2],sy[MAXN<<2];
int n,c,s,a;
bool flag;
void PushUp(int rt)
{
sx[rt] = sx[rt<<1] + sx[rt<<1|1];
sy[rt] = sy[rt<<1] + sy[rt<<1|1];
}
void build(int l, int r, int rt)
{
sd[rt] = 0;
if(l==r)
{
sx[rt] = 0;
scanf("%lf",&sy[rt]);
return;
}
int m = (l+r)>>1;
build(lson);
build(rson);
PushUp(rt);
}
void rotate(int sd, int rt)
{
double d = sd*asin(1.0)/90.0;
double x = cos(d)*sx[rt] - sin(d)*sy[rt];
double y = sin(d)*sx[rt] + cos(d)*sy[rt];
sx[rt] = x, sy[rt] = y;
}
void PushDown(int rt)
{
if(sd[rt])
{
rotate(sd[rt], rt<<1);
rotate(sd[rt], rt<<1|1);
sd[rt<<1] += sd[rt];
sd[rt<<1|1] += sd[rt];
sd[rt] = 0;
}
}
void update(int p, int d, int l, int r, int rt)
{
if(p<l)
{
rotate(d, rt);
sd[rt] += d;
return;
}
PushDown(rt);
int m = (l+r)>>1;
if(p<m) update(p, d, lson);
update(p, d, rson);
PushUp(rt);
}
int main()
{
flag = false;
while(scanf("%d %d",&n,&c)==2)
{
if(flag) puts("");
else flag = true;
build(1, n, 1);
for(int i=1;i<n;i++) degree[i] = 180;
while(c--)
{
scanf("%d %d",&s,&a);
update(s, a - degree[s], 1, n, 1);
degree[s] = a;
printf("%.2lf %.2lf\n",fabs(sx[1])<EPS?0:sx[1],fabs(sy[1])<EPS?0:sy[1]);
}
}
}
线段树小结:
用树结构表示线段的属性, 维护和, 最值, 覆盖等.
首先:
树的组成:
1. 你所需要的属性, 以及维护这些属性所需的辅助值.
2. 标记.
维护操作包括:
build建树:
初始化这些属性.
PushUp向上更新:
更新儿子属性值之后, 回溯时向上更新根的属性.
这个和标记无关.
PushDown向下传递标记:
update或query的时候, 若一个区间被查询分割, 则需要考察儿子, 那么懒惰标记就需要检查更新. 因为懒惰标记是记录儿子的性质, 所以节点本身应该是正确的, 自己的标记不应该改变自己的属性. 标记下落之后记得清除自己的标记.
update更新:
单点修改或者成段修改: 找到应该修改的区间(找的过程记得下落标记), 修改属性, 修改标记.
query询问:
找到应该询问的区间, 找的过程记得下落标记. 返回需要的结果.