P8105 [LCOI RI]Cow Dance 题解

· · 题解

思路

这个题是对于subtask进行处理（有的不能同时得分，例如 subtask 2 和 subtask 3）。

subtask 1

暴力就好了。

subtask 2

维护区间旋转角度，区间和，线段树即可。

subtask 3

维护区间放大倍数，区间和，线段树即可。

subtask 4

维护区间平移，两个线段树即可。

subtask 5

暴力。

subtask 6

和正解几乎一样但有缺陷的做法。

subtask 7

留给常数较大的同正解相同的做法。

subtask 8

注意到区间旋转位似都可以拿矩阵维护，就相当于矩阵加和矩阵乘，或者用虚数维护。

对于平移操作，就是加上一个虚数。

对于旋转和位似操作，可以先把这个中心移到原点，再乘上一个虚数即可，维护区间加，区间乘即可。

复杂度 \Theta(n\log n)。

code

这一题比较良心，不用快读。

#include<bits/stdc++.h>
using namespace std;
#define maxn 300010
int n,m;
int x,y,a,b,p,q,opt;
const double eps=1e-6;
struct Cp{
    double a,b;
    Cp(double aa=0,double bb=0):a(aa),b(bb){}
    Cp operator+(Cp x)const{return Cp(a+x.a,b+x.b);}
    Cp operator-(Cp x)const{return Cp(a-x.a,b-x.b);}
    Cp operator*(Cp x)const{return Cp(a*x.a-b*x.b,a*x.b+x.a*b);}
    Cp operator*(int x)const{return Cp(a*x,b*x);}
    bool operator==(double x)const{return fabs(b)<eps&&fabs(a-x)<eps;}
    bool operator==(Cp x)const{return fabs(a-x.a)<eps&&fabs(b-x.b)<eps;}
    void print(){
        printf("%.6lf %.6lf\n",a,b);
    }
};
Cp e(int a){
    double r=a*3.14159265358979323846/180;
    return Cp(cos(r),-sin(r));
}
    struct sto_DX_orz{
        int l,r;
        Cp sum,mul,add;
    }tree[maxn<<2];
    void pushup(int x){
        tree[x].sum=tree[x<<1].sum+tree[x<<1|1].sum;
    }
    void pushdown(int x){
        if(!(tree[x].mul==1.0)){
            tree[x<<1].add=tree[x<<1].add*tree[x].mul;
            tree[x<<1|1].add=tree[x<<1|1].add*tree[x].mul;
            tree[x<<1].sum=tree[x<<1].sum*tree[x].mul;
            tree[x<<1|1].sum=tree[x<<1|1].sum*tree[x].mul;
            tree[x<<1].mul=tree[x<<1].mul*tree[x].mul;
            tree[x<<1|1].mul=tree[x<<1|1].mul*tree[x].mul;
            tree[x].mul=Cp(1,0);
        }
        if(!(tree[x].add==0)){
            tree[x<<1].add=tree[x<<1].add+tree[x].add;
            tree[x<<1|1].add=tree[x<<1|1].add+tree[x].add;
            tree[x<<1].sum=tree[x<<1].sum+tree[x].add*(tree[x<<1].r-tree[x<<1].l+1);
            tree[x<<1|1].sum=tree[x<<1|1].sum+tree[x].add*(tree[x<<1|1].r-tree[x<<1|1].l+1);
            tree[x].add=Cp(0,0);
        }
    }
    void build(int x,int l,int r){
        tree[x].l=l,tree[x].r=r;
        tree[x].mul=Cp(1,0);
        if(l==r){
            int a,b;
            cin>>a>>b;
            tree[x].sum=Cp((double)a,(double)b);
            return;
        }
        int mid=(l+r)>>1;
        build(x<<1,l,mid),build(x<<1|1,mid+1,r);
        pushup(x);
    }
    void change1(int x,int l,int r,Cp k){
        if(tree[x].l>=l&&tree[x].r<=r){
            tree[x].add=tree[x].add+k;
            tree[x].sum=tree[x].sum+k*(tree[x].r-tree[x].l+1);
            return;
        }
        pushdown(x);
        int mid=(tree[x].l+tree[x].r)>>1;
        if(l<=mid)change1(x<<1,l,r,k);
        if(r>mid)change1(x<<1|1,l,r,k);
        pushup(x);
    }
    void change2(int x,int l,int r,Cp k){
        if(tree[x].l>=l&&tree[x].r<=r){
            tree[x].add=tree[x].add*k;
            tree[x].mul=tree[x].mul*k;
            tree[x].sum=tree[x].sum*k;
            return;
        }
        pushdown(x);
        int mid=(tree[x].l+tree[x].r)>>1;
        if(l<=mid)change2(x<<1,l,r,k);
        if(r>mid)change2(x<<1|1,l,r,k);
        pushup(x);
    }
    Cp ask(int x,int l,int r){
        if(tree[x].l>=l&&tree[x].r<=r)return tree[x].sum;
        pushdown(x);
        int mid=(tree[x].l+tree[x].r)>>1;
        Cp val;
        if(l<=mid)val=(val+ask(x<<1,l,r));
        if(r>mid)val=(val+ask(x<<1|1,l,r));
        return val;
    }
signed main(){
  srand(time(NULL));
    scanf("%d%d",&n,&m);
    build(1,1,n);
    while(m--){
        scanf("%d%d%d",&opt,&x,&y);
        if(opt==4){
            Cp DX=ask(1,x,y);
            DX.a/=(y-x+1),DX.b/=(y-x+1);
            DX.print();
        }else{
            scanf("%d%d",&a,&b);
            Cp A((double)a,(double)b);
            if(opt==1)change1(1,x,y,A);
            else{
                scanf("%d",&p);
                Cp E;
                if(opt==2)E=e(p);
                else scanf("%d",&q),E=Cp((double)p/q,0);
                change2(1,x,y,E);
                change1(1,x,y,A*(Cp(1,0)-E));
            }
        }
    }
}