萌新求助，真的刚学 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];
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 mulSplay(int x,int v){
}
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(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);
}
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);
}
//  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);
//}
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++){
}
int x,y,z;
char typ[2];
while(M--){
scanf(" %s",typ);
if(typ[0]=='+'){
scanf("%d%d%d",&x,&y,&z);
}
else if(typ[0]=='-'){
scanf("%d%d",&x,&y);cut(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;
}

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

@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];
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){
}
inline void mulSplay(long long x,long long v){
}
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(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);
}
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++){
}
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);
}
else if(typ[0]=='-'){
scanf("%lld%lld",&x,&y);cut(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];
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){
}
inline void mulSplay(long long x,long long v){
}
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(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);
}
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++){
}
long long x,y,z;
char typ[2];
while(M--){
scanf(" %s",typ);
if(typ[0]=='+'){
scanf("%lld%lld%lld",&x,&y,&z);
}
else if(typ[0]=='-'){
scanf("%lld%lld",&x,&y);cut(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;
}