結果

問題 No.772 Dynamic Distance Sum
ユーザー QCFiumQCFium
提出日時 2020-04-26 13:14:17
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 871 ms / 5,000 ms
コード長 6,463 bytes
コンパイル時間 1,829 ms
コンパイル使用メモリ 174,576 KB
実行使用メモリ 41,216 KB
最終ジャッジ日時 2024-04-28 11:06:43
合計ジャッジ時間 20,144 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
5,248 KB
testcase_01 AC 1 ms
5,376 KB
testcase_02 AC 1 ms
5,376 KB
testcase_03 AC 1 ms
5,376 KB
testcase_04 AC 6 ms
5,376 KB
testcase_05 AC 4 ms
5,376 KB
testcase_06 AC 6 ms
5,376 KB
testcase_07 AC 3 ms
5,376 KB
testcase_08 AC 5 ms
5,376 KB
testcase_09 AC 8 ms
5,376 KB
testcase_10 AC 8 ms
5,376 KB
testcase_11 AC 3 ms
5,376 KB
testcase_12 AC 856 ms
38,824 KB
testcase_13 AC 861 ms
38,912 KB
testcase_14 AC 755 ms
38,676 KB
testcase_15 AC 759 ms
38,784 KB
testcase_16 AC 851 ms
38,784 KB
testcase_17 AC 843 ms
38,912 KB
testcase_18 AC 680 ms
38,656 KB
testcase_19 AC 814 ms
38,656 KB
testcase_20 AC 633 ms
38,784 KB
testcase_21 AC 871 ms
41,088 KB
testcase_22 AC 772 ms
41,216 KB
testcase_23 AC 797 ms
41,088 KB
testcase_24 AC 806 ms
40,960 KB
testcase_25 AC 825 ms
41,216 KB
testcase_26 AC 786 ms
41,088 KB
testcase_27 AC 863 ms
40,960 KB
testcase_28 AC 796 ms
41,088 KB
testcase_29 AC 641 ms
41,088 KB
権限があれば一括ダウンロードができます

ソースコード

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;
}
0