网上下载的免费网站模板怎么用,重庆网站建设技术外包,wordpress 国产插件,国外互联网资讯网站正题
题目链接:https://www.luogu.org/problemnew/show/P5127 题目大意
定义一个序列的子异和为所有自己的异或和的和。 然后有点权的树#xff0c;要求支持路径异或和路径求子异和。 解题思路
首先树链剖分是肯定的#xff0c;然后我们考虑用哪个数据结构。 从每个位单独…正题
题目链接:https://www.luogu.org/problemnew/show/P5127 题目大意
定义一个序列的子异和为所有自己的异或和的和。 然后有点权的树要求支持路径异或和路径求子异和。 解题思路
首先树链剖分是肯定的然后我们考虑用哪个数据结构。 从每个位单独分析一个长度为nnn的集合然后cntxcnt_xcntx表示有多少数的二进制第xxx位为000 然后对于一个位可以贡献的答案是2cntx−1∗2n−cntx2n−12^{cnt_x-1}*2^{n-cnt_x}2^{n-1}2cntx−1∗2n−cntx2n−1但是若cntx0cnt_x0cntx0时答案是0。 也就是每个位如果cntx≠0cnt_x\neq 0cntx̸0那么就可以贡献2x∗2n−12^x*2^{n-1}2x∗2n−1的答案。
其实我们发现区间或值为sum(or)sum(or)sum(or)那么答案就是2n−1∗sum(or)2^{n-1}*sum(or)2n−1∗sum(or)。
然后我们区间查询就可以用线段树搞了我们考虑如何区间查询 我们依旧是每个位进行分析若第xxx位为0那么保持不变如果为1那么久等于∼sum(and)\sim sum(and)∼sum(and)
所以我们可以得出 sum(or)′(sum(or)amp;∼a)∣(∼sum(and)amp;a)sum(or)#x27;(sum(or)\amp; \sim a)|(\sim sum(and)\amp;a)sum(or)′(sum(or)∼a)∣(∼sum(and)a) 然后我们多维护一个sum(and)sum(and)sum(and) sum(and)′(sum(and)amp;∼a)∣(∼sum(or)amp;a)sum(and)#x27;(sum(and)\amp; \sim a)|(\sim sum(or)\amp;a)sum(and)′(sum(and)∼a)∣(∼sum(or)a) 圆满解决该题 codecodecode
#includecstdio
#includealgorithm
#define ll long long
using namespace std;
const ll N201000,XJQ1e97;
struct Tree_node{ll l,r,sor,sand,lazy;
};
struct Edge_node{ll to,next;
}a[N*2];
ll tot,ls[N],n,m,w[N],cnt,pow[N];
ll id[N],siz[N],seg[N],son[N],top[N],dep[N],f[N];
struct Line_Cut_Tree{Tree_node t[N*4];ll ans,Dig;void build(ll x,ll l,ll r){t[x].ll;t[x].rr;if(lr){t[x].sort[x].sandw[id[l]];return;}ll mid(lr)/2;build(x*2,l,mid);build(x*21,mid1,r);t[x].sort[x*2].sor|t[x*21].sor;t[x].sandt[x*2].sandt[x*21].sand;}void updata(ll x,ll w){ll sort[x].sor,sandt[x].sand;t[x].sor(sor(~w))|((~sand)w);t[x].sand(sand(~w))|((~sor)w);t[x].lazy^w;}void downdata(ll x){if(!t[x].lazy) return;updata(x*2,t[x].lazy);updata(x*21,t[x].lazy);t[x].lazy0;}ll ask(ll x,ll l,ll r){if(t[x].llt[x].rr)return t[x].sor;downdata(x);if(rt[x*2].r) return ask(x*2,l,r);if(lt[x*21].l) return ask(x*21,l,r);return ask(x*2,l,t[x*2].r)|ask(x*21,t[x*21].l,r);t[x].sort[x*2].sor|t[x*21].sor;t[x].sandt[x*2].sandt[x*21].sand;}void change(ll x,ll l,ll r,ll val){if(t[x].llt[x].rr){updata(x,val);return;}downdata(x);if(rt[x*2].r) change(x*2,l,r,val);else if(lt[x*21].l) change(x*21,l,r,val);else change(x*2,l,t[x*2].r,val),change(x*21,t[x*21].l,r,val);t[x].sort[x*2].sor|t[x*21].sor;t[x].sandt[x*2].sandt[x*21].sand;}
}Tree;
void addl(ll x,ll y)
{a[tot].toy;a[tot].nextls[x];ls[x]tot;
}
void dfs(ll x,ll fa){siz[x]1;f[x]fa;dep[x]dep[fa]1;for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa) continue;dfs(y,x);siz[x]siz[y];if(siz[son[x]]siz[y])son[x]y;}
}
void dfs2(ll x,ll fa){seg[x]cnt;id[cnt]x;if(son[x]){top[son[x]]top[x];dfs2(son[x],x);}for(ll ils[x];i;ia[i].next){ll ya[i].to;if(yfa||yson[x]) continue;top[y]y;dfs2(y,x);}
}
void push_change(ll x,ll y,ll z){while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])swap(x,y);Tree.change(1,seg[top[x]],seg[x],z);xf[top[x]];}if(dep[x]dep[y]) swap(x,y);Tree.change(1,seg[x],seg[y],z);return;
}
ll push_ask(ll x,ll y){ll cnt0,ans0;while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])swap(x,y);ans|Tree.ask(1,seg[top[x]],seg[x]);cntseg[x]-seg[top[x]]1;xf[top[x]];}if(dep[x]dep[y]) swap(x,y);ans|Tree.ask(1,seg[x],seg[y]);cntseg[y]-seg[x]1;return ans*pow[cnt-1]%XJQ;
}
int main()
{scanf(%lld%lld,n,m);for(ll i1;in;i){ll x,y;scanf(%lld%lld,x,y);addl(x,y);addl(y,x);}pow[0]1;for(ll i1;in;i)pow[i](pow[i-1]*2)%XJQ;for(ll i1;in;i)scanf(%lld,w[i]);dfs(1,0);top[1]1;dfs2(1,0);Tree.build(1,1,n);for(ll i1;im;i){ll ts,a,b,c;scanf(%lld%lld%lld,ts,a,b);if(ts1)printf(%lld\n,push_ask(a,b));elsescanf(%lld,c),push_change(a,b,c);}
}
