2013-04-13 08:24:39Morris

[NPSC][線段樹] a651. D. 小可魚兒向上游

內容 :

江江江江,有一條江耶!
 
經 過長時間的觀察,老姜發現這條江有許多支流,且整個河系可以用一個以源頭為根的樹狀結構來表示。除此之外老姜還發現有許多小可魚循著某種規律在江河中悠游 穿梭,每當一隻小可魚開始逆流而上時,牠會先在起點做個記號,之後開始奮發向上游阿游阿游,直到源頭或是遇到其他小可魚在牠開始前做的記號為止。
 
聰明的老姜已經先寫了一個程式來預測每隻小可魚最後會停在哪裡,但謹慎的他還是請你也寫一份來確認他寫的程式是否正確。但為了肉眼比對方便,聰明的老姜決定比較結果的雜湊值就好,也就是假設小可魚最後停留的位置依序為p1, p2, ..., pk,則我們定義其雜湊值為(p1 + 1)^(p2 + 2)^...^(pk + k),其中^代表xor 運算。

輸入說明 :

輸入檔的第一行有一個正整數T (T<=514),表示接下來總共有幾條江的觀察記錄。
 
每個觀察記錄開始有兩個正整數N,M (M < N <= 105), 代表這條江的樹狀結構有N 個節點,M 隻小可魚。節點編號為0, 1, ...,N − 1,其中0 為源頭。下一行有N − 1 個整數,代表每個節點(支流)1, 2, ...,N − 1 的上游編號。再下一行有M 個相異整數,代表每隻小可魚的起點,輸入順序為小可魚們開始向上的順序。

輸出說明 :

對於每筆觀察紀錄,請輸出其對應的雜湊值。若對雜湊值之運算有所疑惑可以參考題目B 所附之程式碼。

範例輸入 :

2
4 3
0 1 2
3 1 2
5 3
2 0 2 2
1 2 3

範例輸出 :

7
6

提示 :

出處 :

NPSC 2012 高中組決賽 (管理:xavier13540)


題目簡述:
轉化成一棵有根樹支持兩種操作
1. 將某節點當作新的一棵樹分裂出來
2. 查詢某節點所在的樹根

×
一開始一定會給定以 0 為樹根的一棵樹。

題目分析:
先說,接下來描述的作法不是很好,也是又臭又長的。

先將一棵樹進行後序走訪,對於一個父節點 O,
後序結果:[[子樹 ... 子樹]O ...
[子樹 ... 子樹]O]O
得到父節點的節點編號一定大於子樹的所有節點,同時要記錄每個父節點的控制子節點的區間。

根據後序走訪的結果,建立 ST 線段樹,對應的其父節點在後序走訪中的編號。
因此每個節點一開始都是 n,
然後在
操作 1 時,使用懶操作(標記),將區間 [l, r] 的每個元素與某個值k取 min。
區間[l, r]決定於父節點的控制區間,而 k 是後序走訪的編號。

操作 2 時,直接由 ST 線段樹得到其單一元素數值,記住,
在這裡得到的數值 val 指得是後序走訪編號,因此要得到樹根編號,必須打個映射。


#include <stdio.h>
#include <vector>
#include <string.h>
using namespace std;
vector<int> g[100005];
int ST[530000], label[530000];
int RC[100005][2];
int postOrder[100005], visited[100005], pidx;
void build(int nd) {
    int i;
    RC[nd][0] = pidx;
    for(i = 0; i < g[nd].size(); i++)
        build(g[nd][i]);
    postOrder[pidx] = nd;
    visited[nd] = pidx;
    RC[nd][1] = pidx;
    pidx++;
}
void relax(int k, int l, int r) {
    if(label[k] < 0)    return;
    int m = (l+r)/2;
    ST[k] = min(ST[k], label[k]);
    if(l <= m) {
        if(label[k<<1] < 0)
            label[k<<1] = label[k];
        else
            label[k<<1] = min(label[k], label[k<<1]);
    }
    if(m+1 <= r) {
        if(label[k<<1|1] < 0)
            label[k<<1|1] = label[k];
        else
            label[k<<1|1] = min(label[k], label[k<<1|1]);
    }
    label[k] = -1;
}
int argv;
void modify(int k, int l, int r, int ql, int qr) {
    if(l > r)   return ;
    relax(k, l, r);
    if(ST[k] <= argv)
        return;
    if(l == ql && r == qr) {
        label[k] = argv;
        relax(k, l, r);
        return ;
    }
    int m = (l+r)/2;
    if(m >= qr)
        modify(k<<1, l, m, ql, qr);
    else if(m < ql)
        modify(k<<1|1, m+1, r, ql, qr);
    else {
        modify(k<<1, l, m, ql, m);
        modify(k<<1|1, m+1, r, m+1, qr);
    }
}
int query(int k, int l, int r, int qx) {
    relax(k, l, r);
    if(l == r && l == qx)
        return ST[k];
    int m = (l+r)/2;
    if(qx <= m)
        return query(k<<1, l, m, qx);
    else
        return query(k<<1|1, m+1, r, qx);
}
int main() {
    int T;
    int n, q;
    int i, j, x;
    scanf("%d", &T);
    while(T--) {
        scanf("%d %d", &n, &q);
        for(i = 0; i <= n; i++)
            g[i].clear();
        for(i = 1; i < n; i++) {
            scanf("%d", &x);
            g[x].push_back(i);
        }
        pidx = 0;
        build(0);
        memset(ST, 63, sizeof(ST));
        memset(label, -1, sizeof(label));
        argv = visited[0];
        modify(1, 0, n-1, RC[0][0], RC[0][1]);
        int ans = 0;
        for(i = 1; i <= q; i++) {
            scanf("%d", &x);
            argv = query(1, 0, n-1, visited[x]);
            argv = postOrder[argv];
            ans ^= argv + i;
            //printf("%d %d [%d %d]\n", argv, visited[x], RC[x][0], RC[x][1]);
            argv = visited[x];
            modify(1, 0, n-1, RC[x][0], RC[x][1]);
        }
        printf("%d\n", ans);
    }
    return 0;
}