TIOJ::1866 . 小向的魔動力捷運系統

http://tioj.ck.tp.edu.tw/problems/1866
小向系列。
題目要你求動態區間XOR最大值。

題目是這樣的，你有一棵樹，而你想知道每個節點到根的那條路徑上，哪一段的XOR值會最大。
每個點到根都是一個序列，所以我們現在想做的是在一個序列上找是否某一段的XOR是最大值。

我們可以先把每段的前綴XOR起來，然後就可以輕鬆知道任何一個區間的XOR值（這是經典老梗了XD），問題就是我們要怎麼知道一個數字和前面一堆數字XOR值最大是多少，仔細想想，我們可以開一棵Trie，從最高位開始紀錄01序列，把前面的數字都插入，然後在Trie上走訪，如果有和現在數字的bit相反的路徑可以走就走（XOR起來會是1，從最高位的話當然希望能是1最好，值會愈大），否則則走bit相同的路徑，這樣就能找到XOR最大值了。

至於動態的話要怎麼維護Trie呢，有兩種作法，一種是DFS的時候（也就是遞迴、Stack），往一條路深入時把現在這個數字插入（記的要弄成這個Stack的前綴XOR），然後在退出時把這個數字從Trie上刪除；另外一種方法是用持久化Trie。

兩種方法，第1種會比較慢，壓線通過；第2種很快，可是記憶體是第1種的兩倍。不過因為Trie本來就是一個記憶體效率大概就是到 字串數*字串長度（總字元個數）的資料結構，有沒有持久化大概也就是差兩倍。

因為這題輸出很大，要是加了endl會慢非常多，要注意。

插入刪除版

#include <bits/stdc++.h>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
const int N = 1e5+1, Sz = 29;
vector<int>G[N];
struct Trie{
    int v;
    Trie *ch[2];
    Trie():v(0){
        ch[0] = ch[1] = NULL;
    }
    static int get_bit(int x,int h){
        return x&(1<<h)?1:0;
    }
    void ins(int x, int h = Sz){
        v++;
        if(h<0)return;
        int b = get_bit(x,h);
        if(!ch[b])ch[b] = new Trie();
        ch[b]->ins(x,h-1);
    }
    void del(int x,int h = Sz){
        v--;
        if(h<0)return;
        int b = get_bit(x,h);
        ch[b]->del(x,h-1);
        if(ch[b]->v == 0){
            delete ch[b];
            ch[b] = NULL;
        }
    }
}*R;
int D[N],ANS[N];
int get_max(int x){
    int h = Sz+1, res = 0;
    Trie *p = R;
    while(h--,h+1){
        int b = p->get_bit(x,h);
        if(p->ch[!b]){
            res += 1<<h;
            p = p->ch[!b];
        }else p = p->ch[b];
    }
    return res;
}
void DFS(int now,int fa, int num, int mx){
    ANS[now] = max(mx, get_max(num^D[now]));
    R->ins(num^D[now]);
    for(int v:G[now])if(v!=fa){
        DFS(v,now,num^D[now],ANS[now]);
    }
    R->del(num^D[now]);
}
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t,n,a,b;
    R = new Trie();
    R->ins(0);
    cin>>t;
    while(t--){
        cin>>n;
        F(n)cin>>D[i];
        fill(G,G+n,vector<int>());
        F(n-1){
            cin>>a>>b;
            a--,b--;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        DFS(0,-1,0,0);
        F(n)cout<<ANS[i]<<'\n';
    }
}

持久化版

#include <bits/stdc++.h>
#define F(n) Fi(i,n)
#define Fi(i,n) Fl(i,0,n)
#define Fl(i,l,n) for(int i=l;i<n;i++)
using namespace std;
const int N = 1e5+1, Sz = 29;
vector<int>G[N];
struct Trie{
    static Trie ST[N*Sz],*p;
    Trie *ch[2];
    Trie(){
        ch[0] = ch[1] = NULL;
    }
    static int get_bit(int x,int h){
        return x&(1<<h)?1:0;
    }
    Trie* ins(int x, int h = Sz){
        if(h<0)return new(Trie::p++) Trie();
        int b = get_bit(x,h);
        Trie *r = new(Trie::p++) Trie(*this);
        if(!r->ch[b])r->ch[b] = new(Trie::p) Trie();
        r->ch[b] = r->ch[b]->ins(x,h-1);
        return r;
    }
}*R[N], Trie::ST[N*Sz],*Trie::p = Trie::ST;
int D[N],ANS[N], st;
int get_max(int x, Trie *r){
    int h = Sz+1, res = 0;
    while(h--,h+1){
        int b = r->get_bit(x,h);
        if(r->ch[!b]){
            res += 1<<h;
            r = r->ch[!b];
        }else r = r->ch[b];
    }
    return res;
}
void DFS(int now,int fa, int num, int mx){
    // cout<<"DD "<<now<<' '<<st<<endl;
    int tmp = num^D[now];
    ANS[now] = max(mx, get_max(tmp,R[st-1]));
    R[st] = R[st-1]->ins(tmp);
    st++;
    Trie *tmpP = Trie::p;
    for(int v:G[now])if(v!=fa){
        DFS(v,now,tmp,ANS[now]);
    }
    Trie::p = tmpP;
    st--;
}
main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t,n,a,b;
    R[0] = new(Trie::p) Trie();
    R[0] = R[0]->ins(0);
    st = 1;
    cin>>t;
    while(t--){
        cin>>n;
        F(n)cin>>D[i];
        fill(G,G+n,vector<int>());
        F(n-1){
            cin>>a>>b;
            a--,b--;
            G[a].push_back(b);
            G[b].push_back(a);
        }
        DFS(0,-1,0,0);
        F(n)cout<<ANS[i]<<'\n';
        // cout<<flush;
    }
}