萌新求助,真的刚学 LCT ,5 pts

回复帖子

@tiger2005  2021-01-13 23:18 回复
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
// Splay
const int MAXN = 1e5 + 10;
const long long Md = 51061;
int val[MAXN],cc[MAXN][2],fa[MAXN],siz[MAXN];
bool rev[MAXN];
long long adt[MAXN],ans[MAXN],mul[MAXN];
inline void pushUp(int x){
    if(x==0)    return;
    ans[x]=(ans[cc[x][0]]+ans[cc[x][1]]+val[x])%Md;
    siz[x]=siz[cc[x][0]]+siz[cc[x][1]]+1;
}
inline void revSplay(int x){
    swap(cc[x][0],cc[x][1]),rev[x]^=1;
}
inline void addSplay(int x,int v){
    (adt[x]+=v)%=Md;(ans[x]+=1ll*v*siz[x])%=Md;(val[x]+=v)%=Md;
}
inline void mulSplay(int x,int v){
    (adt[x]*=v)%=Md;(mul[x]*=v)%=Md;(val[x]*=v)%=Md;(ans[x]*=v)%=Md;
}
inline void pushDown(int x){
    if(mul[x]!=1){
        if(cc[x][0])    mulSplay(cc[x][0],mul[x]);
        if(cc[x][1])    mulSplay(cc[x][1],mul[x]);
        mul[x]=1;
    }
    if(adt[x]){
        if(cc[x][0])    addSplay(cc[x][0],adt[x]);
        if(cc[x][1])    addSplay(cc[x][1],adt[x]);
        adt[x]=0;
    }
    if(rev[x]){
        if(cc[x][0])    revSplay(cc[x][0]);
        if(cc[x][1])    revSplay(cc[x][1]);
        rev[x]=false;
    }
}
// Start - nroot
inline bool nroot(int x){
    return cc[fa[x]][0]==x || cc[fa[x]][1]==x;
}
// End - nroot
inline void rtt(int x){
    int y=fa[x],z=fa[y],k=(cc[y][1]==x);
    if(z && nroot(y))
        cc[z][cc[z][1]==y]=x;
    fa[x]=z;
    cc[y][k]=cc[x][!k];
    if(cc[x][!k])   fa[cc[x][!k]]=y;
    cc[x][!k]=y;fa[y]=x;
    pushUp(y);pushUp(x);
}
vector<int> stk;
inline void splay(int x,int g=0){
    int q=x;stk.push_back(q);
    while(nroot(q)) stk.push_back(q=fa[q]);
    while(!stk.empty()) pushDown(stk.back()),stk.pop_back();
    while(nroot(x)){
        int y=fa[x],z=fa[y];
        if(nroot(y))
            ((cc[z][0]==y)^(cc[y][0]==x))?rtt(x):rtt(y);
        rtt(x);
    }
    pushUp(x);
}
// Link Cut Tree
inline void access(int x){
    for(int y=0;x;x=fa[y=x])
        splay(x),cc[x][1]=y,pushUp(x);
}
inline void makeRoot(int x){
    access(x);splay(x);revSplay(x);
}
inline int findRoot(int x){
    access(x);splay(x);
    while(cc[x][0]) pushDown(x),x=cc[x][0];
    splay(x);return x;
}
inline void split(int x,int y){
    makeRoot(x);access(y);splay(y);
}
//inline void link(int x,int y){
//  makeRoot(x);
//  if(findRoot(y)==x)  return;
//  fa[x]=y;pushUp(y);
//}
//inline void cut(int x,int y){
//  makeRoot(x);
//  if(findRoot(y)!=x || fa[y]!=x || cc[y][0])  return;
//  fa[y]=cc[x][1]=0;pushUp(x);
//}
inline void link(int x,int y){
    makeRoot(x);fa[x]=y;pushUp(y);
}
inline void cut(int x,int y){
    split(x,y);fa[x]=cc[y][0]=0;
}
int N,M;
int main(){
    scanf("%d%d",&N,&M);
    for(int i=1;i<=N;i++)   mul[i]=siz[i]=val[i]=ans[i]=1;
    for(int i=1,x,y;i<N;i++){
        scanf("%d%d",&x,&y);link(x,y);
    }
    int x,y,z;
    char typ[2];
    while(M--){
        scanf(" %s",typ);
        if(typ[0]=='+'){
            scanf("%d%d%d",&x,&y,&z);
            split(x,y);addSplay(y,z);
        }
        else if(typ[0]=='-'){
            scanf("%d%d",&x,&y);cut(x,y);
            scanf("%d%d",&x,&y);link(x,y);
        }
        else if(typ[0]=='*'){
            scanf("%d%d%d",&x,&y,&z);
            split(x,y);mulSplay(y,z);
        }
        else{
            scanf("%d%d",&x,&y);
            split(x,y);printf("%lld\n",ans[y]);
        }
    }
    return 0;
}

情况是只 AC 了最后一个点。

@fhqTreap 2021-01-13 23:38 回复 举报

