[BZOJ2631]tree(LCT)
제목 설명
전송문
문제풀이
판자 문제×+ 의 조작은 약간의 기교를 사용했다.너도 선승후승과 선승후승은 다르다는 것을 발견했을 것이다.처음에는 표시를 할 때 먼저 밑에 예전의 표시를 해야 한다고 생각했는데, 밑에 표시가 있으면 어떡하지?그것은 끝이 없다 = 문제풀이를 보고서야 비로소 매번의 선승후가가 정확하다는 것을 보장하는 매우 교묘한 방식이 있다는 것을 알게 되었다.구체적으로 코드를 보아라.
코드
#include
#include
#include
using namespace std;
#define LL unsigned int
const int max_n=1e5+5;
const int Mod=51061;
int n,q,x,y,u,v,c,u1,v1,u2,v2;
int f[max_n],ch[max_n][2],size[max_n],reverse[max_n];
LL key[max_n],sum[max_n],add[max_n],mul[max_n];
int strack[max_n];
inline int get(int x){
return ch[ f[x] ][1]==x;
}
inline int Is_Root(int x){
return ch[ f[x] ][0]!=x&&ch[ f[x] ][1]!=x;
}
inline void update(int x){
if (x){
sum[x]=key[x];
if (ch[x][0]) sum[x]=(int)((LL)(sum[x]+sum[ ch[x][0] ])%Mod);
if (ch[x][1]) sum[x]=(int)((LL)(sum[x]+sum[ ch[x][1] ])%Mod);
size[x]=1;
if (ch[x][0]) size[x]+=size[ ch[x][0] ];
if (ch[x][1]) size[x]+=size[ ch[x][1] ];
}
}
inline void mark(int x,LL y,LL z){
key[x]=(key[x]*z+y)%Mod;
sum[x]=(sum[x]*z+size[x]*y)%Mod;
add[x]=(add[x]*z+y)%Mod;
mul[x]=(mul[x]*z)%Mod;
}
inline void pushdown(int x){
if (x){
if (reverse[x]){
swap(ch[x][0],ch[x][1]);
if (ch[x][0]) reverse[ ch[x][0] ]^=1;
if (ch[x][1]) reverse[ ch[x][1] ]^=1;
reverse[x]=0;
}
if (add[x]!=0||mul[x]!=1){
if (ch[x][0]) mark(ch[x][0],add[x],mul[x]);
if (ch[x][1]) mark(ch[x][1],add[x],mul[x]);
add[x]=0;
mul[x]=1;
}
}
}
inline void rotate(int x){
int old=f[x],oldf=f[old],which=get(x);
if (!Is_Root(old))
ch[oldf][ ch[oldf][1]==old ]=x;
f[x]=oldf;
ch[old][which]=ch[x][which^1];
f[ ch[old][which] ]=old;
ch[x][which^1]=old;
f[old]=x;
update(old);
update(x);
}
inline void splay(int x){
int temp=0;
strack[++temp]=x;
for (int i=x; !Is_Root(i); i=f[i])
strack[++temp]=f[i];
for (int i=temp;i>=1;--i)
pushdown(strack[i]);
for (int fa; !Is_Root(x); rotate(x))
if (!Is_Root(fa=f[x]))
rotate( (get(x)==get(fa)) ?fa:x );
}
inline void Access(int x){
int t=0;
for (; x; t=x,x=f[x]){
splay(x);
ch[x][1]=t;
update(x);//
}
}
inline void Reverse(int x){
Access(x);
splay(x);
reverse[x]^=1;
}
inline void Link(int x,int y){
Reverse(x);
f[x]=y;
splay(x);
}
inline void Cut(int x,int y){
Reverse(x);
Access(y);
splay(y);
ch[y][0]=f[x]=0;
}
inline void Add(int x,int y,int z){
Reverse(x);
Access(y);
splay(y);
mark(y,z,1);
}
inline void Mul(int x,int y,int z){
Reverse(x);
Access(y);
splay(y);
mark(y,0,z);
}
inline int Query(int x,int y){
Reverse(x);
Access(y);
splay(y);
return sum[y];
}
int main(){
// freopen("input.txt","r",stdin);
scanf("%d%d",&n,&q);
for (int i=1;i<=n;++i)
key[i]=mul[i]=1;
for (int i=1;iscanf("%d%d",&x,&y);
Link(x,y);
}
for (int i=1;i<=q;++i){
char cc=getchar();
while (cc!='+'&&cc!='-'&&cc!='*'&&cc!='/')
cc=getchar();
if (cc=='+'){
scanf("%d%d%d",&u,&v,&c);
Add(u,v,c);
}
if (cc=='-'){
scanf("%d%d%d%d",&u1,&v1,&u2,&v2);
Cut(u1,v1);
Link(u2,v2);
}
if (cc=='*'){
scanf("%d%d%d",&u,&v,&c);
Mul(u,v,c);
}
if (cc=='/'){
scanf("%d%d",&u,&v);
int ans=Query(u,v);
printf("%d
",ans);
}
}
}
총결산
판자 는 잘 다듬어야 하고, 손 의 잔해 를 막아야 한다
그러나 판자만 익혀도 소용없다 = 이런 특수한 처리 방식에 대해 스스로 생각해 낼 수 있을까?
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
49일차 - 2022.04.20Baekjoon에서 문제풀이 1) 문제 : 첫째 줄에는 별 1개, 둘째 줄에는 별 2개, N번째 줄에는 별 N개를 찍는 문제/ 첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다. 첫째 줄부터 N번째 줄까지 차례대로 별...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.