24h購物| | PChome| 登入
2013-04-13 08:24:39| 人氣657| 回應0 | 上一篇 | 下一篇

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

推薦 0 收藏 0 轉貼0 訂閱站台

內容 ：

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

我要檢舉
#a651#D. 小可魚兒向上游#ST#線段樹
台長： Morris

您可能對以下文章有興趣

人氣(657) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: NPSC |
此分類下一篇:[NPSC][AC自動機DP] a640. A. 曉涵的紙牌遊戲
此分類上一篇:[NPSC][歸併樹] a656. E. 胖胖天天天胖

我要回應
否 是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼：
請輸入圖片中算式的結果(可能為0) 
(有*為必填)
TOP
詳全文