性感蒟蒻,在线求助

回复帖子

@一梦南柯 2019-07-12 09:58 回复

被标题吸引进来了吧

RT

这是一个历经 三三得五 天千锤百炼而成的优质代码

(然鹅连样例都过不得)

只要998AC就可以把它抱回家

qwq不扯了

求助啊,板子都过不得,有没有天理了啊

顺便 洛天依生快

#include<bits/stdc++.h>
using namespace std;
const int qwe=5e5+10;
#define mid ((l+r)>>1)
long long n2,m2,r,mod,son[qwe],head[qwe],size[qwe],id[qwe],v[qwe];
long long op,x2,y2,z2,dep[qwe],sum[qwe],lazy[qwe],fa[qwe],cnt,tot,top[qwe];
struct node
{
    int l,n,w;
}e[qwe];
inline int read()
{
    int x=0,f=1;
    char ch=getchar();
    while(ch<'0'||ch>'9')
    {
        if(ch=='-') f=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        x=(x<<3)+(x<<1)+ch-'0';
        ch=getchar();
    }
    return x*f;
}

//----------------------------------------------------

void build(int rt,int l,int r)
{
    if(l==r)
    {
        sum[rt]=v[l];
        sum[rt]%=mod;
        return;
    }
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    sum[rt]=sum[rt<<1]+sum[rt<<1|1];
    return;
}

void push(int rt,int l,int r)
{
    lazy[rt<<1]+=lazy[rt];
    lazy[rt<<1]%=mod;

    lazy[rt<<1|1]+=lazy[rt];
    lazy[rt<<1|1]%=mod;

    sum[rt<<1]+=lazy[rt]*(mid-l+1);
    sum[rt<<1]%=mod;

    sum[rt<<1|1]+=lazy[rt]*(r-mid);
    sum[rt<<1|1]%=mod;
    lazy[rt]=0;
    return;
}

int query(int rt,int l,int r,int left,int right)
{
    if(left<=l&&r<=right) return sum[rt]%mod;
    if(l>right||r<left) return 0;
    if(lazy[rt]) push(rt,l,r);
    long long a=0,b=0;
    if(mid>=left) a=query(rt,l<<1,mid,left,right);
    if(mid<right) b=query(rt<<1|1,mid+1,r,left,right);
    return (a%mod+b%mod)%mod;
}

void update(int rt,int l,int r,int left,int right,long long v)
{
    if(left<=l&&r<=right) 
    {
        sum[rt]+=v*(r-l+1);
        sum[rt]%=mod;
        lazy[rt]+=v;
        lazy[rt]%=mod;
        return;
    }
    if(l>right||r<left) return;
    if(lazy[rt]) push(rt,l,r);
    if(mid>=left) update(rt<<1,l,mid,left,right,v);
    if(mid<right) update(rt<<1|1,mid+1,r,left,right,v);
    return;
}

//---------------------------------------------

int add(int x,int y)//链式前向星加边
{
    e[++tot].l=y;
    e[tot].n=head[x];
    head[x]=tot;
}

inline void dfs1(int x,int f,int depth)
{
    dep[x]=depth;
    fa[x]=f;
    size[x]=1;
    int maxson=-1;
    for(int i=head[x];i;i=e[i].n)
    {
        int q=e[i].l;
        if(q==f) continue;
        dfs1(q,x,depth+1);
        size[x]+=size[q];
        if(size[q]>maxson)
        {
            maxson=size[q];
            son[x]=q;
        }
    }
    return;
}

inline void dfs2(int x,int topx)
{
    id[x]=++cnt;
    v[cnt]=e[x].w;
    top[x]=topx;
    if(!son[x]) return;
    dfs2(son[x],topx);
    for(int i=head[x];i;i=e[i].n)
    {
        int y=e[i].l;
        if(y==fa[x]||y==son[x]) continue;
        dfs2(y,y);
    }
    return;
}

long long roadsum(int m,int n)
{
    long long maxn=0;
    int tm=top[m];
    int tn=top[n];
    while(tm!=tn)
    {
        if(dep[tm]<dep[tn]) swap(n,m),swap(tn,tm);
        maxn+=query(1,1,cnt,id[tm],id[m]);
        m=fa[tm];
        tm=top[m];
    }
    if(id[m]>id[n]) swap(m,n);
    maxn+=query(1,1,cnt,id[m],id[n]);
    return maxn%mod;
}

void roadadd(int m,int n,int val)
{
    int tm=top[m],tn=top[n];
    while(tm!=tn)
    {
        if(dep[tm]<dep[tn]) swap(m,n),swap(tm,tn);
        update(1,1,cnt,id[tm],id[m],val);
        m=fa[tm],tm=top[m];
    }
    if(id[m]>id[n]) swap(m,n);
    update(1,1,cnt,id[m],id[n],val);
}

//-------------------------------------------------------------------------------------------------------

int main()
{
    n2=read(),m2=read(),r=read(),mod=read();
    for(int i=1;i<=n2;i++)
    {
        cin>>e[i].w;
        e[i].w%=mod;
    }
    for(int i=1;i<=n2-1;i++)
    {
        int a,b;
        a=read();
        b=read();
        add(a,b);
        add(b,a);
    }
    fa[r]=1;
    dep[r]=1;
    dfs1(r,0,1);
    dfs2(r,r);
    build(1,1,n2);
    for(int i=1; i<=m2; i++)
    {
        op=read(),x2=read();//写到一半发现变量名重了于是都加了2
        if(op==1)
        {
            y2=read(),z2=read();
            roadadd(x2,y2,z2%mod);
        }
        if(op==2)
        {
            y2=read();
            cout<<roadsum(x2,y2)%mod<<endl;
        }
        if(op==3)
        {
            z2=read();
            update(1,1,n2,id[x2],id[x2]+size[x2]-1,z2%mod);
        }
        if(op==4)
        {
            cout<<query(1,1,n2,id[x2],id[x2]+size[x2]-1)%mod<<endl;
        }
    }
    return 0;
}

220行,海星

反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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