本地卡死，测评机编译失败求助

LoveFrieren @ 2024-08-20 19:46:25

#include<bits/stdc++.h>
using namespace std;
const int M = 1e5 + 10; typedef long long ll;
int n, m, r, p, cnt, wson[M], vl[M], sz[M], fa[M], dfn[M], rdfn[M], top[M], d[M];
ll sgt[M * 4];
vector<int> tr[M];
ll read(){
    int f = 1, a = 0;
    char c = getchar();
    while(c < '0' || c > '9'){
        if (c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        a = (a << 1) + (a << 3) + (c ^ 48);
        c = getchar();
    }
    return f * a;
}
dfs1(int u, int f){//求父节点， 重儿子
    fa[u] = f;
    sz[u] = 1;
    for(int i = 0; i < tr[u].size(); ++i){
        int v = tr[u][i];
        if(v == f) continue;
        d[v] = d[u] + 1;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[wson[u]]) wson[u] = v; 
    }
}
dfs2(int u, int topp){//求重链顶，dfs序
    dfn[u] = ++cnt;
    rdfn[cnt] = u;
    top[u] = topp;
    if(wson[u] != 0){
        dfs2(wson[u], topp);
        for(int i = 0; i < tr[u].size(); ++i)
            dfs2(tr[u][i], tr[u][i]);
    }
}
ll lzt[M * 4];//线段树，因为看过MLE的案例所以没写结构体，见谅
void pushup(int u){sgt[u] = sgt[u * 2] + sgt[u * 2 + 1] % p;}
void build(int u, int L, int R){
    if(L == R){
        sgt[u] = vl[rdfn[L]];
        return;
    }
    int mid = L + (R - L >> 1);
    build(u * 2, L, mid), build(u * 2 + 1, mid + 1, R);
    pushup(u);
}
void maketag(int u, int len, int vai){
    vl[u] += vai * len % p;
    lzt[u] += vai % p;
    lzt[u] %= p, vl[u] %= p;
}
void pushdown(int u, int L, int R){
    int mid = L + (R - L >> 1);
    maketag(u * 2, mid - L + 1, lzt[u]);
    maketag(u * 2 + 1, R - mid, lzt[u]);
    lzt[u] = 0;
}
void update(int u, int L, int R, int l, int r, int vai){
    if(l <= L && R <= r){
        maketag(u, R - L + 1, vai);
    }
    else if(!(r < L || R < l)){
        int mid = L + (R - L >> 1);
        pushdown(u, L, R);
        update(u * 2, L, mid, l, r, vai);
        update(u * 2 + 1, mid + 1, R, l, r, vai);
        pushup(u);
    }
}
ll query(int u, int L, int R, int l, int r){
    if(l <= L && R <= r)
        return sgt[u];
    else if(!(r < L || R < l)){
        int mid = L + (R - L >> 1);
        pushdown(u, L, R);
        return (query(u * 2, L, mid, l, r) + query(u * 2 + 1, mid + 1, R, l, r));
    }
    else return 0;
}
void upd(int u, int v, int vai){//题目描述上的1，2操作
    while(top[u] != top[v]){
        if(d[top[u]] < d[top[v]]) swap(u, v);
        update(1, 1, n, dfn[top[u]], dfn[u], vai);
        u = fa[top[u]];
    }
    update(1, 1, n, min(dfn[u], dfn[v]), max(dfn[u], dfn[v]), vai);
}
ll qry(int u, int v){
    ll re = 0;
    while(top[u] != top[v]){
        if(d[top[u]] < d[top[v]]) swap(u, v);
        re += query(1, 1, n, dfn[top[u]], dfn[u]) % p;
        re %= p;
        u = fa[top[u]];
    }
    re += query(1, 1, n, min(dfn[u], dfn[v]), max(dfn[u], dfn[v])) % p;
    return re % p;
}
int main(){
    n = read(), m = read(), r = read(), p = read();
    for(int i = 1; i <= n; ++i) vl[i] = read();
    for(int i = 1, u, v; i < n; ++i){
        u = read(), v = read();
        tr[u].push_back(v);
        tr[v].push_back(u);
    } 
    build(1, 1, n); ++d[r]; dfs1(r, 0); dfs2(r, 0);
    for(int i = 1, x, y, z, t; i <= m; ++i){
        t = read();
        if(t == 1){
            x = read(), y = read(), z = read();
            upd(x, y, z);
        }
        else if(t == 2){
            x = read(), y = read();
            cout << qry(x, y) << "\n";
        }
        else if (t == 3){
            x = read(), y = read();
            update(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, y);
        }
        else{
            x = read();
            cout << query(1, 1, n, dfn[x], dfn[x] + sz[x] - 1) % p << "\n";
        }
    }
    return 0;
} 

by LoveFrieren @ 2024-08-20 20:39:04

