結果

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

ソースコード

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

#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 sum
int enabled_sum_all = 0; // for light_tree
int enabled_sum_max = 0; // for light_tree
int len_self = 0;
int64_t len_sum = 0; // heavy sum
int64_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 r
void 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) { // heavy
flush();
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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0