2021-team02-paste

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e6+1e3+7;

struct Matrix{
    int a[3][3];

    void init()
    {
        for(int i=0;i<3;i++)
            a[i][i]=1;
    }

    void clear()
    {
        for(int i=0;i<3;i++)
            for(int j=0;j<3;j++)
                a[i][j]=0;
    }
};

Matrix operator +(const Matrix &A,const Matrix &B)
{
    Matrix ret;
    ret.clear();
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            ret.a[i][j]=A.a[i][j]+B.a[i][j];
    return ret;
}

Matrix operator *(const Matrix &A,const Matrix &B)
{
    Matrix ret;
    ret.clear();
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            for(int k=0;k<3;k++)
                ret.a[i][j]=(ret.a[i][j]+A.a[i][k]*B.a[k][j]);
    return ret;
}

struct T{
    int l,r,ls,rs;
    int tf;
    Matrix tag,val;
}t[N*2+1];

void update(int x)
{
    t[x].val=t[t[x].ls].val+t[t[x].rs].val;
}

void add(int x,const Matrix &v)
{
    t[x].val=t[x].val*v;
    t[x].tag=t[x].tag*v;
}

void pushdown(int x)
{
    add(t[x].ls,t[x].tag);
    add(t[x].rs,t[x].tag);
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
            t[x].tag.a[i][j]=(i==j);
}

int cnt;

int dc,rev[N];

Matrix w[N];

int build(int l,int r)
{
    int x=++cnt;
    t[x].l=l,t[x].r=r;
    t[x].tag.clear();
    t[x].tag.init();
    if(l==r)
    {
        t[x].val=w[rev[l]];
        return x;
    }
    int mid=(l+r)>>1;
    t[x].ls=build(l,mid);
    t[x].rs=build(mid+1,r);
    update(x);
    return x;
}

void change(int x,int l,int r,const Matrix &v)
{
    if(l<=t[x].l&&t[x].r<=r)
    {
        add(x,v);
        return;
    }
    pushdown(x);
    int mid=(t[x].l+t[x].r)>>1;
    if(l<=mid)
        change(t[x].ls,l,r,v);
    if(r>mid)
        change(t[x].rs,l,r,v);
    update(x);
}

Matrix query(int x,int l,int r)
{
    if(l<=t[x].l&&t[x].r<=r)
        return t[x].val;
    pushdown(x);
    int mid=(t[x].l+t[x].r)>>1;
    Matrix ret;
    ret.clear();
    if(l<=mid)
        ret=ret+query(t[x].ls,l,r);
    if(r>mid)
        ret=ret+query(t[x].rs,l,r);
    return ret;
}

int n,Q;

int st[N],ed[N],top[N],sz[N],son[N],fa[N],dep[N];

vector<int>g[N],X[N],Y[N],Z[N];

void dfs1(int x)
{
    sz[x]=1;
    for(int i=0;i<g[x].size();i++)
    {
        int v=g[x][i];
        if(v==fa[x])
            continue;
        dep[v]=dep[x]+1;
        fa[v]=x;
        dfs1(v);
        w[v].a[0][0]=X[x][i];
        w[v].a[0][1]=Y[x][i];
        w[v].a[0][2]=Z[x][i];
        sz[x]+=sz[v];
        if(sz[v]>sz[son[x]])
            son[x]=v;
    }
}

void dfs2(int x)
{
    st[x]=ed[x]=++dc;
    rev[dc]=x;
    if(!son[x])
        return;
    top[son[x]]=top[x];
    dfs2(son[x]);
    for(auto v:g[x])
    {
        if(v==fa[x]||v==son[x])
            continue;
        top[v]=v;
        dfs2(v);
    }
    ed[x]=dc;
}

char op[11];

int getpos(char ch)
{
    if(ch=='x')
        return 0;
    if(ch=='y')
        return 1;
    return 2;
}

Matrix mod;

Matrix qa,qb;