@Grammar__hbw 深进的书上这么写的（）而且改完也不行[哭]

by LoveFrieren @ 2024-08-20 20:51:47

@Grammar__hbw 再发一遍我改完的代码吧

#include<bits/stdc++.h>
using namespace std;
const int M = 1e5 + 10; typedef long long ll;
int n, m, r, p, cnt;
int wson[M], vl[M], sz[M], fa[M], dfn[M], rdfn[M], top[M], d[M];
ll sgt[M * 4];
vector<int> tr[M];
int read(){
    int f = 1, a = 0;
    char c = getchar();
    while(c < '0' || c > '9'){
        if (c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9'){
        a = (a << 1) + (a << 3) + (c ^ 48);
        c = getchar();
    }
    return f * a;
}
void dfs1(int u, int f){
    fa[u] = f;
    sz[u] = 1;
    for(int i = 0; i < tr[u].size(); ++i){
        int v = tr[u][i];
        if(v == f) continue;
        d[v] = d[u] + 1;
        dfs1(v, u);
        sz[u] += sz[v];
        if(sz[v] > sz[wson[u]]) wson[u] = v; 
    }
}
void dfs2(int u, int topp){
    dfn[u] = ++cnt;
    rdfn[cnt] = u;
    top[u] = topp;
    if(wson[u] != 0){
        dfs2(wson[u], topp);
        for(int i = 0; i < tr[u].size(); ++i){
            if(tr[u][i] == wson[u] || tr[u][i] == fa[u]) continue;
            dfs2(tr[u][i], tr[u][i]);
        }
    }
}
ll lzt[M * 4];
void pushup(int u){sgt[u] = (sgt[u * 2] + sgt[u * 2 + 1]) % p;}
void build(int u, int L, int R){
    if(L == R){
        sgt[u] = vl[rdfn[L]];
        return;
    }
    int mid = L + (R - L >> 1);
    build(u * 2, L, mid), build(u * 2 + 1, mid + 1, R);
    pushup(u);
}
void maketag(int u, int len, int vai){
    sgt[u] += (ll)vai * len % p;
    lzt[u] += vai % p;
    lzt[u] %= p, vl[u] %= p;
}
void pushdown(int u, int L, int R){
    int mid = L + (R - L >> 1);
    maketag(u * 2, mid - L + 1, lzt[u]);
    maketag(u * 2 + 1, R - mid, lzt[u]);
    lzt[u] = 0;
}
void update(int u, int L, int R, int l, int r, int vai){
    if(l <= L && R <= r){
        maketag(u, R - L + 1, vai);
    }
    else if(!(r < L || R < l)){
        int mid = L + (R - L >> 1);
        pushdown(u, L, R);
        if(l <= mid)
            update(u * 2, L, mid, l, r, vai);
        if(r > mid)
            update(u * 2 + 1, mid + 1, R, l, r, vai);
        pushup(u);
    }
}
ll query(int u, int L, int R, int l, int r){
    if(l <= L && R <= r)
        return sgt[u];
    else if(!(r < L || R < l)){
        int mid = L + (R - L >> 1);
        pushdown(u, L, R);
        return (query(u * 2, L, mid, l, r) + query(u * 2 + 1, mid + 1, R, l, r));
    }
    else return 0;
}
void upd(int u, int v, int vai){
    while(top[u] != top[v]){
        if(d[top[u]] < d[top[v]]) swap(u, v);
        update(1, 1, n, dfn[top[u]], dfn[u], vai);
        u = fa[top[u]];
    }
    update(1, 1, n, min(dfn[u], dfn[v]), max(dfn[u], dfn[v]), vai);
}
ll qry(int u, int v){
    ll re = 0;
    while(top[u] != top[v]){
        if(d[top[u]] < d[top[v]]) swap(u, v);
        re += query(1, 1, n, dfn[top[u]], dfn[u]) % p;
        re %= p;
        u = fa[top[u]];
    }
    re += query(1, 1, n, min(dfn[u], dfn[v]), max(dfn[u], dfn[v])) % p;
    return re % p;
}
int main(){
    n = read(), m = read(), r = read(), p = read();
    for(int i = 1; i <= n; ++i) vl[i] = read();
    for(int i = 1, u, v; i < n; ++i){
        u = read(), v = read();
        tr[u].push_back(v);
        tr[v].push_back(u);
    } 
    ++d[r]; dfs1(r, 0); dfs2(r, r); build(1, 1, n);
    for(int i = 1, x, y, z, t; i <= m; ++i){
        t = read();
        if(t == 1){
            x = read(), y = read(), z = read();
            upd(x, y, z);
        }
        else if(t == 2){
            x = read(), y = read();
            cout << qry(x, y) % p << "\n";
        }
        else if (t == 3){
            x = read(), y = read();
            update(1, 1, n, dfn[x], dfn[x] + sz[x] - 1, y);
        }
        else{
            x = read();
            cout << query(1, 1, n, dfn[x], dfn[x] + sz[x] - 1) % p << "\n";
        }
    }
    return 0;
} 

by LoveFrieren @ 2024-08-20 20:53:43

@Grammar__hbw 开1e6过了（）

by Grammar__hbw @ 2024-08-20 21:03:47

@ckkjz 啊这......你的线段树和懒标记开4倍了啊？？？

我不知道是什么问题了。我1e5过了：

#include <bits/stdc++.h>
using namespace std;
const int maxn=100007;
int w[maxn],d[maxn],p[maxn],sz[maxn],num[maxn],h[maxn],tp[maxn],f[maxn],ed[maxn],n,m,rt,mod,op,x,y,z,cnt;
vector<int> to[maxn];
struct segtree{
    long long val[maxn<<2],lz[maxn<<2];
    void update(int o){val[o]=(val[o*2]+val[o*2+1])%mod;}
    void build(int l,int r,int o){
        if(l==r){val[o]=w[num[l]];lz[o]=0;return;}
        int mid=(l+r)>>1;
        build(l,mid,o*2),build(mid+1,r,o*2+1);
        update(o);
    }
    void pushdown(int l,int r,int o){
        if(lz[o]){
            int k=lz[o],mid=(l+r)>>1;
            val[o*2]+=1ll*k*(mid-l+1),val[o*2+1]+=1ll*k*(r-mid);
            val[o*2]%=mod,val[o*2+1]%=mod;
            lz[o*2]+=k,lz[o*2+1]+=k;
            lz[o]=0;
        }
    }
    void modify(int l,int r,int ll,int rr,int o,long long v){
        if(l<=ll&&rr<=r){val[o]=(val[o]+1ll*v*(rr-ll+1))%mod;lz[o]+=v;return;}
        pushdown(ll,rr,o);
        int mid=(ll+rr)>>1;
        if(l<=mid) modify(l,r,ll,mid,o*2,v);
        if(r>mid) modify(l,r,mid+1,rr,o*2+1,v);
        update(o);
    }
    long long query(int l,int r,int ll,int rr,int o){
        if(l<=ll&&rr<=r) return val[o]%mod;
        pushdown(ll,rr,o);
        int mid=(ll+rr)>>1;
        long long ans=0;
        if(l<=mid) ans+=query(l,r,ll,mid,o*2);
        if(r>mid) ans+=query(l,r,mid+1,rr,o*2+1);
        return ans%mod;
    }
} tr;
void dfs(int now,int fa,bool flg){
    if(flg){
        d[now]=d[fa]+1;
        p[now]=fa;
        sz[now]=1;
        for(auto i:to[now]) if(i!=fa){
            dfs(i,now,flg);
            if(sz[i]>sz[h[now]]) h[now]=i;
            sz[now]+=sz[i];
        }
    }else{
        f[now]=(++cnt);
        tp[now]=fa;
        num[cnt]=now;
        if(h[now]) dfs(h[now],fa,flg);
        for(auto i:to[now]) if(i!=h[now]&&i!=p[now]) dfs(i,i,flg);
        ed[now]=cnt;
    }
}
function<void()> opt[5]={
    [](){},
    [](){
    cin>>x>>y>>z;
    while(tp[x]!=tp[y]){
        if(d[tp[x]]<d[tp[y]]) swap(x,y);
        tr.modify(f[tp[x]],f[x],1,n,1,z);
        x=p[tp[x]];
    }
    if(d[x]<d[y]) swap(x,y);
    tr.modify(f[y],f[x],1,n,1,z);
},  [](){
    cin>>x>>y;
    long long ans=0;
    while(tp[x]!=tp[y]){
        if(d[tp[x]]<d[tp[y]]) swap(x,y);
        ans=(ans+tr.query(f[tp[x]],f[x],1,n,1))%mod;
        x=p[tp[x]];
    }
    if(d[x]<d[y]) swap(x,y);
    ans=(ans+tr.query(f[y],f[x],1,n,1))%mod;
    cout<<ans%mod<<'\n';
},  [](){
    cin>>x>>z;
    tr.modify(f[x],ed[x],1,n,1,z);
},  [](){
    cin>>x;
    cout<<tr.query(f[x],ed[x],1,n,1)<<'\n';}
};
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>m>>rt>>mod;
    for(int i=1;i<=n;i++) cin>>w[i];
    for(int i=1,a,b;i<n;i++){
        cin>>a>>b;
        to[a].push_back(b);
        to[b].push_back(a);
    }
    dfs(rt,rt,1);
    dfs(rt,rt,0);
    tr.build(1,n,1);
    for(int i=0;i<m;i++){
        cin>>op;
        opt[op]();
    }
}