我当时模数写错了也是只对了最后一个点,您可以试试把所有跟答案有关的地方都开long long

@tiger2005  2021-01-13 23:50 回复 举报

@fhqTreap 目前是 55pts

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
// Splay
const long long MAXN = 2e5 + 10;
const long long Md = 51061;
long long cc[MAXN][2],fa[MAXN];
bool rev[MAXN];
long long val[MAXN],adt[MAXN],ans[MAXN],mul[MAXN],siz[MAXN];
inline void pushUp(long long x){
    if(x==0)    return;
    ans[x]=(ans[cc[x][0]]+ans[cc[x][1]]+val[x])%Md;
    siz[x]=siz[cc[x][0]]+siz[cc[x][1]]+1;
}
inline void revSplay(long long x){
    swap(cc[x][0],cc[x][1]),rev[x]^=1;
}
inline void addSplay(long long x,long long v){
    (adt[x]+=v)%=Md;(ans[x]+=v*siz[x])%=Md;(val[x]+=v)%=Md;
}
inline void mulSplay(long long x,long long v){
    (adt[x]*=v)%=Md;(mul[x]*=v)%=Md;(val[x]*=v)%=Md;(ans[x]*=v)%=Md;
}
inline void pushDown(long long x){
    if(mul[x]!=1){
        if(cc[x][0])    mulSplay(cc[x][0],mul[x]);
        if(cc[x][1])    mulSplay(cc[x][1],mul[x]);
        mul[x]=1;
    }
    if(adt[x]){
        if(cc[x][0])    addSplay(cc[x][0],adt[x]);
        if(cc[x][1])    addSplay(cc[x][1],adt[x]);
        adt[x]=0;
    }
    if(rev[x]){
        if(cc[x][0])    revSplay(cc[x][0]);
        if(cc[x][1])    revSplay(cc[x][1]);
        rev[x]=false;
    }
}
// Start - nroot
inline bool nroot(long long x){
    return cc[fa[x]][0]==x || cc[fa[x]][1]==x;
}
// End - nroot
inline void rtt(long long x){
    long long y=fa[x],z=fa[y],k=(cc[y][1]==x);
    if(z && nroot(y))
        cc[z][cc[z][1]==y]=x;
    fa[x]=z;
    cc[y][k]=cc[x][!k];
    if(cc[x][!k])   fa[cc[x][!k]]=y;
    cc[x][!k]=y;fa[y]=x;
    pushUp(y);pushUp(x);
}
vector<long long> stk;
inline void splay(long long x,long long g=0){
    long long q=x;stk.push_back(q);
    while(nroot(q)) stk.push_back(q=fa[q]);
    while(!stk.empty()) pushDown(stk.back()),stk.pop_back();
    while(nroot(x)){
        long long y=fa[x],z=fa[y];
        if(nroot(y))
            ((cc[z][0]==y)^(cc[y][0]==x))?rtt(x):rtt(y);
        rtt(x);
    }
    pushUp(x);
}
// Link Cut Tree
inline void access(long long x){
    for(long long y=0;x;x=fa[y=x])
        splay(x),cc[x][1]=y,pushUp(x);
}
inline void makeRoot(long long x){
    access(x);splay(x);revSplay(x);
}
inline long long findRoot(long long x){
    access(x);splay(x);
    while(cc[x][0]) pushDown(x),x=cc[x][0];
    splay(x);return x;
}
inline void split(long long x,long long y){
    makeRoot(x);access(y);splay(y);
}
//inline void link(long long x,long long y){
//  makeRoot(x);
//  if(findRoot(y)==x)  return;
//  fa[x]=y;pushUp(y);
//}
//inline void cut(long long x,long long y){
//  makeRoot(x);
//  if(findRoot(y)!=x || fa[y]!=x || cc[y][0])  return;
//  fa[y]=cc[x][1]=0;pushUp(x);
//}
inline void link(long long x,long long y){
    makeRoot(x);fa[x]=y;pushUp(y);
}
inline void cut(long long x,long long y){
    split(x,y);fa[x]=cc[y][0]=0;
}
long long N,M;
int main(){
    scanf("%lld%lld",&N,&M);
    for(long long i=1;i<=N;i++) mul[i]=siz[i]=val[i]=ans[i]=1;
    for(long long i=1,x,y;i<N;i++){
        scanf("%lld%lld",&x,&y);link(x,y);
    }
    long long x,y;
    long long z;
    char typ[2];
    while(M--){
        scanf(" %s",typ);
        if(typ[0]=='+'){
            scanf("%lld%lld%lld",&x,&y,&z);
            split(x,y);addSplay(y,z);
        }
        else if(typ[0]=='-'){
            scanf("%lld%lld",&x,&y);cut(x,y);
            scanf("%lld%lld",&x,&y);link(x,y);
        }
        else if(typ[0]=='*'){
            scanf("%lld%lld%lld",&x,&y,&z);
            split(x,y);mulSplay(y,z);
        }
        else if(typ[0]=='/'){
            scanf("%lld%lld",&x,&y);
            split(x,y);printf("%lld\n",ans[y]);
        }
    }
    return 0;
}
@tiger2005  2021-01-14 00:04 回复 举报

