萌新袜子刚学 CSP 19pts 求调

LuoFeng_Nanami @ 2023-09-28 21:38:25

#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i,a,b) for(rll i=a;i<=b;i++)
#define Fdn(i,a,b) for(rll i=a;i>=b;i--)
#define int ll
#define itn int
#define umap unordered_map
#define uset unordered_set
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back

using namespace std;

const int inf = 0x3f3f3f3f; 
const int maxn = 1e5 + 7;

int dep[maxn], fa[maxn], top[maxn], hson[maxn], siz[maxn], dfn[maxn], rnk[maxn];
int tot;
int n, m, root, mod;
vector<int> G[maxn];
int d[maxn * 4], b[maxn * 4];
int num[maxn];

inline void dfs1(int u){
    hson[u] = -1;
    siz[u] = 1;
    for(auto v : G[u]){
        if(!dep[v]){
            dep[v] = dep[u] + 1, fa[v] = u;
            dfs1(v);
            siz[u] += siz[v];
            if(hson[u] == -1 || siz[v] > siz[hson[u]]) hson[u] = v;
        }
    }
} 

inline void dfs2(int u, int f){
    top[u] = f;
    dfn[u] = ++tot;
    rnk[tot] = u;
    if(hson[u] == -1)
        return;
    dfs2(hson[u], f);
    for(auto v : G[u])
        if(v != hson[u] && v != fa[u])
            dfs2(v, v); 
}

inline void build(int l, int r, int p){
    if(l == r){
        d[p] = num[rnk[l]] % mod;
        return;
    }
    int mid = l + ((r - l) >> 1);
    build(l, mid, p << 1),
    build(mid + 1, r, (p << 1) | 1);
    d[p] = (d[p << 1] + d[(p << 1) | 1]) % mod;
}

inline void pd(int s, int t, int p){
    int l = (p << 1), r = (p << 1) | 1, mid = (s + t) >> 1;
    if(b[p]){
        b[p << 1] += b[p];
        b[(p << 1) | 1] += b[p];
        d[p << 1] = (d[p << 1] + b[p] * (mid - s + 1)) % mod;
        d[(p << 1) | 1] = (d[(p << 1) | 1] + b[p] * (t - mid)) % mod;
    }
}

inline void update(int l,int r,int c,int s,int t,int p){
    if(l <= s && t <= r){
        d[p] += (t - s + 1) * c,b[p] += c;
        return;
    }
    int m = s + ((t - s) >> 1);
    pd(s, t, p);
    if(l <= m) update(l, r, c, s, m, p << 1);
    if(r > m) update(l, r, c, m + 1, t, (p << 1) | 1);
    d[p] = (d[p << 1] + d[(p << 1) | 1]) % mod;
}

inline int getsum(int l,int r,int s,int t,int p){
    if(l <= s && t <= r)
        return d[p] % mod;
    int m = s + ((t - s) >> 1);
    int sum = 0;
    pd(s, t, p);
    if(l <= m) sum = (sum + getsum(l, r, s, m, p << 1)) % mod;
    if(r > m) sum = (sum + getsum(l, r, m + 1, t, (p << 1) | 1)) % mod;
    return sum;
}

inline void upd(int s, int t, int c){
    c %= mod;
    while(top[s] != top[t]){
        if(dep[top[s]] < dep[top[t]]) 
            swap(s, t);
        update(dfn[top[s]], dfn[s], c, 1, n, 1);
        s = fa[top[s]];
    }
    if(dep[s] > dep[t])
        swap(s, t);
    update(dfn[s], dfn[t], c, 1, n, 1);
}

