From 8d11c6c8213f46f0fa19826917c255edd5d43cb1 Mon Sep 17 00:00:00 2001 From: mzuenni Date: Sun, 28 Jul 2024 22:54:40 +0200 Subject: Test (#4) * update * moved content in subdir * rename file * add test setup * add test setup * add github action * automaticly test all cpp files * timeout after 10s * setulimit and dont zero memory * test build pdf * install latexmk * update * update * ngerman * fonts * removed old code * add first test * added tests * test in sorted order * more tests * simplified test * more tests * fix suffix tree * fixes and improvements * done ust lst directly * fix swap * add links to pdf * fix constants * add primorial * add comment * various improvements * more tests * added missing stuf * more tests * fix tests * more tests * more tests * more tests * fix recursion? * test trie * more tests * only use python temporarily for listings * only use python temporarily for listings * more tests * fix longestCommonSubstring * more tests * more tests * made code more similiar * fix? * more tests * more tests * more tests * add ahoCorasick test + limit 4GB stack size * more tests * fix test * add additional test * more tests * more tests * fix? * better fix * fix virtual tree * more tests * more tests * recursive closest pair * more tests * decrease limit * new tests * more tests * fix name * more tests * add test * new test * more tests * more tests * more tests * more tests * new test and content * new code * new code * larger tests * fix and test * new test * new test * update pdf * remove comments * new test * more tests * more testcases * more tests * increased limit * more tests * more tests * more tests * new tests * more tests * shortened code * new test * add basic tests for bigint * more tests * removed old files * new test * ignore some files * more auto more ccw * fix test * more tests * fix * new tests * more tests * more tests * stronger test * actually verify delaunay... * more tests * fix header * more tests * run tests parallel? * test parralel? * add --missing * separate workflows * test * is the pdf checked? * separate workflows * fix workflow * more workflows --------- Co-authored-by: Yidi --- content/datastructures/LCT.cpp | 178 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 178 insertions(+) create mode 100644 content/datastructures/LCT.cpp (limited to 'content/datastructures/LCT.cpp') diff --git a/content/datastructures/LCT.cpp b/content/datastructures/LCT.cpp new file mode 100644 index 0000000..c1dd278 --- /dev/null +++ b/content/datastructures/LCT.cpp @@ -0,0 +1,178 @@ +constexpr ll queryDefault = 0; +constexpr ll updateDefault = 0; + +ll _modify(ll x, ll y) { + return x + y; +} + +ll _query(ll x, ll y) { + return x + y; +} + +ll _update(ll delta, int length) { + if (delta == updateDefault) return updateDefault; + //ll result = delta + //for (int i=1; ileft != this && + parent->right != this); + } + + void push() { + if (revert) { + revert = false; + swap(left, right); + if (left) left->revert ^= 1; + if (right) right->revert ^= 1; + } + nodeValue = joinValueDelta(nodeValue, delta); + subTreeValue = joinValueDelta(subTreeValue, + _update(delta, size)); + if (left) left->delta = joinDeltas(left->delta, delta); + if (right) right->delta = joinDeltas(right->delta, delta); + delta = updateDefault; + } + + ll getSubtreeValue() { + return joinValueDelta(subTreeValue, _update(delta, size)); + } + + void update() { + subTreeValue = joinValueDelta(nodeValue, delta); + size = 1; + if (left) { + subTreeValue = _query(subTreeValue, + left->getSubtreeValue()); + size += left->size; + } + if (right) { + subTreeValue = _query(subTreeValue, + right->getSubtreeValue()); + size += right->size; + }} + }; + + vector nodes; + + LCT(int n) : nodes(n) { + for (int i = 0; i < n; i++) nodes[i].id = i; + } + + void connect(Node* ch, Node* p, int isLeftChild) { + if (ch) ch->parent = p; + if (isLeftChild >= 0) { + if (isLeftChild) p->left = ch; + else p->right = ch; + }} + + void rotate(Node* x) { + Node* p = x->parent; + Node* g = p->parent; + bool isRootP = p->isRoot(); + bool leftChildX = (x == p->left); + + connect(leftChildX ? x->right : x->left, p, leftChildX); + connect(p, x, !leftChildX); + connect(x, g, isRootP ? -1 : p == g->left); + p->update(); + } + + void splay(Node* x) { + while (!x->isRoot()) { + Node* p = x->parent; + Node* g = p->parent; + if (!p->isRoot()) g->push(); + p->push(); + x->push(); + if (!p->isRoot()) rotate((x == p->left) == + (p == g->left) ? p : x); + rotate(x); + } + x->push(); + x->update(); + } + + Node* expose(Node* x) { + Node* last = nullptr; + for (Node* y = x; y; y = y->parent) { + splay(y); + y->left = last; + last = y; + } + splay(x); + return last; + } + + void makeRoot(Node* x) { + expose(x); + x->revert ^= 1; + } + + bool connected(Node* x, Node* y) { + if (x == y) return true; + expose(x); + expose(y); + return x->parent; + } + + void link(Node* x, Node* y) { + assert(!connected(x, y)); // not yet connected! + makeRoot(x); + x->parent = y; + } + + void cut(Node* x, Node* y) { + makeRoot(x); + expose(y); + //must be a tree edge! + assert(!(y->right != x || x->left != nullptr)); + y->right->parent = nullptr; + y->right = nullptr; + } + + Node* lca(Node* x, Node* y) { + assert(connected(x, y)); + expose(x); + return expose(y); + } + + ll query(Node* from, Node* to) { + makeRoot(from); + expose(to); + if (to) return to->getSubtreeValue(); + return queryDefault; + } + + void modify(Node* from, Node* to, ll delta) { + makeRoot(from); + expose(to); + to->delta = joinDeltas(to->delta, delta); + } +}; -- cgit v1.2.3