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;
}
題目簡述：
轉化成一棵有根樹支持兩種操作
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;
}