inline int get(int s, int t){
    int ret = 0;
    while(top[s] != top[t]){
        if(dep[top[s]] < dep[top[t]])
            swap(s, t);
        ret = (ret + getsum(dfn[top[s]], dfn[s], 1, n, 1)) % mod;
        s = fa[top[s]];
    }
    if(dep[s] > dep[t])
        swap(s, t);
    ret = (ret + getsum(dfn[s], dfn[t], 1, n, 1)) % mod;
    return ret;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> root >> mod;
    F(i, 1, n)
        cin >> num[i];
    F(i, 1, n - 1){
        int u, v;
        cin >> u >> v;
        G[u].pb(v), G[v].pb(u);
    }
    dfs1(root);
    dfs2(root, 0);
    build(1, n, 1);
    while(m--){
        int op;
        cin >> op;
        if(op == 1){
            int x, y, z;
            cin >> x >> y >> z;
            upd(x, y, z);
        }
        else if(op == 2){
            int x, y;
            cin >> x >> y;
            cout << get(x, y) << '\n';
        }
        else if(op == 3){
            int x, y;
            cin >> x >> y;
            update(dfn[x], dfn[x] + siz[x] - 1, y, 1, n, 1);
        } 
        else if(op == 4){
            int x;
            cin >> x;
            cout << getsum(dfn[x], dfn[x] + siz[x] - 1, 1, n, 1) << '\n';
        }
    }

    return 0;
}

by SZX__HAPPY @ 2023-09-28 21:52:48

《萌新袜子》

《刚学 CSP》

by LuoFeng_Nanami @ 2023-09-28 21:54:08

@szx20100828 确实，今年第一次进复赛\ 话说我这是哪里错了 /kk

by liaiyang @ 2023-09-28 21:58:58

尝试多开点空间？总有一种空间小了的感觉

by LuoFeng_Nanami @ 2023-09-28 22:04:16

忘标记清零，清零后 46pts：

#include<bits/stdc++.h>
#define ll long long
#define rll register ll
#define F(i,a,b) for(rll i=a;i<=b;i++)
#define Fdn(i,a,b) for(rll i=a;i>=b;i--)
//#define int ll
#define itn int
#define umap unordered_map
#define uset unordered_set
#define ld long double
#define pii pair<int,int>
#define pll pair<long long,long long>
#define pb push_back

using namespace std;

const int inf = 0x3f3f3f3f; 
const int maxn = 1e5 + 7;

int dep[maxn], fa[maxn], top[maxn], hson[maxn], siz[maxn], dfn[maxn], rnk[maxn];
int tot;
int n, m, root, mod;
vector<int> G[maxn];
int d[maxn * 4], b[maxn * 4];
int num[maxn];

inline void dfs1(int u){
    hson[u] = -1;
    siz[u] = 1;
    for(auto v : G[u]){
        if(!dep[v]){
            dep[v] = dep[u] + 1, fa[v] = u;
            dfs1(v);
            siz[u] += siz[v];
            if(hson[u] == -1 || siz[v] > siz[hson[u]]) hson[u] = v;
        }
    }
} 

inline void dfs2(int u, int f){
    top[u] = f;
    dfn[u] = ++tot;
    rnk[tot] = u;
    if(hson[u] == -1)
        return;
    dfs2(hson[u], f);
    for(auto v : G[u])
        if(v != hson[u] && v != fa[u])
            dfs2(v, v); 
}

inline void build(int l, int r, int p){
    if(l == r){
        d[p] = num[rnk[l]] % mod;
        return;
    }
    int mid = l + ((r - l) >> 1);
    build(l, mid, p << 1),
    build(mid + 1, r, (p << 1) | 1);
    d[p] = (d[p << 1] + d[(p << 1) | 1]) % mod;
}

inline void pd(int s, int t, int p){
    int l = (p << 1), r = (p << 1) | 1, mid = (s + t) >> 1;
    if(b[p]){
        b[l] += b[p];
        b[r] += b[p];
        d[l] = (d[l] + b[p] * (mid - s + 1)) % mod;
        d[r] = (d[r] + b[p] * (t - mid)) % mod;
    }
    b[p] = 0;
}