long double qry(int x,int y)
{
    qa.clear(),qb.clear();
    while(top[x]!=top[y])
    {
        if(dep[top[x]]>dep[top[y]])
        {
            qa=qa+query(1,st[top[x]],st[x]);
            x=fa[top[x]];
        }
        else
        {
            qb=qb+query(1,st[top[y]],st[y]);
            y=fa[top[y]];
        }
    }
    if(dep[x]>dep[y])
        qa=qa+query(1,st[y]+1,st[x]);
    else if(dep[y]>dep[x])
        qb=qb+query(1,st[x]+1,st[y]);
    long double X=0,Y=0,Z=0;
    X=qa.a[0][0]-qb.a[0][0];
    Y=qa.a[0][1]-qb.a[0][1];
    Z=qa.a[0][2]-qb.a[0][2];
    return sqrt(X*X+Y*Y+Z*Z);
}

signed main()
{
    scanf("%lld%lld",&n,&Q);
    for(int i=1;i<n;i++)
    {
        int u,v,w;
        scanf("%lld%lld%lld",&u,&v,&w);
        scanf("%s",op);
        int id=getpos(op[0]);
        int f=op[1]=='+'?1:-1;
        int dlt[3]={0,0,0};
        dlt[id]+=f*w;
        g[u].push_back(v);
        X[u].push_back(dlt[0]);
        Y[u].push_back(dlt[1]);
        Z[u].push_back(dlt[2]);
        g[v].push_back(u);
        X[v].push_back(-dlt[0]);
        Y[v].push_back(-dlt[1]);
        Z[v].push_back(-dlt[2]);
    }
    dfs1(1);
    top[1]=1;
    dfs2(1);
    build(1,n);
    while(Q--)
    {
        int cop;
        scanf("%lld",&cop);
        if(cop==1)
        {
            int x,y,d;
            scanf("%lld%lld%s%lld",&x,&y,op,&d);
            int pos=getpos(op[0]);
            int flag=0;
            if(y==fa[x])
            {
                d=360-d;
                swap(x,y);
                flag=1;
            }
            if(d==180)
            {
                mod.clear();
                for(int i=0;i<3;i++)
                    mod.a[i][i]=(i==pos?1:-1);
                if(st[y]+flag<=ed[y])
                    change(1,st[y]+flag,ed[y],mod);
            }
            else
            {
                int p1,p2;
                if(pos==0)
                    p1=1,p2=2;
                else if(pos==1)
                    p1=2,p2=0;
                else
                    p1=0,p2=1;
                mod.clear();
                mod.a[pos][pos]=1;
                if(d==90)
                {
                    mod.a[p1][p2]=1;
                    mod.a[p2][p1]=-1;
                }
                else
                {
                    mod.a[p2][p1]=1;
                    mod.a[p1][p2]=-1;
                }
                if(st[y]+flag<=ed[y])
                    change(1,st[y]+flag,ed[y],mod);
            }
        }
        else
        {
            int x,y;
            scanf("%lld%lld",&x,&y);
            printf("%.15Lf\n",qry(x,y));
        }
    }
}


请将/etc/apt/sources.list替换为下述内容:
deb http://mirrors.zju.edu.cn/ubuntu bionic main universe restricted multiverse
deb http://mirrors.zju.edu.cn/ubuntu bionic-security main universe restricted multiverse
deb http://mirrors.zju.edu.cn/ubuntu bionic-updates main universe restricted multiverse
deb http://mirrors.zju.edu.cn/ubuntu bionic-backports main universe restricted multiverse
deb-src http://mirrors.zju.edu.cn/ubuntu bionic main universe restricted multiverse
deb-src http://mirrors.zju.edu.cn/ubuntu bionic-security main universe restricted multiverse
deb-src http://mirrors.zju.edu.cn/ubuntu bionic-updates main universe restricted multiverse
deb-src http://mirrors.zju.edu.cn/ubuntu bionic-backports main universe restricted multiverse

