我又炸了wa+mle+re,已疯

回复帖子

@李一阳 2019-04-23 21:31 回复
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=2000005; 
int n,m,x,y,c,to[maxn],nxt[maxn],head[maxn],top[maxn],dep[maxn],f[maxn],siz[maxn],son[maxn],ap[maxn];
int id[maxn],w[maxn],lm=9999999,rm=-99999,lmp=-2,rmp=-2;
int tr[maxn*4],trl[maxn*4],trr[maxn*4],laz[maxn*4],tot,cnt;
char pl;
int read()
{
    char z=getchar();int x=0,y=1;
    while(z<'0'||z>'9'){if(z=='-')y=-1;z=getchar();}
    while(z>='0'&&z<+'9'){x=x*10+z-'0';z=getchar();}
    return x*y;
}
void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
//
void update(int root)
{
    laz[root*2]=laz[root*2+1]=trl[root*2]=trl[root*2+1]=trr[root*2]=trr[root*2+1]=laz[root];
    tr[root*2]=1;tr[root*2+1]=1;
    laz[root]=-1;
    return;
}
void build(int root,int l,int r)
{
    if(l==r)
    {
        tr[root]=1;trl[root]=w[l];trr[root]=w[l];
        return;
    }
    int mid=(l+r)>>1;
    build(root*2,l,mid);build(root*2+1,mid+1,r);
    tr[root]=tr[root*2]+tr[root*2+1];
    trl[root]=trl[root*2];trr[root]=trr[root*2+1];
    if(trr[root*2]==trl[root*2+1])tr[root]--;
}
void add(int root,int l,int r,int s,int t,int k)
{
    if(r<s||l>t)return;
    if(l>=s&&r<=t)
    {
        trl[root]=k;trr[root]=k;tr[root]=1;
        laz[root]=k;return;
    }
    if(laz[root]!=-1)update(root);
    int mid=(l+r)/2;
    add(root*2,l,mid,s,t,k);add(root*2+1,mid+1,r,s,t,k);
    tr[root]=tr[root*2]+tr[root*2+1];
    trl[root]=trl[root*2];trr[root]=trr[root*2+1];
    if(trr[root*2]==trl[root*2+1])tr[root]--;
}
int find(int root,int l,int r,int s,int t)
{
    if(r<s||l>t)return 0;
    if(l>=s&&r<=t)
    {
        if(l<lm)lm=l,lmp=trl[root];
        if(r>rm)rm=r,rmp=trr[root];
        return tr[root];
    }
    int mid=(l+r)/2;
    return find(root*2,l,mid,s,t)+find(root*2+1,mid+1,r,s,t);
}
void findl(int root,int l,int r,int s,int t)
{
    if(r<s||l>t)return;
    if(l>=s&&r<=t)return;
    if(laz[root]!=-1)update(root);
    int mid=(l+r)/2;
    findl(root*2,l,mid,s,t);findl(root*2+1,mid+1,r,s,t);
    tr[root]=tr[root*2]+tr[root*2+1];
    trl[root]=trl[root*2];trr[root]=trr[root*2+1];
    if(trr[root*2]==trl[root*2+1])tr[root]--;
}
//
void dfs1(int x,int deep)
{
    siz[x]=1;
    dep[x]=deep;int y=-1;
    for(int i=head[x];i;i=nxt[i])
    {
        int g=to[i];
        if(g==f[x])continue;
        f[g]=x;
        dfs1(g,deep+1);
        siz[x]+=siz[g];
        if(siz[g]>y)
        {
            y=siz[g];son[x]=g;
        }
    }
}
void dfs2(int x,int topf)
{
    top[x]=topf;
    id[x]=++cnt;
    w[cnt]=ap[x];
    if(!son[x])return;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=nxt[i])
    {
        int g=to[i];
        if(g==son[x]||g==f[x])continue;
        dfs2(g,g);
    }
}
//
void clean()
{
    lm=9999999;rm=-9999;lmp=-2;rmp=-2;return;
}
void cg(int x,int y,int k)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        add(1,1,n,id[top[x]],id[x],k);
        x=f[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    add(1,1,n,id[x],id[y],k);
}
int ask(int x,int y)
{
    int ans=0,ans1=-1,ans2=-1;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y),swap(ans1,ans2);
        findl(1,1,n,id[top[x]],id[x]);
        ans+=find(1,1,n,id[top[x]],id[x]);
        if(ans1==rmp)ans--;
        x=f[top[x]];ans1=lmp;
        clean();
    }
    if(dep[x]>dep[y])swap(x,y),swap(ans1,ans2);
    findl(1,1,n,id[x],id[y]);
    ans+=find(1,1,n,id[x],id[y]);
    if(ans1==lmp)ans--;if(ans2==rmp)ans--;
    clean();
    return ans;
}
int main()
{
    memset(laz,-1,sizeof(laz));
    n=read();m=read();
    for(int i=1;i<=n;i++)ap[i]=read();
    for(int i=1;i<=n-1;i++)
    {
        x=read();y=read();
        add(x,y);add(y,x);
    }
    dfs1(1,1);dfs2(1,1);
    build(1,1,n);
    while(m--)
    {
        cin>>pl;
        if(pl=='C')
        {
            x=read();y=read();c=read();
            cg(x,y,c);
        }
        else
        {
            x=read();y=read();
            cout<<ask(x,y)<<endl;
        }
    }
    return 0;
}
@李一阳 2019-04-23 21:57 回复 举报