inline void update(int l,int r,int c,int s,int t,int p){
    if(l <= s && t <= r){
        d[p] += (t - s + 1) * c,b[p] += c;
        return;
    }
    int m = s + ((t - s) >> 1);
    pd(s, t, p);
    if(l <= m) update(l, r, c, s, m, p << 1);
    if(r > m) update(l, r, c, m + 1, t, (p << 1) | 1);
    d[p] = (d[p << 1] + d[(p << 1) | 1]) % mod;
}

inline int getsum(int l,int r,int s,int t,int p){
    if(l <= s && t <= r)
        return d[p] % mod;
    int m = s + ((t - s) >> 1);
    int sum = 0;
    pd(s, t, p);
    if(l <= m) sum = (sum + getsum(l, r, s, m, p << 1)) % mod;
    if(r > m) sum = (sum + getsum(l, r, m + 1, t, (p << 1) | 1)) % mod;
    return sum;
}

inline void upd(int s, int t, int c){
    c %= mod;
    while(top[s] != top[t]){
        if(dep[top[s]] < dep[top[t]]) 
            swap(s, t);
        update(dfn[top[s]], dfn[s], c, 1, n, 1);
        s = fa[top[s]];
    }
    if(dep[s] > dep[t])
        swap(s, t);
    update(dfn[s], dfn[t], c, 1, n, 1);
}

inline int get(int s, int t){
    int ret = 0;
    while(top[s] != top[t]){
        if(dep[top[s]] < dep[top[t]])
            swap(s, t);
        ret = (ret + getsum(dfn[top[s]], dfn[s], 1, n, 1)) % mod;
        s = fa[top[s]];
    }
    if(dep[s] > dep[t])
        swap(s, t);
    ret = (ret + getsum(dfn[s], dfn[t], 1, n, 1)) % mod;
    return ret;
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0);

    cin >> n >> m >> root >> mod;
    F(i, 1, n)
        cin >> num[i];
    F(i, 1, n - 1){
        int u, v;
        cin >> u >> v;
        G[u].pb(v), G[v].pb(u);
    }
    dfs1(root);
    dfs2(root, 0);
    build(1, n, 1);
    while(m--){
        int op;
        cin >> op;
        if(op == 1){
            int x, y, z;
            cin >> x >> y >> z;
            upd(x, y, z);
        }
        else if(op == 2){
            int x, y;
            cin >> x >> y;
            cout << get(x, y) << '\n';
        }
        else if(op == 3){
            int x, y;
            cin >> x >> y;
            update(dfn[x], dfn[x] + siz[x] - 1, y, 1, n, 1);
        } 
        else if(op == 4){
            int x;
            cin >> x;
            cout << getsum(dfn[x], dfn[x] + siz[x] - 1, 1, n, 1) << '\n';
        }
    }

    return 0;
}

by LuoFeng_Nanami @ 2023-09-28 22:04:45

@liaiyang 可是MLE 3个

by liaiyang @ 2023-09-28 22:08:28

@OIer1030 空间开小了啥牛马东西都能出来说实话

by LuoFeng_Nanami @ 2023-09-28 22:11:13

@liaiyang 8 倍空间都没用 /kk

by LuoFeng_Nanami @ 2023-09-28 22:22:06

@liaiyang 好了，树剖dfs1问题，thx

by zzy0618 @ 2023-09-28 23:00:05

@OIer1030 您这个 dep[root] 是不是就是0，而在之后 dep[root] 又会变成 2

by LoadingSpace @ 2023-09-29 19:53:32

使用有意义且描述明确的标题

在邮件列表、新闻群组或论坛中，大约 50 字以内的标题是抓住资深专家注意力的好机会。别用喋喋不休的「帮帮忙」、「跪求」、「急」、「萌新刚学 OI xxx s」、「萌新妹子求助」（更别说 「救命啊！！！！」这样让人反感的话，用这种标题会被条件反射式地忽略）来浪费这个机会。不要妄想用你的痛苦程度来打动我们，而应该是在这点空间中使用极简单扼要的描述方式来提出问题。

    ——《洛谷新用户必读》—《提问的智慧》