run command:
curl https://dl.zjuqsc.com/linux/qsc.public.key | sudo apt-key add -
curl https://dl.zjuqsc.com/linux/debian/qsc.list | sudo tee /etc/apt/sources.list.d/qsc.list
sudo apt-get update
sudo apt-get install zjunet

#include

using namespace std;

#define int long long

const int N=1e6+1e3+7;

struct Matrix{

int a[3][3];

void init()

{

for(int i=0;i<3;i++)

a[i][i]=1;

}

void clear()

{

for(int i=0;i<3;i++)

for(int j=0;j<3;j++)

a[i][j]=0;

}

};

Matrix operator +(const Matrix &A,const Matrix &B)

{

Matrix ret;

ret.clear();

for(int i=0;i<3;i++)

for(int j=0;j<3;j++)

ret.a[i][j]=A.a[i][j]+B.a[i][j];

return ret;

}

Matrix operator *(const Matrix &A,const Matrix &B)

{

Matrix ret;

ret.clear();

for(int i=0;i<3;i++)

for(int j=0;j<3;j++)

for(int k=0;k<3;k++)

ret.a[i][j]=(ret.a[i][j]+A.a[i][k]*B.a[k][j]);

return ret;

}

struct T{

int l,r,ls,rs;

int tf;

Matrix tag,val;

}t[N*2+1];

void update(int x)

{

t[x].val=t[t[x].ls].val+t[t[x].rs].val;

}

void add(int x,const Matrix &v)

{

t[x].val=t[x].val*v;

t[x].tag=t[x].tag*v;

}

void pushdown(int x)

{

add(t[x].ls,t[x].tag);

add(t[x].rs,t[x].tag);

for(int i=0;i<3;i++)

for(int j=0;j<3;j++)

t[x].tag.a[i][j]=(i==j);

}

int cnt;

int dc,rev[N];

Matrix w[N];

int build(int l,int r)

{

int x=++cnt;

t[x].l=l,t[x].r=r;

t[x].tag.clear();

t[x].tag.init();

if(l==r)

{

t[x].val=w[rev[l]];

return x;

}

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

t[x].ls=build(l,mid);

t[x].rs=build(mid+1,r);

update(x);

return x;

}

void change(int x,int l,int r,const Matrix &v)

{

if(l<=t[x].l&&t[x].r<=r)

{

add(x,v);

return;

}

pushdown(x);

int mid=(t[x].l+t[x].r)>>1;

if(l<=mid)

change(t[x].ls,l,r,v);

if(r>mid)

change(t[x].rs,l,r,v);

update(x);

}

Matrix query(int x,int l,int r)

{

if(l<=t[x].l&&t[x].r<=r)

return t[x].val;

pushdown(x);

int mid=(t[x].l+t[x].r)>>1;

Matrix ret;

ret.clear();

if(l<=mid)

ret=ret+query(t[x].ls,l,r);

if(r>mid)

ret=ret+query(t[x].rs,l,r);

return ret;

}

int n,Q;

int st[N],ed[N],top[N],sz[N],son[N],fa[N],dep[N];

vectorg[N],X[N],Y[N],Z[N];

void dfs1(int x)

