題目鏈接：點擊查看

題目大意：給出一棵 $n$ 個點組成的樹，每個點權的取值范圍是 $[l_i,r_i]$，每條邊權代表的是兩點的異或值，現在問這棵樹有多少種有效賦值

題目分析：假設點 $1$ 為基準點，找到點 $1$ 到 $n$ 個點的路徑上的異或和記為 $w_i$，那么問題轉換為了，點 $1$ 有多少種可行的取值 $x$，需要同時滿足 $n$ 個不等式：$l_i\le (w_i\oplus x)\le r_i$

考慮 $w_i\oplus [l_i,r_i]$ 后的新區間，打表發現并不具有連續性。但是這里有一個異或的性質：

我們可以利用 $[0,2^{30}?1]$ 的線段樹, 把 $[L_i,R_i]$ 分成 $O(logW)$
個連續的區間，且每個區間的形式是 : $k...30$ 位相同，$0...k?1$ 位是 $0$ 到 $2^k?1$，這樣的區間異或上
$w_i$ 后仍然還是一個區間

所以可以利用上述性質將 $w_i\oplus [l_i,r_i]$ 拆成 $O(logW)$ 個新區間，放到線段樹上，最后統計一下 $n$ 個新區間的交集就是答案了

代碼：

// Problem: Tree Xor // Contest: NowCoder // URL: https://ac.nowcoder.com/acm/contest/11255/E // Memory Limit: 524288 MB // Time Limit: 4000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) (x&-x) using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e5+100; const int limit=(1<<30)-1; int l[N],r[N],w[N],n; vector<pair<int,int>>node[N]; struct Node {int l,r,lazy; }tree[N*4*20]; int tot=0; int newnode() {tot++;tree[tot].l=tree[tot].r=tree[tot].lazy;return tot; } int get_l(int x,int dep) {//return xxxxx|00000return x&(limit^((1<<dep)-1)); } int get_r(int x,int dep) {//return xxxxx|11111return x|((1<<dep)-1); } int inter(int l1,int r1,int l2,int r2) {return max(l1,l2)<=min(r1,r2); } void insert(int& k,int l,int r,int x,int y,int w,int dep) {if(!k) {k=newnode();}if(get_l(l^w,dep)>=x&&get_r(l^w,dep)<=y) {tree[k].lazy++;return;}if(tree[k].lazy) {int lz=tree[k].lazy;tree[k].lazy=0;if(!tree[k].l) {tree[k].l=newnode();}if(!tree[k].r) {tree[k].r=newnode();}tree[tree[k].l].lazy+=lz;tree[tree[k].r].lazy+=lz;}int mid=(l+r)>>1;if(inter(x,y,get_l(l^w,dep-1),get_r(l^w,dep-1))) {insert(tree[k].l,l,mid,x,y,w,dep-1);}if(inter(x,y,get_l((mid+1)^w,dep-1),get_r((mid+1)^w,dep-1))) {insert(tree[k].r,mid+1,r,x,y,w,dep-1);} } int query(int k,int l,int r) {if(!k) {return 0;}if(tree[k].lazy==n) {return r-l+1;}if(tree[k].lazy) {int lz=tree[k].lazy;tree[k].lazy=0;if(tree[k].l) {tree[tree[k].l].lazy+=lz;}if(tree[k].r) {tree[tree[k].r].lazy+=lz;}}int mid=(l+r)>>1;return query(tree[k].l,l,mid)+query(tree[k].r,mid+1,r); } void dfs(int u,int fa,int sum) {w[u]=sum;for(auto it:node[u]) {int v=it.first,w=it.second;if(v==fa) {continue;}dfs(v,u,sum^w);} } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);read(n);for(int i=1;i<=n;i++) {read(l[i]),read(r[i]);}for(int i=1;i<n;i++) {int u,v,w;read(u),read(v),read(w);node[u].push_back({v,w});node[v].push_back({u,w});}dfs(1,-1,0);int rt=0;for(int i=1;i<=n;i++) {insert(rt,0,limit,l[i],r[i],w[i],30);}cout<<query(rt,0,limit)<<endl;return 0; }

總結

以上是生活随笔為你收集整理的2021牛客多校4 - Tree Xor(线段树+异或区间拆分)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。