結果
問題 | No.772 Dynamic Distance Sum |
ユーザー |
![]() |
提出日時 | 2020-04-26 13:14:17 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 951 ms / 5,000 ms |
コード長 | 6,463 bytes |
コンパイル時間 | 1,650 ms |
コンパイル使用メモリ | 174,820 KB |
実行使用メモリ | 41,216 KB |
最終ジャッジ日時 | 2024-11-17 02:19:15 |
合計ジャッジ時間 | 21,453 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
#include <bits/stdc++.h>int ri() {int n;scanf("%d", &n);return n;}#include <array>#include <iostream>#include <algorithm>struct Node;extern Node *NONE;struct Node {Node *p = NONE;std::array<std::array<Node *, 2>, 2> ch = { { {NONE, NONE}, {NONE, NONE} } };Node *light_down = NONE;bool rev = false;bool enabled_self = false;int enabled_sum = 0; // heavy + light_down sumint enabled_sum_all = 0; // for light_treeint enabled_sum_max = 0; // for light_treeint len_self = 0;int64_t len_sum = 0; // heavy sumint64_t left_sum = 0;int64_t right_sum = 0;Node *fetch() {for (auto &i : ch) for (auto j : i) if (j != NONE) j->flush();if (light_down != NONE) light_down->flush();enabled_sum = enabled_self + light_down->enabled_sum_all + ch[0][0]->enabled_sum_all + ch[0][1]->enabled_sum_all;enabled_sum_all = enabled_sum + ch[1][0]->enabled_sum_all + ch[1][1]->enabled_sum_all;enabled_sum_max = std::max({enabled_sum, ch[1][0]->enabled_sum_max, ch[1][1]->enabled_sum_max});len_sum = len_self + ch[0][0]->len_sum + ch[0][1]->len_sum;int64_t left_len_sum = ch[0][0]->len_sum;left_sum = ch[0][0]->left_sum + enabled_self * left_len_sum +light_down->left_sum + light_down->enabled_sum_all * (left_len_sum + len_self) +ch[0][1]->left_sum + ch[0][1]->enabled_sum * (left_len_sum + len_self) +ch[1][0]->left_sum + ch[1][1]->left_sum;int64_t right_len_sum = ch[0][1]->len_sum;right_sum = ch[0][1]->right_sum + enabled_self * right_len_sum +light_down->left_sum + light_down->enabled_sum_all * (right_len_sum + len_self) +ch[0][0]->right_sum + ch[0][0]->enabled_sum * (right_len_sum + len_self) +ch[1][0]->left_sum + ch[1][1]->left_sum;return this;}void flush() {if (rev) {ch[0][0]->rev ^= 1;ch[0][1]->rev ^= 1;std::swap(ch[0][0], ch[0][1]);std::swap(left_sum, right_sum);rev = false;}}#define l ch[cat][0]#define r ch[cat][1]template<int cat> Node *rotate(int dir) {Node *new_root = ch[cat][!dir];if (!cat) std::swap(new_root->ch[1], ch[1]);ch[cat][!dir] = new_root->ch[cat][dir];ch[cat][!dir]->p = this;new_root->ch[cat][dir] = this;for (auto &i : p->ch) for (auto &j : i) if (j == this) j = new_root;if (p->light_down == this) p->light_down = new_root;new_root->p = p;p = new_root;return fetch(), new_root->fetch();}template<int cat> bool is_root() {return p == NONE || (p->l != this && p->r != this);}template<int cat> void splay() {flush();while (!is_root<cat>()) {if (p->is_root<cat>()) {p->flush(), flush();p->rotate<cat>(p->l == this);} else {Node *pp = p->p;pp->flush(), p->flush(), flush();bool dir0 = pp->l == p;bool dir1 = p->l == this;if (dir0 == dir1) pp->rotate<cat>(dir0);p->rotate<cat>(dir1);if (dir0 != dir1) pp->rotate<cat>(dir0);}}}#undef l#undef rvoid expose() {Node *cur = this;cur->splay<0>();for (; cur != NONE; ) {cur->splay<1>();if (cur->p == NONE) break;cur = cur->p;cur->splay<0>();cur->light_down->flush();if (cur->ch[0][1] != NONE) {cur->ch[0][1]->flush();std::swap(cur->ch[0][1]->ch[1], cur->light_down->ch[1]);std::swap(cur->ch[0][1], cur->light_down);for (auto i : cur->light_down->ch[1]) i->p = cur->light_down;cur->light_down->fetch();} else {cur->ch[0][1] = cur->light_down;Node *rightest = cur->light_down->ch[1][0];if (rightest == NONE) rightest = cur->light_down->ch[1][1];else {Node *tmp = cur->light_down->ch[1][1];rightest->p = NONE;while (rightest->flush(), (rightest->ch[1][1] != NONE))rightest = rightest->ch[1][1];rightest->splay<1>();rightest->ch[1][1] = tmp;tmp->p = rightest;rightest->fetch();}cur->light_down = rightest;rightest->p = cur;cur->ch[0][1]->ch[1] = {NONE, NONE};}cur->fetch();}splay<0>();Node *right = ch[0][1];if (right != NONE) {right->flush();right->ch[1][0] = light_down;light_down->p = right;light_down = right;ch[0][1] = NONE;right->fetch();fetch();}}void link(Node *parent) {parent->expose();expose();p = parent;parent->ch[0][1] = this;parent->fetch();}Node *cut() {expose();Node *res = ch[0][0];ch[0][0]->p = NONE;ch[0][0] = NONE;fetch();return res;}void evert() {expose();rev ^= 1;flush();}Node *centroid_light(int minimum) {flush();if (ch[1][0]->enabled_sum_max >= minimum) return ch[1][0]->centroid_light(minimum);if (ch[1][1]->enabled_sum_max >= minimum) return ch[1][1]->centroid_light(minimum);return centroid_heavy(minimum, minimum);}Node *centroid_heavy(int remaining, int minimum) { // heavyflush();if (light_down->enabled_sum_max >= minimum) return light_down->centroid_light(minimum);if (ch[0][1]->enabled_sum >= remaining) return ch[0][1]->centroid_heavy(remaining, minimum);int subtree_enabled = ch[0][1]->enabled_sum + light_down->enabled_sum_all + enabled_self;if (subtree_enabled >= remaining) return this;else return ch[0][0]->centroid_heavy(remaining - subtree_enabled, minimum);}Node *centroid() {expose();if (!enabled_sum) return this;Node *cur = this;for (; cur->flush(), (cur->ch[0][0] != NONE); cur = cur->ch[0][0]);cur->expose();int minimum = (cur->enabled_sum + 1) / 2;cur = cur->centroid_heavy(minimum, minimum);cur->expose();return cur;}};Node *NONE = new Node;int main() {int n = ri(), q = ri();Node nodes[n];for (auto &i : nodes) i.enabled_self = true, i.fetch();Node hens[q];int sum = 0;for (int i = 0; i < q; i++) {int t = ri();if (t == 1) {int a = (ri() - 1 + sum) % n;int b = (ri() - 1 + sum) % n;int c = ri();hens[i].len_self = c;hens[i].fetch();nodes[a].evert();nodes[a].link(hens + i);hens[i].link(nodes + b);} else if (t == 2) {int a = (ri() - 1 + sum) % n;int b = (ri() - 1 + sum) % n;nodes[a].evert();Node *hen = nodes[b].cut();while (hen->flush(), (hen->ch[0][1] != NONE)) hen = hen->ch[0][1];hen->cut();} else if (t == 3) {int a = (ri() - 1 + sum) % n;nodes[a].expose();nodes[a].enabled_self ^= 1;nodes[a].fetch();Node *centroid = nodes[a].centroid();centroid->evert();int64_t res = centroid->left_sum;sum = (sum + res) % n;printf("%" PRId64 "\n", res);}}return 0;}