自闭啦QAQ

回复帖子

@_Wallace_  2020-04-29 21:43 回复

发错了重发一边

刚学lct 1 day

然后Wa光 0pts

#include <iostream>
#include <algorithm>

using namespace std;
typedef long long llint;
const int N = 1e5 + 5;
const int mod = 51061;

#define lc ch[x][0]
#define rc ch[x][1]

int ch[N][2], size[N], fa[N];
llint val[N], sum[N], add[N], mul[N];
bool rev[N];

inline void pushup(int x) {
    size[x] = size[lc] + size[rc] + 1;
    sum[x] = (sum[lc] + sum[rc] + val[x]) % mod;
}
inline bool isRoot(int x) {
    return x != ch[fa[x]][0] && x != ch[fa[x]][1];
}
inline void setRev(int x) {
    swap(lc, rc), rev[x] ^= 1;
}
inline void setAdd(int x, int v) {
    (add[x] += v) %= mod;
    (val[x] += v) %= mod;
    (sum[x] += llint(size[x]) * v % mod) %= mod;
}
inline void setMul(int x, int v) {
    (add[x] *= v) %= mod;
    (val[x] *= v) %= mod;
    (sum[x] *= v) %= mod;
    (mul[x] *= v) %= mod;
}
inline void pushdown(int x) {
    if (mul[x] != 1) setMul(lc, mul[x]), setMul(rc, mul[x]);
    if (add[x]) setAdd(lc, add[x]), setAdd(rc, add[x]);
    if (rev[x]) {
        if (lc) setRev(lc);
        if (rc) setRev(rc);
    }
    mul[x] = 1, rev[x] = add[x] = 0;
}

inline int getch(int x) {
    return x == ch[fa[x]][1];
}
inline void connect(int x, int f, int c) {
    fa[x] = f, ch[f][c] =x;
}
inline void rotate(int x) {
    int y = fa[x], r = fa[y];
    int u = getch(x), v = getch(y);
    int b = ch[x][u ^ 1];
    fa[x] = r;
    if (!isRoot(y)) connect(x, r, v);
    connect(b, y, u), connect(y, x, u ^ 1);
    pushup(y), pushup(x), pushup(r);
}

void pushdownAll(int x) {
    if (!isRoot(x)) pushdownAll(fa[x]);
    pushdown(x);
}
inline void splay(int x) {
    pushdownAll(x);
    for (register int y = fa[x]; !isRoot(x); rotate(x), y = fa[x])
        if (!isRoot(y)) rotate(getch(x) != getch(y) ? x : y);
    pushup(x);
}

inline void access(int x) {
    for (register int y = 0; x; x = fa[y = x])
        splay(x), rc = y, pushup(x);
}
inline void makeRoot(int x) {
    access(x), splay(x), setRev(x);
}
inline void split(int x, int y) {
    makeRoot(x), access(y), splay(y);
}
inline int findRoot(int x) {
    access(x), splay(x), pushdown(x);
    while(lc) pushdown(x = lc);
    return splay(x), x;
}
inline void link(int x, int y) {
    if (makeRoot(x), findRoot(y) != x) fa[x] = y;
}
inline void cut(int x, int y) {
    makeRoot(x);
    if (findRoot(y) == x && fa[y] == x && !ch[y][0])
        fa[y] = rc = 0, pushup(x);
}

signed main() {
    ios::sync_with_stdio(false);
    int n, q;

    cin >> n >> q;
    for (register int i = 1; i <= n; i++)
        mul[i] = val[i] = size[i] = 1;

    for (register int i = 1, u, v; i < n; i++)
        cin >> u >> v, link(u, v);

    for (; q; --q) {
        char cmd; int u, v, t;
        cin >> cmd >> u >> v;

        switch (cmd) {
            case '+' : cin >> t, split(u, v), setAdd(v, t); break;
            case '-' : cut(u, v), cin >> u >> v, link(u, v); break;
            case '*' : cin >> t, split(u, v), setMul(v, t); break;
            case '/' : split(u, v), cout << sum[v] << endl; break;
        }
    }
    return 0;
}

请不要无意义回复,谢谢

@Isaunoya 2020-04-29 21:56 回复 举报

