now9999网站提示建设中,网站主导航,门户网站建设方案,做网站可以用微软雅黑字体么E-Tree Xor
首先不考虑区间限制条件#xff0c;我们给定其中一个点的权值后#xff0c;那么其他点的权值也就确定。比如 val10\text{val}_10val10#xff0c;即可通过变得限制求出其他点valu\text{val}_uvalu#xff0c;而且不难发现如果val10⊕a\text{val}_10\oplus …E-Tree Xor
首先不考虑区间限制条件我们给定其中一个点的权值后那么其他点的权值也就确定。比如 val10\text{val}_10val10即可通过变得限制求出其他点valu\text{val}_uvalu而且不难发现如果val10⊕a\text{val}_10\oplus aval10⊕a那么其余点的权值valu0⊕a\text{val}_u0\oplus avalu0⊕a
下面记valu\text{val}_uvalu为当val10\text{val}_10val10时u点的权值。
于是问题转化为求出满足下面区间限制aaa的个数。 L1≤val1⊕a≤R1L2≤val2⊕a≤R2…Ln≤valn⊕a≤Rn\text L_1\leq \text{val}_1\oplus a\leq \text R_1\\\text L_2\leq \text{val}_2\oplus a\leq \text R_2\\ \dots\\ \text L_n\leq \text{val}_n\oplus a\leq \text R_n L1≤val1⊕a≤R1L2≤val2⊕a≤R2…Ln≤valn⊕a≤Rn
考虑其中一种限制直观的想法是Lu≤valu⊕a≤Ru⇒L1⊕val1≤a≤R1⊕val1\text L_u\leq \text{val}_u\oplus a\leq \text R_u\Rightarrow \text L_1\oplus \text{val}_1\ \leq a\leq \text R_1\oplus \text{val}_1Lu≤valu⊕a≤Ru⇒L1⊕val1 ≤a≤R1⊕val1不难发现上面转化是错误的而且可以发现aaa的区间是不连续的需要找出这些不连续的区间
于是就很难处理后面就是讲题人的做法真滴强 我们可以利用 [0,230−1][0,2^{30}-1][0,230−1] 的线段树, 把 [Li,Ri][L_i , R_i][Li,Ri] 分成 logW\log WlogW个连续的区间, 且每个区间的形式是 : [∗∗∗00…00,∗∗∗11…11][***00\dots00,***11\dots 11][∗∗∗00…00,∗∗∗11…11], 这样的区间异或上 vali\text{val}_ivali 后仍然还是一个区间
不妨设∗∗∗***∗∗∗的数量是k
不难发现区间[∗∗∗00…00,∗∗∗11…11][***00\dots00,***11\dots 11][∗∗∗00…00,∗∗∗11…11]抑或上vali\text{val}_ivali的区间是[−−−00…00,−−−,11…11][- - -00\dots00,---,11\dots11][−−−00…00,−−−,11…11] 其中−−−---−−−是(∗∗∗00…00)⊕vali(***00\dots00)\oplus \text{val}_i(∗∗∗00…00)⊕vali的前kkk位的值 比如[10100000,10101111][\color{Blue}{1010} \color{Red}{0000},\color{Blue}{1010} \color{Red}{1111}][10100000,10101111]⊕10011010⇒\oplus\color{Blue}{1001} \color{Red}{1010}\Rightarrow⊕10011010⇒ [00110000,00111111][\color{Blue}{0011} \color{Red}{0000},\color{Blue}{0011} \color{Red}{1111}][00110000,00111111]
蓝色部分异或00111010⊕0011\color{Blue}00111010\oplus001100111010⊕0011原红色部分不变稍微思考一下就知道为什么了。
通过上面操作成功找出这些不连续的区间 然后就sort区间差分乱搞就行。时间复杂度2log可以用线段树维护所有不合法区间的并集把不合法的区间标记为1把时间复杂度降为1log
Code1
#includebits/stdc.h
using namespace std;
using lllong long;
template class Tint T rd()
{T res0;T fg1;char chgetchar();while(!isdigit(ch)) {if(ch-) fg-1;chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res*fg;
}
const int N100010;
int h[N],e[2*N],ne[2*N],w[2*N],idx;
void add(int a,int b,int c){e[idx]b,w[idx]c,ne[idx]h[a],h[a]idx;}
int L[N],R[N];
int val[N];
struct node
{int l,r;
}tree[N*40];
int rt,cnt,n;
vectorpairint,int vec;
void insert(int u,int l,int r,int L,int R,int val)
{if(!u) ucnt;if(LlrR){int qll^(val(~(r-l)));//异或之后的区间[ql,qr]int qrqlr-l;vec.push_back({ql,1});vec.push_back({qr1,-1});return;}int midlr1;if(Lmid) insert(tree[u].l,l,mid,L,R,val);if(Rmid)insert(tree[u].r,mid1,r,L,R,val);
}void dfs(int u,int fa)
{insert(rt,0,(130)-1,L[u],R[u],val[u]);for(int ih[u];i!-1;ine[i]){int ve[i];if(vfa) continue;val[v]val[u]^w[i];dfs(v,u);}
}
int solve()
{sort(vec.begin(),vec.end());vec.push_back({130,0});int ans0;int cur0;for(int i0;ivec.size()-1;i){curvec[i].second;if(curn) ansvec[i1].first-vec[i].first;}return ans;
}
int main()
{nrd();for(int i1;in;i) L[i]rd(),R[i]rd();memset(h,-1,sizeof h);for(int i1;in;i){int urd(),vrd(),wrd();add(u,v,w),add(v,u,w);}dfs(1,0);printf(%d\n,solve());
}比较容易想到的做法就是我们需要求 L1≤val1⊕a≤R1L2≤val2⊕a≤R2…Ln≤valn⊕a≤Rn\text L_1\leq \text{val}_1\oplus a\leq \text R_1\\\text L_2\leq \text{val}_2\oplus a\leq \text R_2\\ \dots\\ \text L_n\leq \text{val}_n\oplus a\leq \text R_n L1≤val1⊕a≤R1L2≤val2⊕a≤R2…Ln≤valn⊕a≤Rn 转化成 [val1⊕a≤R1]➖[val1⊕aL1][val2⊕a≤R2]➖[val2⊕aL2]…[valn⊕a≤Rn]➖[valn⊕aLn][\text{val}_1\oplus a\leq \text R_1]➖[\text{val}_1\oplus a \text L_1]\\ [\text{val}_2\oplus a\leq \text R_2]➖[\text{val}_2\oplus a \text L_2]\\ \dots\\ [\text{val}_n\oplus a\leq \text R_n]➖[\text{val}_n\oplus a \text L_n] [val1⊕a≤R1]➖[val1⊕aL1][val2⊕a≤R2]➖[val2⊕aL2]…[valn⊕a≤Rn]➖[valn⊕aLn] 上面的➖理解为两个集合相减。
实际上我需要求的就是⊕a≤b\oplus a\leq b⊕a≤b的区间显然字典树可以做相当于求⊕a≤b\oplus a\leq b⊕a≤b的数有哪些和第二次杭电I love counting求的步骤一样在Trie树上讨论一下就行。
Code2
#includebits/stdc.h
using namespace std;
using lllong long;
template class Tint T rd()
{T res0;T fg1;char chgetchar();while(!isdigit(ch)) {if(ch-) fg-1;chgetchar();}while( isdigit(ch)) res(res1)(res3)(ch^48),chgetchar();return res*fg;
}
const int N100010;
int h[N],e[2*N],ne[2*N],w[2*N],idx;
void add(int a,int b,int c){e[idx]b,w[idx]c,ne[idx]h[a],h[a]idx;}
int L[N],R[N];
int val[N];
struct node
{int l,r;
}tree[N*40];
int rt,cnt,n;
vectorpairint,int seg[2];
void query(int k,int a,int b)// x^ab
{int urt;int cur0;for(int i29;i0;i--)//30位{int aiai1;int bibi1;if(bi1) //b1{if(ai0) {seg[k].push_back({cur,cur(1i)-1});cur1i;if(!tree[u].r) tree[u].rcnt;utree[u].r;}else{seg[k].push_back({cur(1i),cur(1i)(1i)-1});if(!tree[u].l) tree[u].lcnt;utree[u].l;}}else{if(ai0){if(!tree[u].l) tree[u].lcnt;utree[u].l;}else {cur1i;if(!tree[u].r) tree[u].rcnt;utree[u].r;}}}seg[k].push_back({cur,cur});
}
void dfs(int u,int fa)
{for(int ih[u];i!-1;ine[i]){int ve[i];if(vfa) continue;val[v]val[u]^w[i];dfs(v,u);}
}
int solve()
{vectorpairint,intvec;for(auto t:seg[0]) {vec.push_back({t.first,-1});vec.push_back({t.second1,1});}for(auto t:seg[1]) {vec.push_back({t.first,1});vec.push_back({t.second1,-1});}sort(vec.begin(),vec.end());vec.push_back({130,0});int ans0;int cur0;for(int i0;ivec.size()-1;i){curvec[i].second;if(curn) ansvec[i1].first-vec[i].first;}return ans;
}
int main()
{nrd();for(int i1;in;i) L[i]rd(),R[i]rd();memset(h,-1,sizeof h);for(int i1;in;i){int urd(),vrd(),wrd();add(u,v,w),add(v,u,w);}dfs(1,0);for(int i1;in;i) {if(L[i]0) query(0,val[i],L[i]-1);query(1,val[i],R[i]);}printf(%d\n,solve());
}其实仔细分析应该能写出Trie树的做法不过当时没有分析出来啊www
要加油哦~