@fhqTreap AC 了,十分感谢。

Code:

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;
// Splay
const long long MAXN = 2e5 + 10;
const long long Md = 51061;
long long cc[MAXN][2],fa[MAXN];
bool rev[MAXN];
long long val[MAXN],adt[MAXN],ans[MAXN],mul[MAXN],siz[MAXN];
inline void pushUp(long long x){
    if(x==0)    return;
    ans[x]=(ans[cc[x][0]]+ans[cc[x][1]]+val[x])%Md;
    siz[x]=siz[cc[x][0]]+siz[cc[x][1]]+1;
}
inline void revSplay(long long x){
    swap(cc[x][0],cc[x][1]),rev[x]^=1;
}
inline void addSplay(long long x,long long v){
    (adt[x]+=v)%=Md;(ans[x]+=v*siz[x])%=Md;(val[x]+=v)%=Md;
}
inline void mulSplay(long long x,long long v){
    (adt[x]*=v)%=Md;(mul[x]*=v)%=Md;(val[x]*=v)%=Md;(ans[x]*=v)%=Md;
}
inline void pushDown(long long x){
    if(mul[x]!=1){
        if(cc[x][0])    mulSplay(cc[x][0],mul[x]);
        if(cc[x][1])    mulSplay(cc[x][1],mul[x]);
        mul[x]=1;
    }
    if(adt[x]){
        if(cc[x][0])    addSplay(cc[x][0],adt[x]);
        if(cc[x][1])    addSplay(cc[x][1],adt[x]);
        adt[x]=0;
    }
    if(rev[x]){
        if(cc[x][0])    revSplay(cc[x][0]);
        if(cc[x][1])    revSplay(cc[x][1]);
        rev[x]=false;
    }
}
// Start - nroot
inline bool nroot(long long x){
    return cc[fa[x]][0]==x || cc[fa[x]][1]==x;
}
// End - nroot
inline void rtt(long long x){
    long long y=fa[x],z=fa[y],k=(cc[y][1]==x);
    if(z && nroot(y))
        cc[z][cc[z][1]==y]=x;
    fa[x]=z;
    cc[y][k]=cc[x][!k];
    if(cc[x][!k])   fa[cc[x][!k]]=y;
    cc[x][!k]=y;fa[y]=x;
    pushUp(y);pushUp(x);
}
vector<long long> stk;
inline void splay(long long x){
    long long q=x;stk.push_back(q);
    while(nroot(q)) stk.push_back(q=fa[q]);
    while(!stk.empty()) pushDown(stk.back()),stk.pop_back();
    while(nroot(x)){
        long long y=fa[x],z=fa[y];
        if(nroot(y))
            ((cc[z][0]==y)^(cc[y][0]==x))?rtt(x):rtt(y);
        rtt(x);
    }
    pushUp(x);
}
// Link Cut Tree
inline void access(long long x){
    for(long long y=0;x;x=fa[y=x])
        splay(x),cc[x][1]=y,pushUp(x);
}
inline void makeRoot(long long x){
    access(x);splay(x);revSplay(x);
}
inline long long findRoot(long long x){
    access(x);splay(x);
    while(cc[x][0]) pushDown(x),x=cc[x][0];
    return x;
}
inline void split(long long x,long long y){
    makeRoot(x);access(y);splay(y);
}
inline void link(long long x,long long y){
    makeRoot(x);
    if(findRoot(x)!=y)  fa[x]=y;
}
inline void cut(long long x,long long y){
    makeRoot(x);split(x,y);
    if(findRoot(y)==x && fa[x]==y && !cc[x][1])
       fa[x]=cc[y][0]=0;
}
long long N,M;
int main(){
    scanf("%lld%lld",&N,&M);
    for(long long i=1;i<=N;i++) mul[i]=siz[i]=val[i]=1;
    for(long long i=1,x,y;i<N;i++){
        scanf("%lld%lld",&x,&y);link(x,y);
    }
    long long x,y,z;
    char typ[2];
    while(M--){
        scanf(" %s",typ);
        if(typ[0]=='+'){
            scanf("%lld%lld%lld",&x,&y,&z);
            split(x,y);addSplay(y,z);
        }
        else if(typ[0]=='-'){
            scanf("%lld%lld",&x,&y);cut(x,y);
            scanf("%lld%lld",&x,&y);link(x,y);
        }
        else if(typ[0]=='*'){
            scanf("%lld%lld%lld",&x,&y,&z);
            split(x,y);mulSplay(y,z);
        }
        else if(typ[0]=='/'){
            scanf("%lld%lld",&x,&y);
            split(x,y);printf("%lld\n",ans[y]);
        }
    }
    return 0;
}
反馈
如果你认为某个帖子有问题,欢迎向洛谷反馈,以帮助更多的同学。



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