本文主要是介绍poj Crane 线段树变种，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
今天刚刚看了线段树，以为挺简单，不就就是一个区间的最小值，靠父亲节点来判断~。
谁知，看了后面的一道运用线段树的问题，顿时傻眼了
，代码看了好多遍，根本就是 就是 就是啥也不懂呗。。。。还能是神马。然后就是老规矩，看网上题解。。。然而这次居然不灵了，还是没怎么懂，然后，然后，然后就是去洗衣服去了呗，还能干神马。神奇的是，在洗衣服过程中，我居然有点想通了。。。。 有点激动地来跟大家分享一下。
首先明确各种题解中的坐标不是单个棍子首尾2端点各自的坐标，而是在特定的区间内所有棍子合起来的(可以看作一个向量)的坐标。而这个特定区间其实就是 线段树分成的各个区间呗。。。。(一直平分，直到最后是剩下叶节点），而我们学习的线段树的根节点代表整个区域的最小值，是根据其2个儿子节点的数值，比较得来的，如果改变某一叶节点的值，会相应的改变包含其的所有节点的值。同理：在此题中，根节点的坐标就是所有棍子合起来的坐标呗，它的值是根据其2个儿子节点的数值合起来的呗。。。。。然后往下推一直到叶节点。。。而转动某一根棍子，相当于把线段树中的叶节点的值给改变了呗，咱们就要相应地改变包含这根棍子的所有节点(区域)的值。思路就是这样。。。。。
下面代码是书上的。。。。。
#include<stdio.h> #include<math.h> #define M_PI acos(-1.0) #define SIZE 100100 int N,C; int L[20010],S[20010],A[20010]; double vx[SIZE<<2],vy[SIZE<<2],ang[SIZE<<2],prv[10010]; void init(int k,int l,int r) {int chl,chr;ang[k]=vx[k]=0.0;if(r-l==1)vy[k]=L[l];else{chl=k*2+1;chr=k*2+2;init(chl,l,(l+r)/2);init(chr,(l+r)/2,r);vy[k]=vy[chl]+vy[chr];} } void change(int s,double a,int v,int l,int r) {int chl,chr,m;double ss,c;if(s<=l)return ;elseif(s<r){chl=v*2+1;chr=v*2+2;m=(l+r)/2;change(s,a,chl,l,m);change(s,a,chr,m,r);if(s<=m){ang[v]+=a;}ss=sin(ang[v]);c=cos(ang[v]);vx[v]=vx[chl]+(c*vx[chr]-ss*vy[chr]);vy[v]=vy[chl]+(ss*vx[chr]+c*vy[chr]);} } int main(void) {int s,i;double a;while(scanf("%d%d",&N,&C)!=EOF){for(i=0;i<N;i++)scanf("%d",&L[i]);for(i=0;i<C;i++)scanf("%d%d",&S[i],&A[i]);init(0,0,N);for(i=1;i<N;i++)prv[i]=M_PI;for(i=0;i<C;i++){s=S[i];a=A[i]*2*M_PI/360.0;change(s,a-prv[s],0,0,N);prv[s]=a;printf("%.2f %.2f\n",vx[0],vy[0]);}}}#include<stdio.h> #include<math.h> #define lc p<<1,s,mid #define rc p<<1|1,mid+1,e #define mid ((s+e)>>1) #define N 10005 #define pi acos(-1.0) #define eps 1e-8 double x[N>>2],y[N>>2],rot[N>>2]; double rad[N];void rotate(double &x,double &y,double r) {double xx=x;x=xx*cos(r)-y*sin(r);y=xx*sin(r)+y*cos(r); } void pushup(int p) {x[p]=x[p<<1]+x[p<<1|1];y[p]=y[p<<1]+y[p<<1|1]; } void pushdown(int p,int s,int e) {int lp,rp;if(fabs(rot[p])>eps)return ;lp=p<<1;rp=p<<1|1;rot[lp]+=rot[p];rot[rp]+=rot[p];rotate(x[lp],y[lp],rot[p]);rotate(x[rp],y[rp],rot[p]);rot[p]=0; } void build(int p,int s,int e) {rot[p]=0;if(s==e){scanf("%lf",&y[p]);x[p]=0;rad[s]=pi;return ;}build(lc);build(rc);pushup(p); } void update(int p,int s,int e,int l,int r,double v) {if(l<=s&&e<=r){rot[p]+=v;rotate(x[p],y[p],v);return ;}pushdown(p,s,e);if(l<=mid)update(lc,l,r,v);if(r>mid)update(rc,l,r,v);pushup(p); } int main(void) {int n,m,p,first=1;double r;while(~scanf("%d%d",&n,&m)){build(1,1,n);while(m--){scanf("%d%lf",&p,&r);r=r/180.0*pi;update(1,1,n,p+1,n,r-rad[p]);rad[p]=r;printf("%.2lf %.2lf\n",x[1],y[1]);}}}
这篇关于poj Crane 线段树变种的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
