結果

問題 No.772 Dynamic Distance Sum
コンテスト
ユーザー pekempey
提出日時 2018-12-20 09:10:20
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,188 ms / 5,000 ms
コード長 5,834 bytes
コンパイル時間 791 ms
コンパイル使用メモリ 58,112 KB
実行使用メモリ 48,820 KB
最終ジャッジ日時 2024-09-25 08:24:24
合計ジャッジ時間 17,665 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 27
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <assert.h>
#include <queue>

#define N 100001
#define TRUE 1
#define FALSE 0

void 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];

int L[N], R[N], P[N], REV[N];
int MARKED[N];
long long L_COST[N];
long long R_COST[N];
long long P_COST[N];

int W[N];
long long WU[N];
long long WV[N];
long long WD[N];
long long LEN[N];

int W_DASHED[N];
long long WD_DASHED[N];

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

std::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 std::make_pair(x, WD[x]);
}

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