結果
問題 | No.772 Dynamic Distance Sum |
ユーザー |
|
提出日時 | 2024-07-31 22:34:37 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,268 ms / 5,000 ms |
コード長 | 18,881 bytes |
コンパイル時間 | 2,960 ms |
コンパイル使用メモリ | 224,800 KB |
実行使用メモリ | 54,804 KB |
最終ジャッジ日時 | 2024-07-31 22:35:03 |
合計ジャッジ時間 | 26,003 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>using ll = long long;constexpr std::size_t MAX = 100'001;struct Vertex {void *handle;int v;Vertex(int v = 0) : handle(nullptr), v(v) {}};struct Cluster {/** chd : count of nodes in boundary vertices* left : sum of vertices from left* right : sum of vertices from right*/ll len, weight, chd, ans, left, right;std::pair<ll, Vertex *> max; // rakeconstexpr friend bool operator<(const std::pair<ll, Vertex *> &a, const std::pair<ll, Vertex *> &b) {return a.first < b.first;}Cluster(int len = 0) : len(len), weight(0), chd(0), ans(0), left(0), right(0) {}// swap boundary verticesvoid toggle() {std::swap(left, right);}// rake r to lstatic Cluster rake(const Cluster &l, const Cluster &r) {Cluster c;c.len = l.len;c.weight = l.weight, c.chd = l.chd + r.chd + r.weight;c.ans = l.right + r.right;c.left = l.left + r.right, c.right = l.right + r.right;c.max = std::max(l.max, r.max);return c;}static Cluster compress(const Cluster &l, Vertex *v, const Cluster &r) {Cluster c;c.len = l.len + r.len;c.weight = l.weight + l.chd + v->v + r.chd + r.weight;c.ans = l.right + r.left;c.left = l.left + r.left + (r.weight + l.chd + r.chd + v->v) * l.len;c.right = r.right + l.right + (l.weight + l.chd + r.chd + v->v) * r.len;c.max = {c.weight, v};return c;}};/** Original code from https://beet-aizu.github.io/library/toptree/toptree.cpp* - edit (including annotation) : dkim110807*/template<std::size_t N = MAX>struct TopTree {// each type of node can be compress, rake, edge (only if leaf node)enum Type {Compress, Rake, Edge};struct Node {Vertex *vs[2]; // boundary verticesCluster dat;Node *p, *q; // q is rake node (if exist)Node *ch[2]; // ch[0] : left / ch[1] : rightbool rev, guard;Type type;Node() : p(nullptr), q(nullptr), rev(false), guard(false) {}};inline static std::array<Vertex, 2 * N> pool_vertex;inline static std::size_t ptr_vertex = 0;inline static std::array<Node, 4 * N> pool_node;inline static std::size_t ptr_node = 0;Cluster id; // identitytemplate<typename ...Args>inline Vertex *create(Args ...args) {auto t = &pool_vertex[ptr_vertex++];auto dummy = &pool_vertex[ptr_vertex++];*t = Vertex(std::forward<Args>(args)...);link(t, id, dummy);return t;}Node *recycle = nullptr;inline void dispose_node(Node *t) {t->p = recycle;recycle = t;}inline Node *get_new_node() {if (recycle) return new(std::exchange(recycle, recycle->p)) Node;return &(pool_node[ptr_node++]);}inline Node *edge(Vertex *u, Cluster w, Vertex *v) {auto t = get_new_node();t->vs[0] = u, t->vs[1] = v;t->dat = w;t->type = Type::Edge;return pushup(t);}inline Node *compress(Node *l, Node *r) {auto t = get_new_node();t->ch[0] = l, t->ch[1] = r;t->type = Type::Compress;return pushup(t);}inline Node *rake(Node *l, Node *r) {auto t = get_new_node();t->ch[0] = l, t->ch[1] = r;t->type = Type::Rake;return pushup(t);}int parent_dir(Node *t) {Node *p = t->p;if (!p || p->guard) return -1; // if root or guard (when we meet guard nodes we stop splaying)if (p->ch[0] == t) return 0; // if left nodeif (p->ch[1] == t) return 1; // if right nodereturn -1;}int parent_dir_ignore_guard(Node *t) {Node *p = t->p;if (!p) return -1;if (p->ch[0] == t) return 0;if (p->ch[1] == t) return 1;return -1;}// get data from child nodesinline Node *pushup(Node *const t) {Node *const l = t->ch[0];Node *const r = t->ch[1];if (t->type == Type::Compress) {assert(l->vs[1] == r->vs[0]);t->vs[0] = l->vs[0], t->vs[1] = r->vs[1]; // left node <-- compress --> right nodeCluster lf = l->dat;if (t->q) { // if rake node existassert(l->vs[1] == t->q->vs[1]); // rake node must have same vertexlf = Cluster::rake(l->dat, t->q->dat); // before compressing rake the cluster first}t->dat = Cluster::compress(lf, r->vs[0], r->dat); // then compressl->vs[1]->handle = t;}if (t->type == Type::Rake) {propagate(t);assert(l->vs[1] == r->vs[1]);t->vs[0] = l->vs[0];t->vs[1] = l->vs[1];t->dat = Cluster::rake(l->dat, r->dat); // rake r to l} else {if (!t->p) { // root cluster is handle for its boundary verticest->vs[0]->handle = t;t->vs[1]->handle = t;} else if (t->p->type == Type::Compress) {if (parent_dir(t) == -1)t->vs[0]->handle = t;} else if (t->p->type == Type::Rake) {t->vs[0]->handle = t;}}return t;}// reverse the boundary verticesinline void toggle(Node *t) {if (t->type == Type::Edge) {std::swap(t->vs[0], t->vs[1]);t->dat.toggle();} else if (t->type == Type::Compress) {std::swap(t->vs[0], t->vs[1]);t->dat.toggle();t->rev ^= true; // lazy propagation} else if (t->type == Type::Rake) {} else std::abort(); // something wrong}inline void propagate(Node *t) {if (t->type == Type::Compress) {if (t->rev) {assert(t->ch[0] && t->ch[1]);std::swap(t->ch[0], t->ch[1]);toggle(t->ch[0]), toggle(t->ch[1]);t->rev = false;}}// Todo. lazy propagation here}void set_toggle(Node *v) {toggle(v);propagate(v);}void pushdown(Node *t) {if (!t) return;pushdown(t->p);propagate(t);}void rotate(Node *t, Node *x, std::size_t dir) {Node *y = x->p;int par = parent_dir_ignore_guard(x);propagate(t->ch[dir]);x->ch[dir ^ 1] = t->ch[dir];t->ch[dir]->p = x;t->ch[dir] = x;x->p = t;t->p = y;if (par != -1) y->ch[par] = t;else if (y && y->type == Type::Compress) y->q = t;pushup(x);pushup(t);if (y && !y->guard) pushup(y);}void splay(Node *t) {if (t->type == Type::Edge) return;// assert(t->type != Type::Edge);propagate(t);while (parent_dir(t) != -1) {Node *q = t->p;if (q->type != t->type) break;if (parent_dir(q) != -1 && q->p && q->p->type == q->type) {Node *r = q->p;if (r->p) propagate(r->p);propagate(r);propagate(q);propagate(t);int qt_dir = parent_dir(t), rq_dir = parent_dir(q);if (rq_dir == qt_dir) {rotate(q, r, rq_dir ^ 1);rotate(t, q, qt_dir ^ 1);} else {rotate(t, q, qt_dir ^ 1);rotate(t, r, rq_dir ^ 1);}} else {if (q->p) propagate(q->p);propagate(q);propagate(t);int qt_dir = parent_dir(t);rotate(t, q, qt_dir ^ 1);}}}// expose node to root clusterNode *expose(Node *t) {pushdown(t);while (true) {assert(t->type != Type::Rake);if (t->type == Type::Compress) splay(t);Node *n = nullptr;{Node *p = t->p;if (!p) break;if (p->type == Type::Rake) {propagate(p);splay(p);n = p->p;}if (p->type == Type::Compress) {propagate(p);if (p->guard && parent_dir_ignore_guard(t) != -1) break;n = p;}}splay(n);int dir = parent_dir_ignore_guard(n);if (dir == -1 || n->p->type == Type::Rake) dir = 0;Node *const c = n->ch[dir];if (dir == 1) {set_toggle(c);set_toggle(t);}int n_dir = parent_dir(t);if (n_dir != -1) {Node *const r = t->p;propagate(c);propagate(r);r->ch[n_dir] = c;c->p = r;n->ch[dir] = t;t->p = n;pushup(c);pushup(r);pushup(t);pushup(n);splay(r);} else {propagate(c);n->q = c;c->p = n;n->ch[dir] = t;t->p = n;pushup(c);pushup(t);pushup(n);}if (t->type == Type::Edge) t = n;}return t;}Node *expose(Vertex *v) {return expose((Node *) (v->handle));}// expose path u...v to root clustervoid soft_expose(Vertex *u, Vertex *v) {pushdown((Node *) u->handle), pushdown((Node *) v->handle);Node *rt = expose(u);if (u->handle == v->handle) {if (rt->vs[1] == u || rt->vs[0] == v) set_toggle(rt);return;}rt->guard = true;Node *soft = expose(v);rt->guard = false;pushup(rt);if (parent_dir(soft) == 0) set_toggle(rt);}void bring(Node *rt) {Node *rk = rt->q;if (!rk) {Node *ll = rt->ch[0];dispose_node(ll->p);ll->p = nullptr;pushup(ll);} else if (rk->type == Type::Compress || rk->type == Type::Edge) {Node *nr = rk;set_toggle(nr);rt->ch[1] = nr;nr->p = rt;rt->q = nullptr;pushup(nr);pushup(rt);} else if (rk->type == Type::Rake) {propagate(rk);while (rk->ch[1]->type == Type::Rake) {propagate(rk->ch[1]);rk = rk->ch[1];}pushdown(rk);rt->guard = true;splay(rk);rt->guard = false;Node *ll = rk->ch[0];Node *rr = rk->ch[1];propagate(ll);set_toggle(rr);rt->ch[1] = rr;rr->p = rt;rt->q = ll;ll->p = rt;dispose_node(rk);pushup(ll);pushup(rr);pushup(rt);}}// link u-v with data wNode *link(Vertex *u, Cluster w, Vertex *v) {// single vertex doesn't have handle (so just link it)if (!u->handle && !v->handle) return edge(u, w, v);Node *nnu = (Node *) u->handle;Node *nnv = (Node *) v->handle;Node *ee = edge(u, w, v);Node *ll;assert(nnv);Node *vv = expose(nnv);propagate(vv);if (vv->vs[1] == v) set_toggle(vv);if (vv->vs[0] == v) {Node *nv = compress(ee, vv);ee->p = nv;pushup(ee);vv->p = nv;pushup(vv);pushup(nv);ll = nv;} else {Node *nv = vv;Node *ch = nv->ch[0];propagate(ch);nv->ch[0] = ee;ee->p = nv;pushup(ee);Node *bt = nv->q;Node *rk;if (bt) {propagate(bt);rk = rake(bt, ch);bt->p = rk;ch->p = rk;pushup(bt);pushup(ch);} else {rk = ch;}nv->q = rk;rk->p = nv;pushup(rk);pushup(nv);ll = nv;}assert(nnu);Node *uu = expose(nnu);propagate(uu);if (uu->vs[0] == u) set_toggle(uu);if (uu->vs[1] == u) {Node *tp = compress(uu, ll);uu->p = tp;ll->p = tp;pushup(uu);pushup(ll);pushup(tp);} else {Node *nu = uu;Node *ch = nu->ch[1];toggle(ch);propagate(ch);nu->ch[1] = ll;ll->p = nu;pushup(ll);Node *al = nu->q;Node *rk;if (al) {propagate(al);rk = rake(al, ch);al->p = rk;ch->p = rk;pushup(al);pushup(ch);} else {rk = ch;}nu->q = rk;rk->p = nu;pushup(rk);pushup(nu);}return ee;}// cut between u-v (it must exist)void cut(Vertex *u, Vertex *v) {soft_expose(u, v);Node *rt = (Node *) u->handle;propagate(rt);Node *rr = rt->ch[1];rr->p = nullptr;set_toggle(rr);assert(rr->ch[1]->type == Type::Edge);dispose_node(rr->ch[1]);bring(rr);bring(rt);}Node *path(Vertex *u, Vertex *v) {assert(u != v);soft_expose(u, v);Node *rt = (Node *) u->handle;splay(rt);propagate(rt);propagate(rt->ch[1]);propagate(rt->ch[1]->ch[0]); // * propagate complete *return rt->ch[1]->ch[0];}void set_vertex(Vertex *u, Vertex v) {auto t = expose(u);// Todo.u->v = v.v;pushup(t);}// this must be edge - dkim110807void set_edge(Vertex *u, Vertex *v, const Cluster &w) {auto t = path(u, v);assert(t->type == Type::Edge);t->dat = w;while (t) pushup(t), t = t->p;}// Todo. lazy update here// If lazy is not required use set_edgevoid set_path(Vertex *u, Vertex *v, ll c) {Node *t = path(u, v);}Cluster get_path(Vertex *u, Vertex *v) {return path(u, v)->dat;}Cluster get_subtree(Vertex *v) {return expose(v)->dat;}// Todo. lazy update on subtreevoid set_subtree(Vertex *v) {Node *t = expose(v);}// subtree of v when rootCluster get_subtree(Vertex *root, Vertex *v) {if (root == v) return get_subtree(v);Node *t = path(root, v);Cluster res = t->p->ch[1]->dat;res.toggle();Node *rk = t->p->q;if (t->p->q) {assert(rk->vs[1] == t->p->ch[1]->vs[0]);res = Cluster::rake(res, rk->dat);}return res;}// I'm not sure with these things.. maybe wrong (MST accepted)void set_root(Vertex *root) {expose(root);Node *r = (Node *) root->handle;while (r->p) r = r->p;expose(r);assert(!r->p);}Node *get_root(Vertex *v) {Node *n = (Node *) v->handle;assert(n != nullptr);while (n->p) n = n->p;splay(n);return n;}};int main() {std::ios_base::sync_with_stdio(false);std::cin.tie(nullptr), std::cout.tie(nullptr);TopTree tree;int n, m;std::cin >> n >> m;std::vector<int> X(n + 1, 1);std::vector<Vertex *> node(n + 1);for (int i = 1; i <= n; i++) node[i] = tree.create(1); // initially all $X_[v} = 1$/** Non-local searching** Center* : Follow node having greater sum of weights or* : Follow node having less max distance*/auto center = [&](Vertex *v) -> Vertex * {using Node = decltype(tree)::Node;using Type = decltype(tree)::Type;Node *root = tree.expose(v);if (root->type == Type::Edge) return v;Node *c = root;ll left = 0, right = 0, sum = c->dat.weight;while (c->type == Type::Compress) {tree.propagate(c);Node *l = c->ch[0], *r = c->ch[1], *q = c->q;if ((l->dat.weight + left) * 2 > sum) { // follow leftright += c->dat.max.first - l->dat.weight;c = l;} else if ((r->dat.weight + right) * 2 > sum) { // follow rightleft += c->dat.max.first - r->dat.weight;c = r;} else if (q && (q->dat.max.first * 2) > sum) { // follow rake's max if rake exist/** c* / | \* / | \* / | \* left q right* follow 'q' -> every left become right*/right += left, left = 0;right += c->dat.max.first - q->dat.max.first;c = (Node *) q->dat.max.second->handle;} else {return c->dat.max.second;}}return nullptr;};ll last = 0;for (int op, a, b, c; m--;) {std::cin >> op;if (op == 1) {std::cin >> a >> b >> c;a = int((last + a - 1) % n + 1), b = int((last + b - 1) % n + 1);tree.link(node[a], c, node[b]);} else if (op == 2) {std::cin >> a >> b;a = int((last + a - 1) % n + 1), b = int((last + b - 1) % n + 1);tree.cut(node[a], node[b]);} else if (op == 3) {std::cin >> a;a = int((last + a - 1) % n + 1);X[a] = 1 - X[a];tree.set_vertex(node[a], X[a]);auto v = center(node[a]);#ifdef LOCALfor (int i = 1; i <= n; i++) {if (v == node[i]) {std::clog << "Center : " << i << "\n";break;}}#endifll ans = tree.get_subtree(v).ans;std::cout << ans << "\n";last = (last + ans) % n;}}}