{

sz[x]=1;

for(int i=0;i

{

int v=g[x][i];

if(v==fa[x])

continue;

dep[v]=dep[x]+1;

fa[v]=x;

dfs1(v);

w[v].a[0][0]=X[x][i];

w[v].a[0][1]=Y[x][i];

w[v].a[0][2]=Z[x][i];

sz[x]+=sz[v];

if(sz[v]>sz[son[x]])

son[x]=v;

}

}

void dfs2(int x)

{

st[x]=ed[x]=++dc;

rev[dc]=x;

if(!son[x])

return;

top[son[x]]=top[x];

dfs2(son[x]);

for(auto v:g[x])

{

if(v==fa[x]||v==son[x])

continue;

top[v]=v;

dfs2(v);

}

ed[x]=dc;

}

char op[11];

int getpos(char ch)

{

if(ch=='x')

return 0;

if(ch=='y')

return 1;

return 2;

}

Matrix mod;

Matrix qa,qb;

long double qry(int x,int y)

{

qa.clear(),qb.clear();

while(top[x]!=top[y])

{

if(dep[top[x]]>dep[top[y]])

{

qa=qa+query(1,st[top[x]],st[x]);

x=fa[top[x]];

}

else

{

qb=qb+query(1,st[top[y]],st[y]);

y=fa[top[y]];

}

}

if(dep[x]>dep[y])

qa=qa+query(1,st[y]+1,st[x]);

else if(dep[y]>dep[x])

qb=qb+query(1,st[x]+1,st[y]);

long double X=0,Y=0,Z=0;

X=qa.a[0][0]-qb.a[0][0];

Y=qa.a[0][1]-qb.a[0][1];

Z=qa.a[0][2]-qb.a[0][2];

return sqrt(X*X+Y*Y+Z*Z);

}

signed main()

{

scanf("%lld%lld",&n,&Q);

for(int i=1;i

{

int u,v,w;

scanf("%lld%lld%lld",&u,&v,&w);

scanf("%s",op);

int id=getpos(op[0]);

int f=op[1]=='+'?1:-1;

int dlt[3]={0,0,0};

dlt[id]+=f*w;

g[u].push_back(v);

X[u].push_back(dlt[0]);

Y[u].push_back(dlt[1]);

Z[u].push_back(dlt[2]);

g[v].push_back(u);

X[v].push_back(-dlt[0]);

Y[v].push_back(-dlt[1]);

Z[v].push_back(-dlt[2]);

}

dfs1(1);

top[1]=1;

dfs2(1);

build(1,n);

while(Q--)

{

int cop;

scanf("%lld",&cop);

if(cop==1)

{

int x,y,d;

scanf("%lld%lld%s%lld",&x,&y,op,&d);

int pos=getpos(op[0]);

int flag=0;

if(y==fa[x])

{

d=360-d;

swap(x,y);

flag=1;

}

if(d==180)

{

mod.clear();

for(int i=0;i<3;i++)

mod.a[i][i]=(i==pos?1:-1);

if(st[y]+flag<=ed[y])

change(1,st[y]+flag,ed[y],mod);

}

else

{

int p1,p2;

if(pos==0)

p1=1,p2=2;

else if(pos==1)

p1=2,p2=0;

else

p1=0,p2=1;

mod.clear();

mod.a[pos][pos]=1;

if(d==90)

{

mod.a[p1][p2]=1;

mod.a[p2][p1]=-1;

}

else

{

mod.a[p2][p1]=1;

mod.a[p1][p2]=-1;

}

if(st[y]+flag<=ed[y])

change(1,st[y]+flag,ed[y],mod);

}

}

else

{

int x,y;

scanf("%lld%lld",&x,&y);

printf("%.15Lf\n",qry(x,y));

}

}

}

请将/etc/apt/sources.list替换为下述内容:

deb http://mirrors.zju.edu.cn/ubuntu bionic main universe restricted multiverse

deb http://mirrors.zju.edu.cn/ubuntu bionic-security main universe restricted multiverse

deb http://mirrors.zju.edu.cn/ubuntu bionic-updates main universe restricted multiverse

deb http://mirrors.zju.edu.cn/ubuntu bionic-backports main universe restricted multiverse

deb-src http://mirrors.zju.edu.cn/ubuntu bionic main universe restricted multiverse

deb-src http://mirrors.zju.edu.cn/ubuntu bionic-security main universe restricted multiverse

deb-src http://mirrors.zju.edu.cn/ubuntu bionic-updates main universe restricted multiverse

deb-src http://mirrors.zju.edu.cn/ubuntu bionic-backports main universe restricted multiverse

run command:

curl https://dl.zjuqsc.com/linux/qsc.public.key | sudo apt-key add -

curl https://dl.zjuqsc.com/linux/debian/qsc.list | sudo tee /etc/apt/sources.list.d/qsc.list

sudo apt-get update

sudo apt-get install zjunet