救救被卡常的孩子

liuyifan @ 2019-04-21 14:37:49

#include<bits/stdc++.h>
#define reg register
#define ll long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
ll ans,bj[100005],qpow[20]={1},n,m,Q,cnt,top,block,blocknum,v[100005],w[100005],C[100005],pre[100005],f[100005][17],h[100005],q[100005],d[100005],belong[100005],dfn[100005],num[100005];
bool vis[100005];
template<class T>void read(T &x)
{
    x=0;reg int f=0;reg char ch=getchar();
    while(ch<'0'||ch>'9')  {f|=(ch=='-');ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
}
struct edge
{
    int to,next;
}e[200005];
struct query
{
    int x,y,t,id;
    inline bool operator<(const query &b)const
    {
        if(belong[x]==belong[b.x]&&belong[y]==belong[b.y])return t<b.t;
        else if(belong[x]==belong[b.x])return belong[y]<belong[b.y];
        else return belong[x]<belong[b.x];
    }
}b[100005];
struct change
{
    int x,y,t,pre;
}c[100005];
inline void add(reg int u,reg int v)
{
    e[++cnt].to=v;
    e[cnt].next=h[u];
    h[u]=cnt;
}
int dfs(reg int x)
{
    reg int size=0;
    dfn[x]=1;
    for(reg int i=1;i<=16;++i)
    {
        if(d[x]>=qpow[i])f[x][i]=f[f[x][i-1]][i-1];
        else break;
    }
    for(reg int i=h[x];i;i=e[i].next)
    if(e[i].to!=f[x][0])
    {
        d[e[i].to]=d[x]+1;
        f[e[i].to][0]=x;
        size+=dfs(e[i].to);
        if(size>=block)
        {
            blocknum++;
            for(int k=1;k<=size;k++)belong[q[top--]]=blocknum;
            size=0;
        }
    }
    q[++top]=x;
    return size+1;
}
inline int lca(reg int x,reg int y)
{
    if(d[x]<d[y])swap(x,y);
    int t=d[x]-d[y];
    for(reg int i=0;qpow[i]<=t;++i)
    if(qpow[i]&t)x=f[x][i];
    for(reg int i=16;i>=0;--i)
    if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    if(x==y)return x;
    return f[x][0];
}
inline void st(reg int x)
{
    if(vis[x])ans-=w[num[C[x]]]*v[C[x]],num[C[x]]--;
    else num[C[x]]++,ans+=w[num[C[x]]]*v[C[x]];
    vis[x]^=1;
}
inline void change(reg int x,reg int y)
{
    if(vis[x])
    {
        st(x);
        C[x]=y;
        st(x);
    }
    else C[x]=y;
}
inline void getans(reg int x,reg int y)
{
    while(x^y)
    {
        if(d[x]>d[y])st(x),x=f[x][0];
        else st(y),y=f[y][0];
    }
}
int main()
{
    for(reg int i=1;i<20;++i)qpow[i]=qpow[i-1]<<1;
    read(n);read(m);read(Q);
    block=pow(n,0.66666666);
    for(reg int i=1;i<=m;++i)read(v[i]);
    for(reg int i=1;i<=n;++i)read(w[i]);
    for(reg int i=1;i<n;++i)
    {
        reg int u,v;
        read(u);
        read(v);
        add(u,v);
        add(v,u);
    }
    for(reg int i=1;i<=n;++i)
    {
        read(pre[i]);
        C[i]=pre[i];
    }
    dfs(1);
    while(top)belong[q[top--]]=blocknum;
    reg int c1=0,c2=0;
    for(int i=1;i<=Q;++i)
    {
        reg int op,x,y;
        read(op);
        read(x);
        read(y);
        if(!op)
        {
            c1++;
            c[c1].x=x;c[c1].y=y;c[c1].pre=pre[x];pre[x]=y;
        }
        else 
        {
            c2++;
            if(dfn[x]>dfn[y])swap(x,y);
            b[c2].x=x;b[c2].y=y;b[c2].id=c2;b[c2].t=c1;
        }
    }
    sort(b+1,b+c2+1);
    for(reg int i=1;i<=b[1].t;++i)change(c[i].x,c[i].y);
    getans(b[1].x,b[1].y);
    int t=lca(b[1].x,b[1].y);
    st(t);
    bj[b[1].id]=ans;
    st(t);
    for(reg int i=2;i<=c2;++i)
    {
        for(reg int j=b[i-1].t+1;j<=b[i].t;++j)change(c[j].x,c[j].y);
        for(reg int j=b[i-1].t;j>b[i].t;--j)change(c[j].x,c[j].pre);
        getans(b[i-1].x,b[i].x);
        getans(b[i-1].y,b[i].y);
        reg int t=lca(b[i].x,b[i].y);
        st(t);
        bj[b[i].id]=ans;
        st(t);
    }
    for(reg int i=1;i<=c2;i++)printf("%lld\n",bj[i]);
    return 0;
}

by NaCly_Fish @ 2019-04-21 14:38:50

改用树剖，就不卡常了

by NaCly_Fish @ 2019-04-21 14:39:14

@liuyifan

by liuyifan @ 2019-04-21 14:41:58

@NaCly_Fish 我刚刚已经过了 将int全部换成long long

by liuyifan @ 2019-04-21 14:42:16

@NaCly_Fish 据说强转很慢 是真的吗

by NaCly_Fish @ 2019-04-21 14:50:42

@liuyifan 全用long long才慢，强转常数小大约一半

by liuyifan @ 2019-04-21 14:52:52

@NaCly_Fish 但我改了就AC了

#include<bits/stdc++.h>
#define reg register
#define ll long long
#pragma GCC optimize("Ofast","inline","-ffast-math")
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
using namespace std;
ll ans,bj[100005],qpow[20]={1},n,m,Q,cnt,top,block,blocknum,v[100005],w[100005],C[100005],pre[100005],f[100005][17],h[100005],q[100005],d[100005],belong[100005],dfn[100005],num[100005];
bool vis[100005];
template<class T>void read(T &x)
{
    x=0;reg ll f=0;reg char ch=getchar();
    while(ch<'0'||ch>'9')  {f|=(ch=='-');ch=getchar();}
    while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
    x=f?-x:x;
}
struct edge
{
    ll to,next;
}e[200005];
struct query
{
    ll x,y,t,id;
    inline bool operator<(const query &b)const
    {
        if(belong[x]==belong[b.x]&&belong[y]==belong[b.y])return t<b.t;
        else if(belong[x]==belong[b.x])return belong[y]<belong[b.y];
        else return belong[x]<belong[b.x];
    }
}b[100005];
struct change
{
    ll x,y,t,pre;
}c[100005];
inline void add(reg ll u,reg ll v)
{
    e[++cnt].to=v;
    e[cnt].next=h[u];
    h[u]=cnt;
}
ll dfs(reg ll x)
{
    reg ll size=0;
    dfn[x]=1;
    for(reg ll i=1;i<=16;++i)
    {
        if(d[x]>=qpow[i])f[x][i]=f[f[x][i-1]][i-1];
        else break;
    }
    for(reg ll i=h[x];i;i=e[i].next)
    if(e[i].to!=f[x][0])
    {
        d[e[i].to]=d[x]+1;
        f[e[i].to][0]=x;
        size+=dfs(e[i].to);
        if(size>=block)
        {
            blocknum++;
            for(ll k=1;k<=size;k++)belong[q[top--]]=blocknum;
            size=0;
        }
    }
    q[++top]=x;
    return size+1;
}
inline ll lca(reg ll x,reg ll y)
{
    if(d[x]<d[y])swap(x,y);
    ll t=d[x]-d[y];
    for(reg ll i=0;qpow[i]<=t;++i)
    if(qpow[i]&t)x=f[x][i];
    for(reg ll i=16;i>=0;--i)
    if(f[x][i]!=f[y][i])x=f[x][i],y=f[y][i];
    if(x==y)return x;
    return f[x][0];
}
inline void st(reg ll x)
{
    if(vis[x])ans-=w[num[C[x]]]*v[C[x]],num[C[x]]--;
    else num[C[x]]++,ans+=w[num[C[x]]]*v[C[x]];
    vis[x]^=1;
}
inline void change(reg ll x,reg ll y)
{
    if(vis[x])
    {
        st(x);
        C[x]=y;
        st(x);
    }
    else C[x]=y;
}
inline void getans(reg ll x,reg ll y)
{
    while(x^y)
    {
        if(d[x]>d[y])st(x),x=f[x][0];
        else st(y),y=f[y][0];
    }
}
int main()
{
    for(reg ll i=1;i<20;++i)qpow[i]=qpow[i-1]<<1;
    read(n);read(m);read(Q);
    block=pow(n,0.66666666);
    for(reg ll i=1;i<=m;++i)read(v[i]);
    for(reg ll i=1;i<=n;++i)read(w[i]);
    for(reg ll i=1;i<n;++i)
    {
        reg ll u,v;
        read(u);
        read(v);
        add(u,v);
        add(v,u);
    }
    for(reg ll i=1;i<=n;++i)
    {
        read(pre[i]);
        C[i]=pre[i];
    }
    dfs(1);
    while(top)belong[q[top--]]=blocknum;
    reg ll c1=0,c2=0;
    for(ll i=1;i<=Q;++i)
    {
        reg ll op,x,y;
        read(op);
        read(x);
        read(y);
        if(!op)
        {
            c1++;
            c[c1].x=x;c[c1].y=y;c[c1].pre=pre[x];pre[x]=y;
        }
        else 
        {
            c2++;
            if(dfn[x]>dfn[y])swap(x,y);
            b[c2].x=x;b[c2].y=y;b[c2].id=c2;b[c2].t=c1;
        }
    }
    sort(b+1,b+c2+1);
    for(reg ll i=1;i<=b[1].t;++i)change(c[i].x,c[i].y);
    getans(b[1].x,b[1].y);
    ll t=lca(b[1].x,b[1].y);
    st(t);
    bj[b[1].id]=ans;
    st(t);
    for(reg ll i=2;i<=c2;++i)
    {
        for(reg ll j=b[i-1].t+1;j<=b[i].t;++j)change(c[j].x,c[j].y);
        for(reg ll j=b[i-1].t;j>b[i].t;--j)change(c[j].x,c[j].pre);
        getans(b[i-1].x,b[i].x);
        getans(b[i-1].y,b[i].y);
        reg ll t=lca(b[i].x,b[i].y);
        st(t);
        bj[b[i].id]=ans;
        st(t);
    }
    for(reg ll i=1;i<=c2;i++)printf("%lld\n",bj[i]);
    return 0;
}

这是改后的

by zzw4257 @ 2020-01-27 12:17:01

捕捉我们OJ的水题贡献之神