結果

問題 No.772 Dynamic Distance Sum
ユーザー dkim110807
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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; // rake
constexpr 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 vertices
void toggle() {
std::swap(left, right);
}
// rake r to l
static 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 vertices
Cluster dat;
Node *p, *q; // q is rake node (if exist)
Node *ch[2]; // ch[0] : left / ch[1] : right
bool 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; // identity
template<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 node
if (p->ch[1] == t) return 1; // if right node
return -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 nodes
inline 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 node
Cluster lf = l->dat;
if (t->q) { // if rake node exist
assert(l->vs[1] == t->q->vs[1]); // rake node must have same vertex
lf = Cluster::rake(l->dat, t->q->dat); // before compressing rake the cluster first
}
t->dat = Cluster::compress(lf, r->vs[0], r->dat); // then compress
l->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 vertices
t->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 vertices
inline 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 cluster
Node *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 cluster
void 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 w
Node *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 - dkim110807
void 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_edge
void 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 subtree
void set_subtree(Vertex *v) {
Node *t = expose(v);
}
// subtree of v when root
Cluster 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 left
right += c->dat.max.first - l->dat.weight;
c = l;
} else if ((r->dat.weight + right) * 2 > sum) { // follow right
left += 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 LOCAL
for (int i = 1; i <= n; i++) {
if (v == node[i]) {
std::clog << "Center : " << i << "\n";
break;
}
}
#endif
ll ans = tree.get_subtree(v).ans;
std::cout << ans << "\n";
last = (last + ans) % n;
}
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0