結果
問題 | No.772 Dynamic Distance Sum |
ユーザー | tonegawa |
提出日時 | 2024-09-08 17:12:47 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 874 ms / 5,000 ms |
コード長 | 17,507 bytes |
コンパイル時間 | 2,448 ms |
コンパイル使用メモリ | 178,128 KB |
実行使用メモリ | 76,760 KB |
最終ジャッジ日時 | 2024-09-08 17:13:06 |
合計ジャッジ時間 | 19,458 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <iostream>#include <string>#include <vector>#include <array>#include <tuple>#include <stack>#include <queue>#include <deque>#include <algorithm>#include <set>#include <map>#include <unordered_set>#include <unordered_map>#include <bitset>#include <cmath>#include <functional>#include <cassert>#include <climits>#include <iomanip>#include <numeric>#include <memory>#include <random>#include <thread>#include <chrono>#define allof(obj) (obj).begin(), (obj).end()#define range(i, l, r) for(int i=l;i<r;i++)#define unique_elem(obj) obj.erase(std::unique(allof(obj)), obj.end())#define bit_subset(i, S) for(int i=S, zero_cnt=0;(zero_cnt+=i==S)<2;i=(i-1)&S)#define bit_kpop(i, n, k) for(int i=(1<<k)-1,x_bit,y_bit;i<(1<<n);x_bit=(i&-i),y_bit=i+x_bit,i=(!i?(1<<n):((i&~y_bit)/x_bit>>1)|y_bit))#define bit_kth(i, k) ((i >> k)&1)#define bit_highest(i) (i?63-__builtin_clzll(i):-1)#define bit_lowest(i) (i?__builtin_ctzll(i):-1)#define sleepms(t) std::this_thread::sleep_for(std::chrono::milliseconds(t))using ll = long long;using ld = long double;using ul = uint64_t;using pi = std::pair<int, int>;using pl = std::pair<ll, ll>;using namespace std;template<typename F, typename S>std::ostream &operator << (std::ostream &dest, const std::pair<F, S> &p) {dest << p.first << ' ' << p.second;return dest;}template<typename A, typename B>std::ostream &operator << (std::ostream &dest, const std::tuple<A, B> &t) {dest << std::get<0>(t) << ' ' << std::get<1>(t);return dest;}template<typename A, typename B, typename C>std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C> &t) {dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t);return dest;}template<typename A, typename B, typename C, typename D>std::ostream &operator << (std::ostream &dest, const std::tuple<A, B, C, D> &t) {dest << std::get<0>(t) << ' ' << std::get<1>(t) << ' ' << std::get<2>(t) << ' ' << std::get<3>(t);return dest;}template<typename T>std::ostream &operator << (std::ostream &dest, const std::vector<std::vector<T>> &v) {int sz = v.size();if (!sz) return dest;for (int i = 0; i < sz; i++) {int m = v[i].size();for (int j = 0; j < m; j++) dest << v[i][j] << (i != sz - 1 && j == m - 1 ? '\n' : ' ');}return dest;}template<typename T>std::ostream &operator << (std::ostream &dest, const std::vector<T> &v) {int sz = v.size();if (!sz) return dest;for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';dest << v[sz - 1];return dest;}template<typename T, size_t sz>std::ostream &operator << (std::ostream &dest, const std::array<T, sz> &v) {if (!sz) return dest;for (int i = 0; i < sz - 1; i++) dest << v[i] << ' ';dest << v[sz - 1];return dest;}template<typename T>std::ostream &operator << (std::ostream &dest, const std::set<T> &v) {for (auto itr = v.begin(); itr != v.end();) {dest << *itr;itr++;if (itr != v.end()) dest << ' ';}return dest;}template<typename T, typename E>std::ostream &operator << (std::ostream &dest, const std::map<T, E> &v) {for (auto itr = v.begin(); itr != v.end(); ) {dest << '(' << itr->first << ", " << itr->second << ')';itr++;if (itr != v.end()) dest << '\n';}return dest;}template<typename T>vector<T> make_vec(size_t sz, T val) { return std::vector<T>(sz, val); }template<typename T, typename... Tail>auto make_vec(size_t sz, Tail ...tail) {return std::vector<decltype(make_vec<T>(tail...))>(sz, make_vec<T>(tail...));}template<typename T>vector<T> read_vec(size_t sz) {std::vector<T> v(sz);for (int i = 0; i < (int)sz; i++) std::cin >> v[i];return v;}template<typename T, typename... Tail>auto read_vec(size_t sz, Tail ...tail) {auto v = std::vector<decltype(read_vec<T>(tail...))>(sz);for (int i = 0; i < (int)sz; i++) v[i] = read_vec<T>(tail...);return v;}// x / y以上の最小の整数ll ceil_div(ll x, ll y) {assert(y > 0);return (x + (x > 0 ? y - 1 : 0)) / y;}// x / y以下の最大の整数ll floor_div(ll x, ll y) {assert(y > 0);return (x + (x > 0 ? 0 : -y + 1)) / y;}void io_init() {std::cin.tie(nullptr);std::ios::sync_with_stdio(false);}#include <unistd.h>// サイズは空白や改行も含めた文字数template<int size_in = 1 << 25, int size_out = 1 << 25>struct fast_io {char ibuf[size_in], obuf[size_out];char *ip, *op;fast_io() : ip(ibuf), op(obuf) {int t = 0, k = 0;while ((k = read(STDIN_FILENO, ibuf + t, sizeof(ibuf) - t)) > 0) {t += k;}}~fast_io() {int t = 0, k = 0;while ((k = write(STDOUT_FILENO, obuf + t, op - obuf - t)) > 0) {t += k;}}long long in() {long long x = 0;bool neg = false;for (; *ip < '+'; ip++) ;if (*ip == '-'){ neg = true; ip++;}else if (*ip == '+') ip++;for (; *ip >= '0'; ip++) x = 10 * x + *ip - '0';if (neg) x = -x;return x;}unsigned long long inu64() {unsigned long long x = 0;for (; *ip < '+'; ip++) ;if (*ip == '+') ip++;for (; *ip >= '0'; ip++) x = 10 * x + *ip - '0';return x;}char in_char() {for (; *ip < '!'; ip++) ;return *ip++;}void out(long long x, char c = 0) {static char tmp[20];if (!x) {*op++ = '0';} else {int i;if (x < 0) {*op++ = '-';x = -x;}for (i = 0; x; i++) {tmp[i] = x % 10;x /= 10;}for (i--; i >= 0; i--) *op++ = tmp[i] + '0';}if (c) *op++ = c;}void outu64(unsigned long long x, char c = 0) {static char tmp[20];if (!x) {*op++ = '0';} else {int i;for (i = 0; x; i++) {tmp[i] = x % 10;x /= 10;}for (i--; i >= 0; i--) *op++ = tmp[i] + '0';}if (c) *op++ = c;}void out_char(char x, char c = 0){*op++ = x;if (c) *op++ = c;}long long memory_size() {return (long long)(size_in + size_out) * sizeof(char);}};template<typename W>struct centroid_dynamic {struct T {W distsum, distsum_rev, w, wsum, len, lensum;T() : distsum(0), distsum_rev(0), w(0), wsum(0), len(0), lensum(0) {}};struct U {W distsum, wsum;U() : distsum(0), wsum(0) {}};struct node;struct node_in {node_in *lch, *rch, *par;W wmax;node *c, *wmaxnode;node_in(node *_self) : lch(nullptr), rch(nullptr), par(nullptr), wmax(_self->x.wsum), c(_self), wmaxnode(_self) {}bool is_root() { return !par; }};struct node {node *lch, *rch, *par;bool _flip;T x;U y;node_in *lic, *lip;node() : lch(nullptr), rch(nullptr), par(nullptr), _flip(false), x(), y(), lic(nullptr), lip(nullptr) {}bool is_root() { return !par || (par->lch != this && par->rch != this); }};// 重みwの頂点static node *make_node(W w) {node *v = new node();v->x.w = v->x.wsum = w;return v;}// 長さlenの辺static node *make_edge(W len) {node *v = new node();v->x.len = v->x.lensum = len;return v;}static void update(node *v) {if (v->lch && v->lch->lip) std::swap(v->lip, v->lch->lip);if (v->rch && v->rch->lip) std::swap(v->lip, v->rch->lip);T lsum = (v->lch ? v->lch->x : T());T rsum = (v->rch ? v->rch->x : T());W a = lsum.distsum + lsum.lensum * v->x.w;W b = lsum.wsum + v->x.w;W c = lsum.lensum + v->x.len;W d = v->y.distsum + rsum.distsum;W e = v->y.wsum + rsum.wsum;v->x.distsum = a + d + c * e;v->x.distsum_rev = (rsum.distsum_rev + rsum.lensum * v->x.w) + (v->y.distsum + lsum.distsum_rev) + (rsum.lensum + v->x.len) * (v->y.wsum +lsum.wsum);v->x.wsum = b + e;v->x.lensum = c + rsum.lensum;}static void update(node_in *v) {v->wmax = v->c->x.wsum;v->wmaxnode = v->c;if (v->lch && v->wmax < v->lch->wmax) {v->wmax = v->lch->wmax;v->wmaxnode = v->lch->wmaxnode;}if (v->rch && v->wmax < v->rch->wmax) {v->wmax = v->rch->wmax;v->wmaxnode = v->rch->wmaxnode;}}static void push(node_in *v) {}static void flip(node *v) {v->_flip = !v->_flip;std::swap(v->x.distsum, v->x.distsum_rev);std::swap(v->lch, v->rch);}static void push(node *v) {if (v->_flip) {if (v->lch) flip(v->lch);if (v->rch) flip(v->rch);v->_flip = false;}}template<typename Node = node>static void splay(Node *v) {push(v);while (!v->is_root()) {Node *p = v->par;if (p->is_root()) {push(p), push(v);Node *pp = p->par;if(p->lch == v) {if ((p->lch = v->rch)) p->lch->par = p;update(p);v->rch = p;p->par = v;update(v);} else {if ((p->rch = v->lch)) p->rch->par = p;update(p);v->lch = p;p->par = v;update(v);}v->par = pp;} else {Node *pp = p->par;Node *ppp = pp->par;push(pp), push(p), push(v);if (pp->lch == p) {if (p->lch == v) {if ((pp->lch = p->rch)) pp->lch->par = pp;update(pp);p->rch = pp;pp->par = p;if ((p->lch = v->rch)) p->lch->par = p;update(p);v->rch = p;p->par = v;update(v);} else {if ((p->rch = v->lch)) p->rch->par = p;update(p);if ((pp->lch = v->rch)) pp->lch->par = pp;update(pp);v->lch = p;v->rch = pp;p->par = pp->par = v;update(v);}} else {if(p->rch == v) {if ((pp->rch = p->lch)) pp->rch->par = pp;update(pp);p->lch = pp;pp->par = p;if ((p->rch = v->lch)) p->rch->par = p;update(p);v->lch = p;p->par = v;update(v);} else {if ((p->lch = v->rch)) p->lch->par = p;update(p);if ((pp->rch = v->lch)) pp->rch->par = pp;update(pp);v->rch = p;v->lch = pp;p->par = pp->par = v;update(v);}}if ((v->par = ppp)) {if (ppp->lch == pp) ppp->lch = v;if (ppp->rch == pp) ppp->rch = v;}}}if constexpr (std::is_same<Node, node>::value == true) {if (v->lip) {v->lip->c = v;}}}static node* expose(node *v) {node *c = nullptr;for (node *u = v; u; u = u->par) {splay(u);node *r = u->rch;if (c) {u->y.distsum -= c->x.distsum;u->y.wsum -= c->x.wsum;}if (r) {u->y.distsum += r->x.distsum;u->y.wsum += r->x.wsum;}if (c && r) {node_in *p = c->lip;std::swap(c->lip, r->lip);p->c = r;update(p);splay<node_in>(p);u->lic = p;} else if (c) {node_in *p = c->lip;c->lip = nullptr;splay<node_in>(p);if (!p->lch || !p->rch) {if (p->rch) std::swap(p->lch, p->rch);if ((u->lic = p->lch)) p->lch->par = nullptr;} else {node_in *L = p->lch, *R = p->rch;R->par = nullptr;while (R->lch) R = R->lch;splay<node_in>(R);R->lch = L;L->par = R;update(R);u->lic = R;}} else if (r) {node_in *p = new node_in(r);if ((p->rch = u->lic)) {p->rch->par = p;update(p);}u->lic = r->lip = p;}u->rch = c;update(u);c = u;}splay(v);return c;}// vを根にするstatic void evert(node *v) {expose(v);flip(v);}// 非連結であることが保証されている場合static void _link(node *p, node *c) {evert(c);expose(p);c->par = p;p->rch = c;update(p);}// cの親との辺を切るstatic void cut_from_parent(node *c){expose(c);node *p = c->lch;if (p == nullptr) return;c->lch = p->par = nullptr;update(c);}// 辺(a, b)があることが保証されている場合static void _cut(node *u, node *v) {evert(u);cut_from_parent(v);}// 連結なことが保証されている場合static node *_lca(node *u, node *v) {expose(u);return expose(v);}static bool is_there_edge(node *u, node *v) {evert(u);return u == get_parent(v);}static node *get_root(node *v) {expose(v);while (v->lch) {push(v);v = v->lch;}splay(v);return v;}static node *get_parent(node *v) {expose(v);if (!v->lch) return nullptr;// aが根push(v);v = v->lch;while (v->rch) {push(v);v = v->rch;}splay(v);return v;}// 同じ連結成分かstatic bool is_same(node *u, node *v) {if (!u || !v) return false;return get_root(u) == get_root(v);}static node *centroid(node *v) {expose(v);W wsum = v->x.wsum;if (wsum == 0) return v;while (true) {W subsum = 0;node *u = nullptr;while (v) {push(v);W rsum = v->x.w + v->y.wsum + subsum + (v->rch ? v->rch->x.wsum : 0);if (wsum <= 2 * rsum) {u = v;v = v->rch;} else {subsum = rsum;v = v->lch;}}v = u;if (!v->lic || 2 * v->lic->wmax <= wsum) {expose(v);return v;}v = v->lic->wmaxnode;splay(v);}}};int main() {fast_io<1 << 25, 1 << 24> io;int N = io.in();int Q = io.in();using tree = centroid_dynamic<long long>;using node = tree::node;std::vector<node*> V(N);for (int i = 0; i < N; i++) V[i] = tree::make_node(1);map<std::pair<int, int>, node*> mp;long long S = 0;for (int i = 0; i < Q; i++) {int t = io.in();if (t == 1) {int a = io.in();int b = io.in();int c = io.in();a = (a - 1 + S) % N;b = (b - 1 + S) % N;auto e = tree::make_edge(c);if (a > b) std::swap(a, b);mp[{a, b}] = e;tree::_link(V[a], e);tree::_link(V[b], e);} else if (t == 2) {int a = io.in();int b = io.in();a = (a - 1 + S) % N;b = (b - 1 + S) % N;if (a > b) std::swap(a, b);auto e = mp[{a, b}];tree::_cut(V[a], e);tree::_cut(V[b], e);} else {int a = io.in();a = (a - 1 + S) % N;bool f = V[a]->x.w;tree::expose(V[a]);V[a]->x.w = !f;tree::update(V[a]);auto v = tree::centroid(V[a]);tree::evert(v);long long ans = v->x.distsum;io.out(ans, '\n');S = (S + ans) % N;}}}