Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- class UFNode;
- class LNode {
- public:
- UFNode *Myval;
- LNode *Prev, *Next;
- LNode() :Prev(NULL), Next(NULL), Myval(NULL) {}
- LNode(LNode *pr, LNode *nx, UFNode *val) :Prev(pr), Next(nx), Myval(val) {}
- void Isolate() {
- if (this->Prev) {
- this->Prev->Next = this->Next;
- }
- this->Next->Prev = this->Prev;
- this->Prev = NULL;
- this->Next = new LNode(this, NULL, NULL);
- }
- static void Isolate(LNode* st, LNode* en);
- static void Insert(LNode* lis, LNode* nod);
- static void InsertChild(LNode* lis, UFNode* np, LNode* nod);
- static void InsertNL(LNode* lis, LNode* nod);
- static void Splice(LNode* pl, LNode* st, LNode* en);
- };
- class UFNode {
- public:
- UFNode* p;
- int rank = 0, elem, NLcou = 0, Ccou = 0;;
- LNode *NLnode, *DFSnode, *Cnode;
- LNode* Child, *Chlast, *ChNL, *ChNLlast;
- LNode *DFSlast;
- UFNode(int element) :elem(element), p(this) {
- DFSlast = new LNode;
- DFSnode = new LNode(NULL, DFSlast, this);
- NLnode = new LNode(NULL, new LNode, this);
- Cnode = new LNode(NULL, new LNode, this);
- DFSlast->Prev = DFSnode;
- Chlast = new LNode;
- Child = Chlast;
- ChNLlast = new LNode;
- ChNL = ChNLlast;
- p = this;
- }
- void Init() {
- DFSnode->Isolate();
- Cnode->Isolate();
- NLnode->Isolate();
- p = this;
- DFSnode->Prev = NULL;
- DFSnode->Next = DFSlast;
- DFSlast->Prev = DFSnode;
- ChNL = ChNLlast;
- ChNLlast->Prev = NULL;
- Cnode->Prev = NULL;
- NLnode->Prev = NULL;
- Child = Chlast;
- Chlast->Prev = NULL;
- rank = 0, NLcou = 0, Ccou = 0;
- }
- };
- void LNode::Isolate(LNode* st, LNode* en) {
- if (st->Prev) {
- st->Prev->Next = en->Next;
- }
- en->Next->Prev = st->Prev;
- st->Prev = NULL;
- en->Next = new LNode(en, NULL, NULL);
- }
- void LNode::Insert(LNode* lis, LNode* nod) {
- nod->Isolate();
- delete nod->Next;
- nod->Prev = lis->Prev;
- nod->Next = lis;
- if (lis->Prev)
- lis->Prev->Next = nod;
- lis->Prev = nod;
- }
- void LNode::InsertChild(LNode* lis, UFNode* np, LNode* nod) {
- if (nod->Myval != nod->Myval->p && !nod->Prev)
- nod->Myval->p->Child = nod->Next;
- Insert(lis, nod);
- if (!nod->Prev)
- np->Child = nod;
- if (nod->Myval != nod->Myval->p)
- nod->Myval->p->Ccou--;
- np->Ccou++;
- nod->Myval->p = np;
- }
- void LNode::Splice(LNode* pl, LNode* st, LNode* en) {
- Isolate(st, en);
- delete en->Next;
- en->Next = pl;
- st->Prev = pl->Prev;
- if (pl->Prev)
- pl->Prev->Next = st;
- pl->Prev = en;
- }
- class UnionFind_Deletion {
- public:
- int n, setcou = 0;
- vector<UFNode*> element;
- UnionFind_Deletion(int size) : n(size), element(n, NULL) {
- REP(i, n) {
- element[i] = new UFNode(i);
- }
- }
- bool isReduced(UFNode* root) {
- return !root->NLcou;
- }
- bool isRoot(UFNode* node) {
- return node->p == node;
- }
- void Unite(int a, int b) {// O(A(n))
- UFNode *ap = Find(a),
- *bp = Find(b);
- if (ap == bp)return;
- if (ap->rank < bp->rank) swap(ap, bp);
- else if (ap->rank == bp->rank && ap->Ccou < bp->Ccou) swap(ap, bp);
- if (isReduced(bp) && bp->Ccou < 4) {
- while (bp->Child->Myval != NULL) {
- bp->Child->Myval->rank = 0;
- LNode* buf = bp->Child->Next;
- LNode::Insert(ap->DFSnode->Next, bp->Child->Myval->DFSnode);
- LNode::InsertChild(ap->Child, ap, bp->Child);
- }
- bp->rank = 0;
- LNode::InsertChild(ap->Child, ap, bp->Cnode);
- LNode::Insert(ap->DFSnode->Next, bp->DFSnode);
- ap->rank = max(ap->rank, 1);
- }
- else {
- if (ap->rank == bp->rank)
- ap->rank++;
- LNode::InsertChild(ap->Child, ap, bp->Cnode);
- LNode::Insert(ap->ChNL, bp->NLnode);
- ap->ChNL = bp->NLnode;
- ap->NLcou++;
- LNode::Splice(ap->DFSnode->Next, bp->DFSnode, bp->DFSlast->Prev);
- }
- }
- UFNode* Relink(UFNode* a, bool LRB = 0) {
- UFNode *par = a->p;
- if (isRoot(par)) return a;
- if (par->Chlast->Prev && par->Chlast->Prev->Myval != a) {
- LNode::InsertChild(par->Cnode, par->p, a->Cnode);
- LNode::Splice(par->DFSnode->Next, a->DFSnode, a->Cnode->Next->Myval->DFSnode->Prev);
- }
- else {
- LNode::InsertChild(par->Cnode->Next, par->p, a->Cnode);
- }
- if (!par->Ccou) {
- par->rank = 0;
- if (isRoot(par->p)) {
- if (par->p->ChNL == par->NLnode)
- par->p->ChNL = par->NLnode->Next;
- par->NLnode->Isolate();
- par->p->NLcou--;
- if (!par->p->NLcou)
- par->p->rank = 1;
- }
- }
- if (!LRB && (par->Ccou > 0 && par->Ccou < 3)) {
- Relink(par->Child->Myval);
- }
- return a;
- }
- UFNode* Find(int a) {// O(A(n))
- UFNode* x = element[a];
- while (!isRoot(x->p)) {
- UFNode* t = x->p;
- Relink(x);
- x = t;
- }
- return x->p;
- }
- void Delete(int a) {// O(1)
- UFNode* x = element[a];
- UFNode *leaf = x, *par;
- if (x->Ccou) {
- if (isRoot(x) && isReduced(x)) {
- leaf = x->Child->Myval;
- }
- else {
- if (isRoot(x))
- leaf = x->DFSlast->Prev->Myval;
- else {
- if (x->Cnode->Next->Myval)
- leaf = x->Cnode->Next->Myval->DFSnode->Prev->Myval;
- else
- leaf = x->DFSnode->Prev->Myval;
- }
- }
- }
- swap(element[x->elem], element[leaf->elem]);
- swap(x->elem, leaf->elem);
- par = leaf->p;
- par->Ccou--;
- if (leaf->Cnode->Prev == NULL)
- par->Child = leaf->Cnode->Next;
- leaf->Init();
- if (!(isRoot(par) && isReduced(par))) {
- if (par->Ccou < 3)
- if (isRoot(par)) {
- UFNode* nl = par->NLnode->Myval;
- Relink(nl->Child->Next->Next->Myval, 1);
- Relink(nl->Child->Next->Myval, 1);
- Relink(nl->Child->Myval);
- }
- else {
- Relink(par->Child->Next->Myval, 1);
- Relink(par->Child->Myval);
- }
- }
- if (isRoot(par) && isReduced(par))
- par->rank = 1;
- }
- };
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement