(RE) luogu P3690 【模板】Link Cut Tree

时间:2022-11-04 21:35:26

二次联通门 : luogu P3690 【模板】Link Cut Tree

莫名RE第8个点。。。。如果有dalao帮忙查错的话万分感激

#include <cstdio>
#include <iostream> #define Max 4000002 void read (int &now)
{
now = ;
bool temp = false;
register char word = getchar ();
while (word < '' || word > '')
{
if (word == '-')
temp = false;
word = getchar ();
}
while (word >= '' && word <= '')
{
now = now * + word - '';
word = getchar ();
}
if (temp)
now = -now;
} int N, M; struct S_D
{
S_D *child[]; S_D *father; int key;
int number; int Flandre;
S_D (int __x) : number (__x)
{
child[] = child[] = NULL; father = NULL;
key = __x;
Flandre = ;
} inline void Updata ()
{
/*
this->key ^= this->number;
if (this->child[0])
this->key ^= this->child[0]->key;
if (this->child[1])
this->key ^= this->child[1]->key;
*/
if (this->child[] != NULL && this->child[] != NULL)
this->key = this->child[]->key ^ this->child[]->key ^ this->number;
else if (this->child[] != NULL && this->child[] == NULL)
this->key = this->child[]->key ^ this->number;
else if (this->child[] != NULL && this->child[] == NULL)
this->key = this->child[]->key ^ this->number;
else
this->key = this->number;
//this->key = this->child[0]->key ^ this->number ^ this->child[1]->key;
return ;
} inline void Down ()
{
if (!this->Flandre)
return ;
std :: swap (this->child[], this->child[]);
if (this->child[])
this->child[]->Flandre ^= ;
if (this->child[])
this->child[]->Flandre ^= ;
this->Flandre = ;
} inline int Get_Pos ()
{
return this->father->child[] == this;
} inline int Is_Root ()
{
return !(this->father) || (this->father->child[] != this && this->father->child[] != this);
} }; S_D *data[Max];
S_D *node[Max]; class L_T
{ private : inline void Rotate (S_D *now)
{
int pos = now->Get_Pos () ^ ;
S_D *Father = now->father;
Father->child[pos ^ ] = now->child[pos];
if (now->child[pos])
now->child[pos]->father = Father;
now->father = Father->father;
if (!Father->Is_Root ())
now->father->child[Father->Get_Pos ()] = now;
Father->father = now;
now->child[pos] = Father;
Father->Updata ();
now->Updata ();
} inline void Splay (S_D *now)
{
int pos = ;
for (S_D *Father = now; ; Father = Father->father)
{
data[++pos] = Father;
if (Father->Is_Root ())
break;
}
for (; pos >= ; -- pos)
data[pos]->Down ();
for (; !now->Is_Root (); Rotate (now))
if (!now->father->Is_Root ())
Rotate (now->Get_Pos () == now->father->Get_Pos () ? now->father : now);
now->Updata ();
} inline void Access (S_D *now)
{
for (S_D *Pre = NULL; now; Pre = now, now = now->father)
{
Splay (now);
now->child[] = Pre;
now->Updata ();
}
} inline void Make_Root (S_D *now)
{
Access (now);
Splay (now);
now->Flandre ^= ;
} public : inline void Cut (S_D *x, S_D *y)
{
Make_Root (x);
Access (y);
Splay (y);
x->father = y->child[] = NULL;
y->Updata ();
} inline void Link (S_D *x, S_D *y)
{
Make_Root (x);
x->father = y;
} inline void Split (S_D *x, S_D *y)
{
Make_Root (x);
Access (y);
Splay (y);
} inline bool Find (S_D *x, S_D *y)
{
while (x->child[])
x = x->child[];
while (y->child[])
y = y->child[];
return x == y;
} inline int Query (int x, int y)
{
Split (node[x], node[y]);
return node[y]->key;
} inline void Change (int x, int y)
{
Access (node[x]);
Splay (node[x]);
node[x]->number = y;
node[x]->Updata ();
}
}; L_T Make; int main (int argc, char *argv[])
{
read (N);
read (M);
for (register int i = , x; i < N; i ++)
{
read (x);
node[i] = new S_D (x);
}
int x, y, type;
for (; M --; )
{
read (type);
read (x);
read (y);
if (type == )
printf ("%d\n", Make.Query (-- x, -- y));
else if (type == )
{
x --;
y --;
if (!Make.Find (node[x], node[y]))
Make.Link (node[x], node[y]);
}
else if (type == )
{
x --;
y --;
if (Make.Find (node[x], node[y]))
Make.Cut (node[x], node[y]);
}
else
Make.Change (-- x, y);
}
return ;
}