結果
問題 | No.772 Dynamic Distance Sum |
ユーザー |
|
提出日時 | 2018-12-20 08:50:37 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,211 ms / 5,000 ms |
コード長 | 9,834 bytes |
コンパイル時間 | 1,238 ms |
コンパイル使用メモリ | 83,400 KB |
実行使用メモリ | 49,200 KB |
最終ジャッジ日時 | 2024-09-25 08:23:30 |
合計ジャッジ時間 | 18,426 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 27 |
ソースコード
/*[1] wo sankou ni shita ga (omoni median), warito tigau koto wo shita.Priority Queue wo tsukau to toptree wo tukawanaku temo ikeru ikeru (?)[1] S. Alstrup, J. Holm, K. D. Lichtenberg, M. Thorup. Maintaining information in fully dynamic trees with top trees, Jornal ACM Transactions onAlgorithms, 1(2), Pages 243--264, 2005.*/#include <stdio.h>#include <assert.h>#include <queue> /* priority_queue */#include <iostream>using namespace std;#define N 100001#define TRUE 1#define FALSE 0void swap(int *x, int *y) {int t = *x;*x = *y;*y = t;}void swapl(long long *x, long long *y) {long long t = *x;*x = *y;*y = t;}struct Queue {std::priority_queue<std::pair<int, int>> q;std::priority_queue<std::pair<int, int>> q2;void ins(int k, int v) {q.emplace(k, v);}void del(int k, int v) {q2.emplace(k, v);}std::pair<int, int> min() {while (!q.empty() && !q2.empty() && q.top() == q2.top()) {q.pop();q2.pop();}return q.top();}int size() {return q.size() - q2.size();}};Queue q[N];/* structure data */int L[N], R[N], P[N], REV[N];int MARKED[N]; /* whether the specified node is marked or not (this is a bool value) */long long L_COST[N]; /* the cost of the downward edge */long long R_COST[N]; /* the cost of the upward etge */long long P_COST[N];/* aggregation data */int W[N]; /* the numebr of marked children */long long WU[N]; /* the sum of weights from the external node named u to other nodes */long long WV[N]; /* the sum of weights from the external node named v to other nodes */long long WD[N]; /* the sum of weights from the central node to other nodes */long long LEN[N]; /* the total length of the current cluster path *//* special aggregation data (this data should be handled carefully !!) */int W_DASHED[N]; /* the number of marked children lied on dashed subtrees */long long WD_DASHED[N]; /* the sum of weights from the central node to the dashed children of the specified node *//* external node, v is an ancestor of u */void fix(int x) {W[x] = MARKED[x] + W_DASHED[x] + W[L[x]] + W[R[x]];WD[x] = WD_DASHED[x] + WV[L[x]] + WU[R[x]] + W[L[x]] * L_COST[x] + W[R[x]] * R_COST[x];WU[x] = WU[L[x]] + WU[R[x]] + WD_DASHED[x] + (LEN[L[x]] + L_COST[x]) * (MARKED[x] + W_DASHED[x]) + (LEN[L[x]] + L_COST[x] + R_COST[x]) * W[R[x]];WV[x] = WV[R[x]] + WV[L[x]] + WD_DASHED[x] + (LEN[R[x]] + R_COST[x]) * (MARKED[x] + W_DASHED[x]) + (LEN[R[x]] + R_COST[x] + L_COST[x]) * W[L[x]];LEN[x] = LEN[L[x]] + LEN[R[x]] + L_COST[x] + R_COST[x]; /* (^^) */}void reverse(int x, int rev) {if (!rev) return;REV[x] ^= rev;swapl(&WU[x], &WV[x]);swapl(&L_COST[x], &R_COST[x]);swap(&L[x], &R[x]);}void push(int x) {reverse(L[x], REV[x]);reverse(R[x], REV[x]);REV[x] = FALSE;}void rot(int x) {int y = P[x];int z = P[y];if (L[z] == y) L[z] = x;if (R[z] == y) R[z] = x;P_COST[x] = P_COST[y];P_COST[y] = 0;P[y] = x;P[x] = z;if (L[y] == x) {L[y] = R[x];R[x] = y;if (L[y]) P[L[y]] = y;else {swapl(&L_COST[y], &R_COST[x]);}} else {R[y] = L[x];L[x] = y;if (R[y]) P[R[y]] = y;else {swapl(&R_COST[y], &L_COST[x]);}}fix(y);}bool is_root(int x) {return L[P[x]] != x && R[P[x]] != x;}void local_splay(int x) {while (!is_root(x)) {if (!is_root(P[x])) {rot((L[P[x]] == x) == (L[P[P[x]]] == P[x]) ? P[x] : x);}rot(x);}}void push_ancestors(int x) {if (!x) return;push_ancestors(P[x]);push(x);}void global_splay(int x) {push_ancestors(x);{int y = x;while (y != 0) {while (!is_root(y)) y = P[y];int z = P[y];if (z) {W_DASHED[z] -= W[y];WD_DASHED[z] -= WV[y] + W[y] * P_COST[y];q[z].del(W[y], y);}y = z;}}int y = x;int l = 0;while (y != 0) {local_splay(y);int w = L[y];P_COST[w] = L_COST[y];L_COST[y] = P_COST[l];P_COST[l] = 0;W_DASHED[y] += W[w];WD_DASHED[y] += WV[w] + W[w] * P_COST[w];if (w) {q[y].ins(W[w], w);}L[y] = l;l = y;fix(y);y = P[y];}local_splay(x);fix(x);}void reroot(int x) {global_splay(x);reverse(x, TRUE);push(x);}void link(int x, int y, long long w) {reroot(x);global_splay(y);// assert(L[y] == 0);assert(P[x] == 0);L[y] = x;P[x] = y;L_COST[y] = w;fix(y);}void cut(int x, int y) {reroot(x);global_splay(y);R_COST[y] = 0;P_COST[R[y]] = 0;P[R[y]] = 0;R[y] = 0;fix(y);}void dfs(int u) {if (!u) {return;}dfs(L[u]);// assert(!(L[u] == 0 && L_COST[u] != 0));// assert(!(R[u] == 0 && R_COST[u] != 0));printf(" ");printf("(%d,%lld)", L[u], L_COST[u]);printf("%d", u);printf("(%d,%lld)", R[u], R_COST[u]);printf(" ");dfs(R[u]);}void iter(int x, vector<int> &res) {if (!x) return;res.push_back(x);iter(L[x], res);iter(R[x], res);}bool same(int x, int y) {while (P[x] != 0) x = P[x];while (P[y] != 0) y = P[y];bool res = x == y;global_splay(x);global_splay(y);return res;}long long median2(int x, int n) {long long res = 2e18;for (int i = 1; i <= n; i++) {if (same(i, x)) {global_splay(i);res = min(res, WD[i]);}}return res;}pair<int, long long> median(int x) {global_splay(x);int ll = 0;int rr = 0;int E = W[x];for (;;) {push(x);int n = W[x];if (L[x]) {int y = L[x];int ny = ll + W[y];int nx = E - ny;assert(ny + nx == E);if (ny > nx) {rr += W[x] - W[y];x = y;continue;}}if (R[x]) {int y = R[x];int ny = rr + W[y];int nx = E - ny;assert(ny + nx == E);if (ny > nx) {ll += W[x] - W[y];x = y;continue;}}if (q[x].size() > 0) {int y = q[x].min().second;assert(is_root(y));int ny = W[y];int nx = E - ny;if (ny > nx) {rr += ll + W[x] - W[y];ll = 0;x = y;continue;}}break;}global_splay(x);return make_pair(x, WD[x]);}void output(int n) {for (int i = 1; i <= n; i++) {global_splay(i);printf("%d %lld %lld\n", i, WD[i], LEN[i]);}for (int i = 1; i <= n; i++) {if (is_root(i)) {printf("*** %d %d\n", i, P[i]);}}for (int i = 1; i <= n; i++) {if (is_root(i)) {dfs(i);}puts("");}}void test1() {for (int i = 1; i <= 7; i++) {MARKED[i] = 1;}link(1, 2, 2);link(3, 4, 4);link(2, 3, 3);link(5, 6, 3);link(5, 7, 10);link(2, 5, 1);printf("%d %d %d %d %lld %lld %lld %lld\n", L[0], R[0], P[0], W[0], WD[0], WU[0], WV[0], LEN[0]);reroot(1);for (int i = 1; i <= 7; i++) {global_splay(i);}for (int i = 1; i <= 7; i++) {printf("*** %d %lld\n", i, P_COST[i]);}global_splay(7);for (int i = 1; i <= 7; i++) {if (is_root(i)) {dfs(i);}puts("");}global_splay(1); assert(WD[1] == 38); assert(W[1] == 7);global_splay(2); assert(WD[2] == 28); assert(W[2] == 7);global_splay(3); assert(WD[3] == 37); assert(W[3] == 7);global_splay(4); assert(WD[4] == 57); assert(W[4] == 7);global_splay(5); assert(WD[5] == 29); assert(W[5] == 7);global_splay(6); assert(WD[6] == 44); assert(W[6] == 7);global_splay(7); assert(WD[7] == 79); assert(W[7] == 7);cout << "---" << endl;cut(2, 5);for (int i = 1; i <= 7; i++) {printf("*** %d %lld\n", i, P_COST[i]);}for (int i = 1; i <= 7; i++) {if (is_root(i)) {dfs(i);}puts("");}}void test2() {for (int i = 1; i <= 7; i++) {MARKED[i] = 1;}link(1, 2, 2);link(3, 4, 4);link(2, 5, 1);link(5, 6, 3);link(5, 7, 10);link(2, 3, 3);pair<int, long long> res = median(1);assert(res.first == 2 && res.second == 28);}long long Q;int main() {int n, q;scanf("%d %d", &n, &q);for (int i = 1; i <= n; i++) {MARKED[i] = TRUE;}long long S = 0;while (q--) {int type;scanf("%d", &type);if (type == 1) {int a, b, c;scanf("%d %d %d", &a, &b, &c);a = (a - 1 + S) % n + 1;b = (b - 1 + S) % n + 1;link(a, b, c);} else if (type == 2) {int a, b;scanf("%d %d", &a, &b);a = (a - 1 + S) % n + 1;b = (b - 1 + S) % n + 1;cut(a, b);} else {int a;scanf("%d", &a);a = (a - 1 + S) % n + 1;global_splay(a);MARKED[a] ^= 1;fix(a);long long ans = median(a).second;S += ans;S %= n;printf("%lld\n", ans);}}}