【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
#include
#include
#include
#include
#include
#include
#include
#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(qrql)
        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;

}
线段树计算几何模拟赛

相关

2019.11.8模拟赛

[NOIP模拟赛] 2021.11.16

20211116 NOIP 模拟赛

20210628模拟赛解题报告

20201115gryz模拟赛解题报告

#直径，线段树#51nod 1766 树上的最远点对

「NOI2020」命运（树形DP+线段树合并）

线段树学习笔记 1

关于 线段树 的一些认识

线段树

[NOI2015]软件包管理器（巧用线段树）

11.16模拟赛 简记

标签