題目大意

題目描述

Mirko在玩堆疊遊戲。開始他有一個空的堆疊，編號為0.在第i步(1<=i<=300000)，他會選擇一個編號為v的堆疊，複製一份並做如下操作：

a v 表示將v號堆疊複製一份，新棧的編號為i,並將元素i壓入新棧的棧頂。
b v 表示將v號堆疊複製一份，新棧的編號為i，將新棧的棧頂元素彈出。
c v w 將v號堆疊複製一份，編號為i，並比較第v號和第w號堆疊中有多少相同的數。

輸入格式

第一行一個整數n，表示有n步。
接下來n步，每步表示一個操作，如上所述。

輸出格式：

對所有的b操作和c操作，輸出結果，每行一個。b操作需要輸出該棧移除的元素，c操作表示兩個堆疊的相同的數的個數。

樣例

樣例輸入

5
a 0
a 1
b 2
c 2 3
b 4

樣例輸出

2
1
2

題解

對於a類操作，我們可以把i看成是x延伸出去的一個兒子；
對於b類操作，我們可以發現i和x的父節點是等價的，所以我們直接將其在樹上的節點設為x的父節點。
對於c類操作，因為每次加入棧中的數互不相同(所有的i都不同)，所以只有在樹上經過同一個操作的結點才會增加一個相等的數，即是找LCA。

程式碼

#include <bits/stdc++.h>
using namespace std;
const int Step = 20;

int n;
int tree[300005];
bool f[300005];
int pre[300005];
int dp[300005][30];
int tot[300005];
int First[300005];

int LCA(int x, int y) {
    if (pre[x] > pre[y]) {
        int t = x;
        x = y;
        y = t;
    }
    for (int i = Step; i >= 0; --i) {
        if (pre[dp[y][i]] >= pre[x])
            y = dp[y][i];
    }
    if (x == y)
        return x;
    for (int i = Step; i >= 0; --i) {
        if (dp[x][i] != dp[y][i]) {
            x = dp[x][i];
            y = dp[y][i];
        }
    }
    return dp[x][0];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        char s[5];
        int x;
        scanf("%s%d", s, &x);
        // printf("\n%c\n%d\n",s[0],x);
        x = tree[x];
        if (s[0] == 'a') {
            tree[i] = i;
            dp[i][0] = x;
            tot[i] = tot[x] + 1;
            First[i] = i;
            pre[i] = pre[dp[i][0]] + 1;
            for (int j = 1; j <= Step; j++) {
                dp[i][j] = dp[dp[i][j - 1]][j - 1];
            }
        } else if (s[0] == 'b') {
            tree[i] = dp[x][0];
            printf("%d\n", First[x]);
        } else {
            int y;
            scanf("%d", &y);
            y = tree[y];
            printf("%d\n", tot[LCA(x, y)]);
            tree[i] = x;
        }
    }
    return 0;
}

堆疊遊戲題解

目錄