【2020NOI.AC省选模拟#2】A. 旋转

题目链接

原题解：

把每个点的坐标视为复数，那么每次询问就是区间求平均数（先求和然后除以个数）。一个点绕着原点旋转就是乘以$(\cos 60^\circ +i\sin 60^\circ)$。

一个点绕着某点$A$旋转可以理解为先减去点$A$的坐标，再绕原点旋转，再加上点$A$的坐标。

最终变成用线段树维护复数的序列，支持区间加上一个数和乘上一个数和区间求和，使用打标记的线段树解决。

补充：

在？为什么卡空间？

原题解提供的线段树做法很NICE，然而直接上线段树会被卡空间。然后我百度到了深度好文，学习了线段树少开空间的方法。

首先来个结论：

长度为$n$的序列会形成$2n-1$个节点的线段树。

为啥呢？观察一下线段树的结构，发现有底下的$n$个叶子，之后两个子节点用一个父节点合并。由$n$个连通块合并为一个块需要$n-1$次，所以总共有$2n-1$个节点。

然后我们考虑用DFS序给节点编号。发现对于节点$i$代表$[l,r]$，左儿子的编号就是$i+1$，然后左子树占用了连续的$2(mid-l+1)-1$个编号，那么右儿子编号就是$i+2(mid-l+1)-1+1=i+2(mid-l+1)$。

然后就过了。打标记的线段树参考我自己的这篇博客。

噢还有一点，就是浮点数要记得重写一个等于函数，本题因为有封装，不容易注意到这个问题，但这确实会导致RE。

代码（100分）：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define IL inline

#define RG register

#define _1 first

#define _2 second

using namespace std;

typedef double DB;

#define RI RG int

#define RD RG DB

#define RP RG Pr

#define RM RG Mrk

const int N=1e5;

const DB Pi=acos(-1);

const DB eps=1e-6;

    int n,q;

struct Pr{

    DB x,y;

    Pr(RD x=0,RD y=0):x(x),y(y){}

}mul1=Pr(1,0),add0=Pr(0,0)

,rot=Pr(cos(Pi/3),sin(Pi/3))

,a[N+3],sum[N*2+3];

IL bool eql(RD x,RD y){

    return fabs(x-y)<eps;

}

IL bool operator==(RP x,RP y){

    return eql(x.x,y.x)&&eql(x.y,y.y);

}

IL Pr operator*(RP x,RP y){

    return Pr(x.x*y.x-x.y*y.y,x.y*y.x+x.x*y.y);

}

IL Pr operator*(RD x,RP y){

    return Pr(x*y.x,x*y.y);

}

IL Pr operator+(RP x,RP y){

    return Pr(x.x+y.x,x.y+y.y);

}

struct Mrk{

    Pr m,a;

    Mrk(RP m=mul1,RP a=add0):m(m),a(a){}

}non,tag[N*2+3];

IL bool operator==(RM x,RM y){

    return x.m==y.m&&x.a==y.a;

}

IL int ls(RI i){return i+1;}

IL int rs(RI i,RI l,RI mid){

    return i+((mid-l+1)<<1);

}

IL void f(RI i,RI l,RI r,RM opt){

    if(opt==non)

        return ;

    sum[i]=opt.m*sum[i]+(DB)(r-l+1)*opt.a;

    Mrk tmp=tag[i];

    tag[i]=Mrk(opt.m*tmp.m,opt.m*tmp.a+opt.a);

}

IL void spread(RI i,RI l,RI r){

    RI mid=(l+r)>>1;

    f(ls(i),l,mid,tag[i]);

    f(rs(i,l,mid),mid+1,r,tag[i]);

    tag[i]=non;

}

void build(RI i,RI l,RI r){

    tag[i]=non;

    if(l==r){

        sum[i]=a[l];

        return ;

    }

    RI mid=(l+r)>>1;

    build(ls(i),l,mid);

    build(rs(i,l,mid),mid+1,r);

    sum[i]=sum[ls(i)]+sum[rs(i,l,mid)];

}

void mdf(RI i,RI l,RI r,RI ql,RI qr,RM opt){

    if(ql<=l&&r<=qr){

        f(i,l,r,opt);

        return ;

    }

    spread(i,l,r);

    RI mid=(l+r)>>1;

    if(ql<=mid)

        mdf(ls(i),l,mid,ql,qr,opt);

    if(qr>mid)

        mdf(rs(i,l,mid),mid+1,r,ql,qr,opt);

    sum[i]=sum[ls(i)]+sum[rs(i,l,mid)];

}

Pr qry(RI i,RI l,RI r,RI ql,RI qr){

    if(qr<l||r<ql)

        return add0;

    if(ql<=l&&r<=qr)

        return sum[i];

    spread(i,l,r);

    RI mid=(l+r)>>1;

    if(qr<=mid)

        return qry(ls(i),l,mid,ql,qr);

    if(ql>mid)

        return qry(rs(i,l,mid),mid+1,r,ql,qr);

    return qry(ls(i),l,mid,ql,qr)

          +qry(rs(i,l,mid),mid+1,r,ql,qr);

}

int main(){

    scanf("%d%d",&n,&q);

    for(RI i=1;i<=n;i++)

        scanf("%lf%lf",&a[i].x,&a[i].y);

    build(1,1,n);

    for(RI i=1,l,r;i<=q;i++){

        scanf("%d%d",&l,&r);

        RP tmp=1.0/(r-l+1)*qry(1,1,n,l,r);

        printf("%.10lf %.10lf\n",tmp.x,tmp.y);

        mdf(1,1,n,l,r,Mrk(mul1,-1.0*tmp));

        mdf(1,1,n,l,r,Mrk(rot,add0));

        mdf(1,1,n,l,r,Mrk(mul1,tmp));

    }

    for(RI i=1;i<=n;i++){

        a[i]=qry(1,1,n,i,i);

        printf("%.10lf %.10lf\n",a[i].x,a[i].y);

    }

    return 0;

}

巴特西

【2020NOI.AC省选模拟#2】A. 旋转

题目链接

最新文章

热门文章