一番更改毫无卵用```cpp

include<iostream>

include<cstring>

include<cstdio>

include<cmath>

include<queue>

include<algorithm>

using namespace std; const int maxn=100005; int n,m,x,y,c,to[maxn],nxt[maxn],head[maxn],top[maxn],dep[maxn],f[maxn],siz[maxn],son[maxn],ap[maxn]; int id[maxn],w[maxn],lmp,rmp; int tr[maxn4],trl[maxn4],trr[maxn4],laz[maxn4],tot,cnt; char pl; int read() { char z=getchar();int x=0,y=1; while(z<'0'||z>'9'){if(z=='-')y=-1;z=getchar();} while(z>='0'&&z<+'9'){x=x10+z-'0';z=getchar();} return xy; } void add(int x,int y) { to[++tot]=y; nxt[tot]=head[x]; head[x]=tot; } // void update(int root) { laz[root2]=laz[root2+1]=trl[root2]=trl[root2+1]=trr[root2]=trr[root2+1]=laz[root]; tr[root2]=1;tr[root2+1]=1; laz[root]=-1; return; } void build(int root,int l,int r) { if(l==r) { tr[root]=1;trl[root]=w[l];trr[root]=w[l]; return; } int mid=(l+r)>>1; build(root2,l,mid);build(root2+1,mid+1,r); tr[root]=tr[root2]+tr[root2+1]; trl[root]=trl[root2];trr[root]=trr[root2+1]; if(trr[root2]==trl[root2+1])tr[root]--; } void add(int root,int l,int r,int s,int t,int k) { if(r<s||l>t)return; if(l>=s&&r<=t) { trl[root]=k;trr[root]=k;tr[root]=1; laz[root]=k;return; } if(laz[root]!=-1)update(root); int mid=(l+r)/2; add(root2,l,mid,s,t,k);add(root2+1,mid+1,r,s,t,k); tr[root]=tr[root2]+tr[root2+1]; trl[root]=trl[root2];trr[root]=trr[root2+1]; if(trr[root2]==trl[root2+1])tr[root]--; } int find(int root,int l,int r,int s,int t) { if(r<s||l>t)return 0; if(l>=s&&r<=t) { if(l==s)lmp=trl[root]; if(r==t)rmp=trr[root]; return tr[root]; } int mid=(l+r)/2; return find(root2,l,mid,s,t)+find(root2+1,mid+1,r,s,t); } void findl(int root,int l,int r,int s,int t) { if(r<s||l>t)return; if(l>=s&&r<=t)return; if(laz[root]!=-1)update(root); int mid=(l+r)/2; findl(root2,l,mid,s,t);findl(root2+1,mid+1,r,s,t); tr[root]=tr[root2]+tr[root2+1]; trl[root]=trl[root2];trr[root]=trr[root2+1]; if(trr[root2]==trl[root2+1])tr[root]--; } // void dfs1(int x,int deep) { siz[x]=1; dep[x]=deep;int y=-1; for(int i=head[x];i;i=nxt[i]) { int g=to[i]; if(g==f[x])continue; f[g]=x; dfs1(g,deep+1); siz[x]+=siz[g]; if(siz[g]>y) { y=siz[g];son[x]=g; } } } void dfs2(int x,int topf) { top[x]=topf; id[x]=++cnt; w[cnt]=ap[x]; if(!son[x])return; dfs2(son[x],topf); for(int i=head[x];i;i=nxt[i]) { int g=to[i]; if(g==son[x]||g==f[x])continue; dfs2(g,g); } } // void cg(int x,int y,int k) { while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y); add(1,1,n,id[top[x]],id[x],k); x=f[top[x]]; } if(dep[x]>dep[y])swap(x,y); add(1,1,n,id[x],id[y],k); } int ask(int x,int y) { int ans=0,ans1=-1,ans2=-1; while(top[x]!=top[y]) { if(dep[top[x]]<dep[top[y]])swap(x,y),swap(ans1,ans2); findl(1,1,n,id[top[x]],id[x]); ans+=find(1,1,n,id[top[x]],id[x]); if(ans1==rmp)ans--; x=f[top[x]];ans1=lmp; } if(dep[x]>dep[y])swap(x,y),swap(ans1,ans2); findl(1,1,n,id[x],id[y]); ans+=find(1,1,n,id[x],id[y]);

if(ans1==lmp)ans--;if(ans2==rmp)ans--;
return ans;

} int main() { memset(laz,-1,sizeof(laz)); n=read();m=read(); for(int i=1;i<=n;i++)ap[i]=read(); for(int i=1;i<=n-1;i++) { x=read();y=read(); add(x,y);add(y,x); } dfs1(1,1);dfs2(1,1); build(1,1,n); while(m--) { cin>>pl; if(pl=='C') { x=read();y=read();c=read(); cg(x,y,c); } else { x=read();y=read(); cout<<ask(x,y)<<endl; } } return 0; }

@李一阳 2019-04-23 21:58 回复 举报
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#include<queue>
#include<algorithm>
using namespace std;
const int maxn=100005; 
int n,m,x,y,c,to[maxn],nxt[maxn],head[maxn],top[maxn],dep[maxn],f[maxn],siz[maxn],son[maxn],ap[maxn];
int id[maxn],w[maxn],lmp,rmp;
int tr[maxn*4],trl[maxn*4],trr[maxn*4],laz[maxn*4],tot,cnt;
char pl;
int read()
{
    char z=getchar();int x=0,y=1;
    while(z<'0'||z>'9'){if(z=='-')y=-1;z=getchar();}
    while(z>='0'&&z<+'9'){x=x*10+z-'0';z=getchar();}
    return x*y;
}
void add(int x,int y)
{
    to[++tot]=y;
    nxt[tot]=head[x];
    head[x]=tot;
}
//
void update(int root)
{
    laz[root*2]=laz[root*2+1]=trl[root*2]=trl[root*2+1]=trr[root*2]=trr[root*2+1]=laz[root];
    tr[root*2]=1;tr[root*2+1]=1;
    laz[root]=-1;
    return;
}
void build(int root,int l,int r)
{
    if(l==r)
    {
        tr[root]=1;trl[root]=w[l];trr[root]=w[l];
        return;
    }
    int mid=(l+r)>>1;
    build(root*2,l,mid);build(root*2+1,mid+1,r);
    tr[root]=tr[root*2]+tr[root*2+1];
    trl[root]=trl[root*2];trr[root]=trr[root*2+1];
    if(trr[root*2]==trl[root*2+1])tr[root]--;
}
void add(int root,int l,int r,int s,int t,int k)
{
    if(r<s||l>t)return;
    if(l>=s&&r<=t)
    {
        trl[root]=k;trr[root]=k;tr[root]=1;
        laz[root]=k;return;
    }
    if(laz[root]!=-1)update(root);
    int mid=(l+r)/2;
    add(root*2,l,mid,s,t,k);add(root*2+1,mid+1,r,s,t,k);
    tr[root]=tr[root*2]+tr[root*2+1];
    trl[root]=trl[root*2];trr[root]=trr[root*2+1];
    if(trr[root*2]==trl[root*2+1])tr[root]--;
}
int find(int root,int l,int r,int s,int t)
{
    if(r<s||l>t)return 0;
    if(l>=s&&r<=t)
    {
        if(l==s)lmp=trl[root];
        if(r==t)rmp=trr[root];
        return tr[root];
    }
    int mid=(l+r)/2;
    return find(root*2,l,mid,s,t)+find(root*2+1,mid+1,r,s,t);
}
void findl(int root,int l,int r,int s,int t)
{
    if(r<s||l>t)return;
    if(l>=s&&r<=t)return;
    if(laz[root]!=-1)update(root);
    int mid=(l+r)/2;
    findl(root*2,l,mid,s,t);findl(root*2+1,mid+1,r,s,t);
    tr[root]=tr[root*2]+tr[root*2+1];
    trl[root]=trl[root*2];trr[root]=trr[root*2+1];
    if(trr[root*2]==trl[root*2+1])tr[root]--;
}
//
void dfs1(int x,int deep)
{
    siz[x]=1;
    dep[x]=deep;int y=-1;
    for(int i=head[x];i;i=nxt[i])
    {
        int g=to[i];
        if(g==f[x])continue;
        f[g]=x;
        dfs1(g,deep+1);
        siz[x]+=siz[g];
        if(siz[g]>y)
        {
            y=siz[g];son[x]=g;
        }
    }
}
void dfs2(int x,int topf)
{
    top[x]=topf;
    id[x]=++cnt;
    w[cnt]=ap[x];
    if(!son[x])return;
    dfs2(son[x],topf);
    for(int i=head[x];i;i=nxt[i])
    {
        int g=to[i];
        if(g==son[x]||g==f[x])continue;
        dfs2(g,g);
    }
}
//
void cg(int x,int y,int k)
{
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y);
        add(1,1,n,id[top[x]],id[x],k);
        x=f[top[x]];
    }
    if(dep[x]>dep[y])swap(x,y);
    add(1,1,n,id[x],id[y],k);
}
int ask(int x,int y)
{
    int ans=0,ans1=-1,ans2=-1;
    while(top[x]!=top[y])
    {
        if(dep[top[x]]<dep[top[y]])swap(x,y),swap(ans1,ans2);
        findl(1,1,n,id[top[x]],id[x]);
        ans+=find(1,1,n,id[top[x]],id[x]);
        if(ans1==rmp)ans--;
        x=f[top[x]];ans1=lmp;
    }
    if(dep[x]>dep[y])swap(x,y),swap(ans1,ans2);
    findl(1,1,n,id[x],id[y]);
    ans+=find(1,1,n,id[x],id[y]);

    if(ans1==lmp)ans--;if(ans2==rmp)ans--;
    return ans;
}
int main()
{
    memset(laz,-1,sizeof(laz));
    n=read();m=read();
    for(int i=1;i<=n;i++)ap[i]=read();
    for(int i=1;i<=n-1;i++)
    {
        x=read();y=read();
        add(x,y);add(y,x);
    }
    dfs1(1,1);dfs2(1,1);
    build(1,1,n);
    while(m--)
    {
        cin>>pl;
        if(pl=='C')
        {
            x=read();y=read();c=read();
            cg(x,y,c);
        }
        else
        {
            x=read();y=read();
            cout<<ask(x,y)<<endl;
        }
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



请具体说明理由,以增加反馈的可信度。