Tree Xor

題意：

一顆有n個(gè)點(diǎn)的樹(shù)，邊權(quán)給出，第i個(gè)節(jié)點(diǎn)的權(quán)值為Wi，但并不知道Wi，只知道Wi在[Li,Ri]，邊權(quán)等于兩端點(diǎn)的異或值
問(wèn)W序列有多少可能

題解：

如果我們知道一個(gè)點(diǎn)的值，就可以推出其他所有點(diǎn)的值。
現(xiàn)在我們令w[1]=0,解出剩下的w，如果令w[1] = a ,剩下的w都會(huì)xor上a
所以就變成了求解合法的a的數(shù)量，限制有n個(gè)不等式，形式為：
L[i] <= W[i] Xor a <= R[i]
你可能會(huì)覺(jué)得a會(huì)屬于[L[i] Xor W[i],R[i] Xor w[i]],但問(wèn)題是原本[L,R]是連續(xù)的，但是異或w[i]后不一定連續(xù)。
出題很妙的地方：

我們利用[0,2³⁰-1]的線段樹(shù)，把[L[i],R[i]]分成O(logW)個(gè)連續(xù)的區(qū)間，且每個(gè)區(qū)間的形式是K…30位相同，0…k-1位是0到2^k-1，這樣的區(qū)間異或上w[i]后仍然還是一個(gè)區(qū)間

剛才這一部分是官方題解里的，談?wù)勎业睦斫?br /> 剛才說(shuō)了區(qū)間xor W[i]后不一定連續(xù)，但是如果我們把區(qū)間[L[i],R[i]]分成好幾個(gè)小區(qū)間，這個(gè)小區(qū)間Xor W[i]后，這幾個(gè)小區(qū)間可能本身還是連續(xù)的(不看這幾個(gè)小區(qū)間之間的聯(lián)系，只看小區(qū)間本身)。
那該怎么分呢？我們利用[0,2³⁰-1]的線段樹(shù)，我們想下建樹(shù)過(guò)程，一開(kāi)始是[L=0,R=111111…（一共30個(gè)1）]，然后分治建邊，分成兩個(gè)區(qū)間[L=0,R=1111…(一共29個(gè))]，[L=1000…（一共29個(gè)0）,R=11111…（一共30個(gè)1）]，一直這樣下去，得到的區(qū)間都滿足下面形式：
[xxxx0000，xxxx1111],xxxx部分是相同的，也就是前k位相同，后k位分別是0和1
這樣的區(qū)間異或上一個(gè)數(shù)x后仍然還是一個(gè)連續(xù)完整區(qū)間（很神奇，可以自己測(cè)試以下）
我用L=80（101000），R=95（1011111），當(dāng)x小于等于15(1111)時(shí)，[L,R]的區(qū)間還是本區(qū)間只是內(nèi)部打亂順序，當(dāng)大于15時(shí)[L,R]區(qū)間會(huì)整體變小，但是區(qū)間長(zhǎng)度依舊不變。我認(rèn)為是一位這個(gè)區(qū)間的對(duì)稱的，所以才會(huì)這樣
這樣就可以將原區(qū)間[L[i],R[i]]拆成n組區(qū)間，a屬于這個(gè)n組區(qū)間，那n組區(qū)間求個(gè)交(可以利用差分)，就得到a的數(shù)量

代碼：

#include <iostream> #include <string> #include <cstring> #include <cmath> #include <algorithm> #include <queue> #include <iomanip> #include <map> #include <cstdio> #include <stack> #include <set> using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int ,int> pii; #define endl '\n' ll gcd(ll a, ll b){return b == 0 ? a : gcd(b, a % b); } void input(){freopen("in.txt", "r", stdin);freopen("out.txt", "w", stdout); } inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9') {if(c=='-') f=-1;c=getchar();}while (c>='0'&&c<='9') x=(x<<3)+(x<<1)+(c^48),c=getchar();return x*f; } const int N = 1e6+10, M = N * 2, inf = 1e8; int n, L[N], R[N], W[N]; vector<pii> G[N]; vector<pii> seg, v; // l r 是當(dāng)前點(diǎn)限制的左右取值范圍 // vl vr 是當(dāng)前這段區(qū)間所代表的取值范圍 // dep 表示深度，v是在w1取0的條件下當(dāng)前點(diǎn)的取值 void build(int l, int r, int vl, int vr, int dep, int v){if(l <= vl && vr <= r){int nowl = (vl ^ v) & (((1<<30)-1) ^ ((1<<dep) - 1));int nowr = nowl + (1<<dep) - 1;//cout<<"vl="<<vl<<" "<<"vr="<<vr<<endl;//cout<<"nowl="<<nowl<<" "<<"nowr="<<nowr<<endl; seg.push_back({nowl, nowr});}else{int mid = (vl + vr) >> 1;if(l <= mid) build(l, r, vl, mid, dep-1, v);if(r > mid) build(l, r, mid+1, vr, dep-1, v);} } // 使用dfs求解每個(gè)點(diǎn)的值 void dfs(int x, int fa, int val){if(x != 1) build(L[x], R[x], 0, (1<<30)-1, 30, val);for(auto i : G[x]){if(i.first == fa) continue;dfs(i.first, x, i.second^val);} } int main(){ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);cin>>n;for(int i = 1; i <= n; i++) cin>>L[i]>>R[i];for(int i = 1; i < n; i++){int u, v, w; cin>>u>>v>>w;G[u].push_back({v, w});G[v].push_back({u, w});}dfs(1, -1, 0);seg.push_back({L[1], R[1]});for(auto i : seg) v.push_back({i.first, 1}), v.push_back({i.second + 1, -1});//差分思想 sort(v.begin(), v.end());int res = 0, sum = 0;for(int i = 0; i < (int)v.size(); i++){sum += v[i].second;if(sum == n) //當(dāng)存在n個(gè)區(qū)間同時(shí)滿足時(shí)，就是a的取值范圍 res += v[i+1].first - v[i].first;}cout<<res<<endl;return 0; }

總結(jié)

以上是生活随笔為你收集整理的Tree Xor(未完全搞定)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。