萌新袜子5分求助!!!!!

回复帖子

@Dorbmon  2020-01-31 22:04 回复

真的只有5分!!!!求助!!!!!!!!!

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1000000;
bool fan [N];int son [2][N];int fa [N];
ll val [N];
ll rsize [N];
ll sum [N];
inline void push_up (int x) {
    rsize [x] = rsize [son [0][x]] + rsize [son [1][x]] + 1;
    sum [x] = sum [son [0][x]] + sum [son [1][x]] + val [x];
}
ll tag [2][N];
const ll MOD = 51061;
//1加
//0乘法 default:1
inline void push_down (int x) {
    if (son [0][x]) {
        sum [son [0][x]] *= tag [0][x];
        sum [son [0][x]] %= MOD;
        sum [son [0][x]] += tag [1][x] * rsize [son [0][x]];
        sum [son [0][x]] %= MOD;
        val [son [0][x]] *= tag [0][x];
        val [son [0][x]] %= MOD;
        val [son [0][x]] += tag [1][x];
        val [son [0][x]] %= MOD;
        tag [0][son [0][x]] *= tag [0][x];
        tag [0][son [0][x]] %= MOD;
        tag [1][son [0][x]] *= tag [0][x];
        tag [1][son [0][x]] %= MOD;
        tag [1][son [0][x]] += tag [1][x];
        tag [1][son [0][x]] %= MOD;
    }
    if (son [1][x]) {
        sum [son [1][x]] *= tag [0][x];
        sum [son [1][x]] %= MOD;
        sum [son [1][x]] += tag [1][x] * rsize [son [1][x]];
        sum [son [1][x]] %= MOD;
        val [son [1][x]] *= tag [0][x];
        val [son [1][x]] %= MOD;
        val [son [1][x]] += tag [1][x];
        val [son [1][x]] %= MOD;
        tag [0][son [1][x]] *= tag [0][x];
        tag [0][son [1][x]] %= MOD;
        tag [1][son [1][x]] *= tag [0][x];
        tag [1][son [1][x]] %= MOD;
        tag [1][son [1][x]] += tag [1][x];
        tag [1][son [1][x]] %= MOD;
    }
    tag [1][x] = 0;
    tag [0][x] = 1;
    if (fan [x]) {
        fan [son [1][x]] ^= 1;
        swap (son [0][son [1][x]],son [1][son [1][x]]);
        fan [son [0][x]] ^= 1;
        swap (son [0][son [0][x]],son [1][son [0][x]]);
        fan [x] = false;
    }
}
inline int get (int x) {
    return (son [1][fa [x]] == x);
}
inline bool is_root (int x) {
    return ((!fa [x]) || (son [get (x)][fa [x]] != x));
}
inline void connect (int a,int b,int d) {
    if (a) {
        fa [a] = b;
    }
    if (b) {
        son [d][b] = a;
        push_up (b);
    }
}
inline void rorate (int x) {
    //上旋
    int f = fa [x],ff = fa [f],d = get (x),e = get (f);
    if (is_root (x)) {
        return ;
    }
    if (!is_root (f)) {
        son [e][ff] = x;
    }
    fa [x] = ff;
    son [d][f] = son [d^1][x];
    if (son [d^1][x]) {
        fa [son [d^1][x]] = f;
    }
    fa [f] = x;
    son [d^1][x] = f;
    push_up (f);
    push_up (x);
}
int buf [N];
inline void splay (int x) {
    int y = x,z = 0;
    buf [++ z] = y;
    while (!is_root (y)) {
        buf [++ z] = (y = fa [y]);
        //cout << buf [z] << endl;
    }
    while (z) {
        push_down (buf [z --]);
    }
    for (int f = fa [x];!is_root (x) && (f = fa [x]);rorate (x)) {
        if (fa [f]) {
            rorate ((get (f) == get (x))?f:x);
        }
    }
    push_up (x);
}
inline void access (int x) {
    int y = 0;
    while (x) {
        //cout << x;
        splay (x);
        son [1][x] = y;
        push_up (x);
        y = x;
        x = fa [x];
    }
}
inline void make_root (int x) {
    access (x);splay (x);
    swap (son [0][x],son [1][x]);fan [x] ^= 1;
    return ;
}
inline void split (int a,int b) {
    make_root (a);  //因为深度一样的不可能在一棵splay中。
    access (b);
    splay (b);
}
inline int find_root (int x) {
    access (x);
    splay (x);
    while (son [0][x]) push_down (x),x = son [0][x];
    return x;
}
inline void cut (int u,int v) {
    split (u,v);
    //v为根 并且u是根了
    //所以u一定在v的最左儿子上
    if (find_root (v) == u && fa [u] == v && !son [1][u]) {
        son [0][v] = fa [u] = 0;
        push_up (v);
    }
}
int main(){
#ifndef ONLINE_JUDGE
    freopen ("shit.txt","r",stdin);
#endif
    ios::sync_with_stdio (false);
    int n,q;cin >> n >> q;
    for (int i = 1;i <= n;++ i) {
        rsize [i] = sum [i] = val [i] = tag [0][i] = 1;
    }
    for (int i = 1;i <= n - 1;++ i) {
        int u,v;cin >> u >> v;
        //连接u,v
        make_root (v);
        fa [v] = u;
    }
    while (q --) {
        char opt;cin >> opt;
        //cout << opt << endl;
        if (opt == '+') {
            ll u,v,c;cin >> u >> v >> c;
            c %= MOD;
            split (u,v);
            val [v] += c;
            val [v] %= MOD;
            sum [v] += rsize [v] * c;
            sum [v] %= MOD;
            tag [1][v] += c;
            tag [1][v] %= MOD;
        } else if (opt == '*') {
            ll u,v,c;cin >> u >> v >> c;
            split (u,v);
            val [v] *= c;
            val [v] %= MOD;
            sum [v] *= c;
            sum [v] %= MOD;
            tag [1][v] *= c;
            tag [1][v] %= MOD;
            tag [0][v] *= c;
            tag [0][v] %= MOD;
        } else if (opt == '-') {
            int u1,v1,u2,v2;cin >> u1 >> v1 >> u2 >> v2;
            cut (u1,v1);
            make_root (u2);
            access (v2);
            if (find_root (v2) != u2) {
                fa [u2] = v2;
            }
        } else if (opt == '/'){
            int u,v;cin >> u >> v;
            split (u,v);
            cout << sum [v] << endl;
        }
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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