大概所有人的 lct 写法都不太一样。。。所以自己调吧…反正就线段树2那种写法

@_Wallace_  2020-04-29 23:06 回复 举报

@UltiMadow 发现rotate写错了

AC Code:

/********************
Luogu P1501 [国家集训队]Tree II
https://www.luogu.com.cn/problem/P1501
********************/
#include <iostream>
#include <algorithm>

using namespace std;
typedef long long llint;
const int N = 1e5 + 5;
const int mod = 51061;

#define lc ch[x][0]
#define rc ch[x][1]

int ch[N][2], size[N], fa[N];
llint val[N], sum[N], add[N], mul[N];
bool rev[N];

inline void pushup(int x) {
    size[x] = size[lc] + size[rc] + 1;
    sum[x] = (sum[lc] + sum[rc] + val[x]) % mod;
}
inline bool isRoot(int x) {
    return x != ch[fa[x]][0] && x != ch[fa[x]][1];
}
inline void setRev(int x) {
    swap(lc, rc), rev[x] ^= 1;
}
inline void setAdd(int x, int v) {
    (add[x] += v) %= mod;
    (val[x] += v) %= mod;
    (sum[x] += llint(size[x]) * v % mod) %= mod;
}
inline void setMul(int x, int v) {
    (add[x] *= v) %= mod;
    (val[x] *= v) %= mod;
    (sum[x] *= v) %= mod;
    (mul[x] *= v) %= mod;
}
inline void pushdown(int x) {
    if (mul[x] != 1) setMul(lc, mul[x]), setMul(rc, mul[x]);
    if (add[x]) setAdd(lc, add[x]), setAdd(rc, add[x]);
    if (rev[x]) { if (lc) setRev(lc); if (rc) setRev(rc); }
    mul[x] = 1, rev[x] = add[x] = 0;
}

inline void rotate(int x) {
    int y = fa[x], z = fa[y];
    int k = ch[y][1] == x, w = ch[x][!k];
    if (!isRoot(y)) ch[z][ch[z][1] == y] = x;
    ch[x][!k] = y, ch[y][k] = w;
    if (w) fa[w] = y;
    fa[y] = x, fa[x] = z;
    pushup(y);
}

inline int getch(int x) {
    return x == ch[fa[x]][1];
}
int stk[N], top = 0;
void pushdownAll(int x) {
    int y = x; stk[top = 1] = y;
    while (!isRoot(y)) stk[++top] = y = fa[y];
    while (top) pushdown(stk[top--]);
}
inline void splay(int x) {
    pushdownAll(x);
    for (register int y = fa[x]; !isRoot(x); rotate(x), y = fa[x])
        if (!isRoot(y)) rotate(getch(x) != getch(y) ? x : y);
    pushup(x);
}

inline void access(int x) {
    for (register int y = 0; x; x = fa[y = x])
        splay(x), rc = y, pushup(x);
}
inline void makeRoot(int x) {
    access(x), splay(x), setRev(x);
}
inline void split(int x, int y) {
    makeRoot(x), access(y), splay(y);
}
inline int findRoot(int x) {
    access(x), splay(x), pushdown(x);
    while(lc) pushdown(x = lc);
    return splay(x), x;
}
inline void link(int x, int y) {
    if (makeRoot(x), findRoot(y) != x) fa[x] = y;
}
inline void cut(int x, int y) {
    makeRoot(x);
    if (findRoot(y) == x && fa[y] == x && !ch[y][0])
        fa[y] = rc = 0, pushup(x);
}

signed main() {
    ios::sync_with_stdio(false);
    int n, q;

    cin >> n >> q;
    for (register int i = 1; i <= n; i++)
        mul[i] = val[i] = size[i] = sum[i] = 1;

    for (register int i = 1, u, v; i < n; i++)
        cin >> u >> v, link(u, v);

    for (; q; --q) {
        char cmd; int u, v, t;
        cin >> cmd >> u >> v;

        switch (cmd) {
            case '+' : cin >> t, split(u, v), setAdd(v, t); break;
            case '-' : cut(u, v), cin >> u >> v, link(u, v); break;
            case '*' : cin >> t, split(u, v), setMul(v, t); break;
            case '/' : split(u, v), cout << sum[v] << endl; break;
        }
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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