daily pastebin goal
10%
SHARE
TWEET

Untitled

Moyashi_senpai May 19th, 2017 130 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class UFNode;
  2. class LNode {
  3. public:
  4.     UFNode *Myval;
  5.     LNode *Prev, *Next;
  6.     LNode() :Prev(NULL), Next(NULL), Myval(NULL) {}
  7.     LNode(LNode *pr, LNode *nx, UFNode *val) :Prev(pr), Next(nx), Myval(val) {}
  8.     void Isolate() {
  9.         if (this->Prev) {
  10.             this->Prev->Next = this->Next;
  11.         }
  12.         this->Next->Prev = this->Prev;
  13.         this->Prev = NULL;
  14.         this->Next = new LNode(this, NULL, NULL);
  15.     }
  16.  
  17.     static void Isolate(LNode* st, LNode* en);
  18.     static void Insert(LNode* lis, LNode* nod);
  19.     static void InsertChild(LNode* lis, UFNode* np, LNode* nod);
  20.     static void InsertNL(LNode* lis, LNode* nod);
  21.     static void Splice(LNode* pl, LNode* st, LNode* en);
  22. };
  23.  
  24. class UFNode {
  25. public:
  26.     UFNode* p;
  27.     int rank = 0, elem, NLcou = 0, Ccou = 0;;
  28.     LNode *NLnode, *DFSnode, *Cnode;
  29.     LNode* Child, *Chlast, *ChNL, *ChNLlast;
  30.     LNode *DFSlast;
  31.  
  32.     UFNode(int element) :elem(element), p(this) {
  33.         DFSlast = new LNode;
  34.         DFSnode = new LNode(NULL, DFSlast, this);
  35.         NLnode = new LNode(NULL, new LNode, this);
  36.         Cnode = new LNode(NULL, new LNode, this);
  37.  
  38.         DFSlast->Prev = DFSnode;
  39.         Chlast = new LNode;
  40.         Child = Chlast;
  41.         ChNLlast = new LNode;
  42.         ChNL = ChNLlast;
  43.         p = this;
  44.     }
  45.  
  46.     void Init() {
  47.         DFSnode->Isolate();
  48.         Cnode->Isolate();
  49.         NLnode->Isolate();
  50.         p = this;
  51.         DFSnode->Prev = NULL;
  52.         DFSnode->Next = DFSlast;
  53.         DFSlast->Prev = DFSnode;
  54.         ChNL = ChNLlast;
  55.         ChNLlast->Prev = NULL;
  56.         Cnode->Prev = NULL;
  57.         NLnode->Prev = NULL;
  58.         Child = Chlast;
  59.         Chlast->Prev = NULL;
  60.         rank = 0, NLcou = 0, Ccou = 0;
  61.     }
  62. };
  63.  
  64. void LNode::Isolate(LNode* st, LNode* en) {
  65.     if (st->Prev) {
  66.         st->Prev->Next = en->Next;
  67.     }
  68.  
  69.     en->Next->Prev = st->Prev;
  70.     st->Prev = NULL;
  71.     en->Next = new LNode(en, NULL, NULL);
  72. }
  73. void LNode::Insert(LNode* lis, LNode* nod) {
  74.     nod->Isolate();
  75.     delete nod->Next;
  76.  
  77.     nod->Prev = lis->Prev;
  78.     nod->Next = lis;
  79.     if (lis->Prev)
  80.         lis->Prev->Next = nod;
  81.     lis->Prev = nod;
  82. }
  83. void LNode::InsertChild(LNode* lis, UFNode* np, LNode* nod) {
  84.     if (nod->Myval != nod->Myval->p && !nod->Prev)
  85.         nod->Myval->p->Child = nod->Next;
  86.     Insert(lis, nod);
  87.     if (!nod->Prev)
  88.         np->Child = nod;
  89.     if (nod->Myval != nod->Myval->p)
  90.         nod->Myval->p->Ccou--;
  91.     np->Ccou++;
  92.     nod->Myval->p = np;
  93. }
  94. void LNode::Splice(LNode* pl, LNode* st, LNode* en) {
  95.     Isolate(st, en);
  96.     delete en->Next;
  97.     en->Next = pl;
  98.     st->Prev = pl->Prev;
  99.     if (pl->Prev)
  100.         pl->Prev->Next = st;
  101.     pl->Prev = en;
  102. }
  103.  
  104. class UnionFind_Deletion {
  105. public:
  106.     int n, setcou = 0;
  107.     vector<UFNode*> element;
  108.  
  109.     UnionFind_Deletion(int size) : n(size), element(n, NULL) {
  110.         REP(i, n) {
  111.             element[i] = new UFNode(i);
  112.         }
  113.     }
  114.     bool isReduced(UFNode* root) {
  115.         return !root->NLcou;
  116.     }
  117.     bool isRoot(UFNode* node) {
  118.         return node->p == node;
  119.     }
  120.  
  121.     void Unite(int a, int b) {// O(A(n))
  122.         UFNode *ap = Find(a),
  123.             *bp = Find(b);
  124.         if (ap == bp)return;
  125.         if (ap->rank < bp->rank) swap(ap, bp);
  126.         else if (ap->rank == bp->rank && ap->Ccou < bp->Ccou) swap(ap, bp);
  127.  
  128.         if (isReduced(bp) && bp->Ccou < 4) {
  129.  
  130.             while (bp->Child->Myval != NULL) {
  131.                 bp->Child->Myval->rank = 0;
  132.                 LNode* buf = bp->Child->Next;
  133.                 LNode::Insert(ap->DFSnode->Next, bp->Child->Myval->DFSnode);
  134.                 LNode::InsertChild(ap->Child, ap, bp->Child);
  135.             }
  136.  
  137.             bp->rank = 0;
  138.             LNode::InsertChild(ap->Child, ap, bp->Cnode);
  139.             LNode::Insert(ap->DFSnode->Next, bp->DFSnode);
  140.             ap->rank = max(ap->rank, 1);
  141.         }
  142.         else {
  143.             if (ap->rank == bp->rank)
  144.                 ap->rank++;
  145.             LNode::InsertChild(ap->Child, ap, bp->Cnode);
  146.             LNode::Insert(ap->ChNL, bp->NLnode);
  147.             ap->ChNL = bp->NLnode;
  148.             ap->NLcou++;
  149.  
  150.  
  151.             LNode::Splice(ap->DFSnode->Next, bp->DFSnode, bp->DFSlast->Prev);
  152.         }
  153.     }
  154.  
  155.     UFNode* Relink(UFNode* a, bool LRB = 0) {
  156.         UFNode *par = a->p;
  157.         if (isRoot(par)) return a;
  158.         if (par->Chlast->Prev && par->Chlast->Prev->Myval != a) {
  159.             LNode::InsertChild(par->Cnode, par->p, a->Cnode);
  160.             LNode::Splice(par->DFSnode->Next, a->DFSnode, a->Cnode->Next->Myval->DFSnode->Prev);
  161.         }
  162.         else {
  163.             LNode::InsertChild(par->Cnode->Next, par->p, a->Cnode);
  164.         }
  165.  
  166.         if (!par->Ccou) {
  167.             par->rank = 0;
  168.             if (isRoot(par->p)) {
  169.                 if (par->p->ChNL == par->NLnode)
  170.                     par->p->ChNL = par->NLnode->Next;
  171.                 par->NLnode->Isolate();
  172.                 par->p->NLcou--;
  173.                 if (!par->p->NLcou)
  174.                     par->p->rank = 1;
  175.             }
  176.  
  177.         }
  178.         if (!LRB && (par->Ccou > 0 && par->Ccou < 3)) {
  179.             Relink(par->Child->Myval);
  180.         }
  181.         return a;
  182.     }
  183.  
  184.     UFNode* Find(int a) {// O(A(n))
  185.         UFNode* x = element[a];
  186.         while (!isRoot(x->p)) {
  187.             UFNode* t = x->p;
  188.             Relink(x);
  189.             x = t;
  190.         }
  191.         return x->p;
  192.     }
  193.  
  194.     void Delete(int a) {// O(1)
  195.         UFNode* x = element[a];
  196.         UFNode *leaf = x, *par;
  197.  
  198.         if (x->Ccou) {
  199.             if (isRoot(x) && isReduced(x)) {
  200.                 leaf = x->Child->Myval;
  201.             }
  202.             else {
  203.                 if (isRoot(x))
  204.                     leaf = x->DFSlast->Prev->Myval;
  205.                 else {
  206.                     if (x->Cnode->Next->Myval)
  207.                         leaf = x->Cnode->Next->Myval->DFSnode->Prev->Myval;
  208.                     else
  209.                         leaf = x->DFSnode->Prev->Myval;
  210.                 }
  211.             }
  212.         }
  213.         swap(element[x->elem], element[leaf->elem]);
  214.         swap(x->elem, leaf->elem);
  215.  
  216.         par = leaf->p;
  217.         par->Ccou--;
  218.         if (leaf->Cnode->Prev == NULL)
  219.             par->Child = leaf->Cnode->Next;
  220.  
  221.         leaf->Init();
  222.  
  223.         if (!(isRoot(par) && isReduced(par))) {
  224.             if (par->Ccou < 3)
  225.                 if (isRoot(par)) {
  226.                     UFNode* nl = par->NLnode->Myval;
  227.  
  228.                     Relink(nl->Child->Next->Next->Myval, 1);
  229.                     Relink(nl->Child->Next->Myval, 1);
  230.                     Relink(nl->Child->Myval);
  231.                 }
  232.                 else {
  233.                     Relink(par->Child->Next->Myval, 1);
  234.                     Relink(par->Child->Myval);
  235.                 }
  236.         }
  237.         if (isRoot(par) && isReduced(par))
  238.             par->rank = 1;
  239.     }
  240.  
  241.  
  242. };
RAW Paste Data
Top