萌新求助lct

回复帖子

@UltiMadow  2020-04-30 08:28 回复

RT,调了一天自闭了/kk

并且 rotate 和 splay 操作应该没写错(我甚至把之前写的lct板子拉过来了)

code here

不要无意义回复,蟹蟹

@xwmwr  2020-04-30 08:37 回复 举报

@UltiMadow 比了下你代码和我AC代码的 pushdownupdate以及其它函数, 大概没区别, 你可以找篇题解对着调, 也可以看看我的代码

#include<bits/stdc++.h>
using namespace std;
#define int long long

const int maxn = 1e5 + 5;
const int mod = 51061;

int siz[maxn], val[maxn], sum[maxn], adtag[maxn], mltag[maxn];
int fa[maxn], ch[maxn][2];
bool c[maxn];

inline bool is(int x) {
    return ch[fa[x]][0]!=x && ch[fa[x]][1]!=x;
}
inline void ml(int x, int t) {
    mltag[x] *= t; adtag[x] *=t;
    mltag[x] %= mod; adtag[x] %= mod;
    sum[x] *= t;
    sum[x] %= mod;
    val[x] *= t;
    val[x] %= mod;
}
inline void ad(int x, int t) {
    adtag[x] += t;
    adtag[x] %= mod;
    sum[x] += siz[x] * t;
    sum[x] %= mod;
    val[x] += t;
    val[x] %= mod;
}
inline void rv(int x) {
    c[x]^=1; swap(ch[x][0], ch[x][1]);
}
inline void ps(int x) {
    if(mltag[x] != 1) {
        ml(ch[x][0], mltag[x]);
        ml(ch[x][1], mltag[x]);
        mltag[x] = 1;
    }
    if(adtag[x]) {
        ad(ch[x][0], adtag[x]);
        ad(ch[x][1], adtag[x]);
        adtag[x] = 0;
    }
    if(c[x]) {
        rv(ch[x][0]);
        rv(ch[x][1]);
        c[x]=0;
    }
}
inline void ud(int x) {
    sum[x] = (sum[ch[x][0]] + sum[ch[x][1]] + val[x]) % mod;
    siz[x] = siz[ch[x][0]] + siz[ch[x][1]] + 1;
}
void ro(int x) {
    int y=fa[x], z=fa[y];
    int sz = ch[z][1]==y;
    int sy = ch[y][1]==x;
    int sx = sy^1;
    int d = ch[x][sx];

    if(!is(y)) ch[z][sz]=x;
    fa[x]=z;
    ch[x][sx]=y;
    fa[y]=x;
    ch[y][sy]=d;
    if(d) fa[d]=y;

    ud(y), ud(x);
}
void gx(int x) {
    if(!is(x)) gx(fa[x]);
    ps(x);
}
void sp(int x) {
    gx(x);
    while(!is(x)) {
        int y = fa[x];
        if(!is(y)) {
            if(ch[fa[y]][1]==y  ^ ch[y][1]==x) ro(x);
            else ro(y);
        }
        ro(x);
    }
}
void ac(int x) {
    int d = 0;
    while(x) {
        sp(x);
        ch[x][1] = d;
        ud(x);
        d=x;
        x=fa[x];
    }
}
void mk(int x) {
    ac(x); sp(x); rv(x);
}
int fr(int x) {
    ac(x); sp(x);
    while(ch[x][0]) x=ch[x][0];
    return x;
}
void lk(int x,int y) {
    mk(x);
    if(fr(y)!=x) fa[x]=y;
}
void ct(int x,int y) {
    mk(x);
    if(fr(y)==x && fa[x]==y && !ch[x][1]) {
        fa[x] = ch[y][0] = 0;
        ud(y);
    }
}

int n, q;

signed main() {
    scanf("%lld%lld", &n, &q);
    for(int i=1; i<=n; ++i) val[i] = sum[i] = siz[i] = mltag[i] = 1;
    for(int i=1; i< n; ++i) {
        int x,y;
        scanf("%lld%lld", &x,&y);
        lk(x,y);
    }

    char op[4];
    while(q--)
    {
        scanf("%s", op);
        if(op[0] == '+') {
            int u,v,c;
            scanf("%lld%lld%lld", &u, &v, &c);
            mk(u); ac(v); sp(v);
            ad(v, c);
        } else if(op[0] == '-') {
            int u1,v1,u2,v2;
            scanf("%lld%lld%lld%lld", &u1, &v1, &u2, &v2);
            ct(u1, v1);
            lk(u2, v2);
        } else if(op[0] == '*') {
            int u,v,c;
            scanf("%lld%lld%lld", &u, &v, &c);
            mk(u); ac(v); sp(v);
            ml(v, c);
        } else {
            int u, v;
            scanf("%lld%lld", &u, &v);
            mk(u); ac(v); sp(v);
            cout << sum[v]%mod << '\n';
        }
    }
    return 0;
}
@ez_lcw 2020-04-30 08:40 回复 举报

说实话,调这种码农题必须得找个真人跟你一起调或者自己调

@_Wallace_  2020-04-30 09:07 回复 举报

@UltiMadow

道理我都懂,但你的代码空格为什么时有时无呢?

道理我都懂,但是你的 cut 为什么把x,y搞反了呢

void ct(int x,int y) {
    mk(x);
    if(fr(y)==x && fa[y]==x && !ch[y][0]) {
        fa[y] = ch[x][1] = 0;
        ud(x);
    }
}

改后50pts

总之我再看看

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



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