怎么制作动态的网站微信营销软件收费排行榜

怎么制作动态的网站,微信营销软件收费排行榜,三维家3d设计软件免费,网站文章内容的选取题目概括#xff1a; 给定一棵 nnn 个节点的树#xff0c;每个节点有一个初始权值 viv_ivi​#xff08;范围为 [0,230)[0, 2^{30})[0,230)#xff09;。需要处理 qqq 次操作#xff0c;操作分为两种#xff1a; 修改操作 Update x y z#xff1a;将节点 xxx 到 yyy 的简…题目概括给定一棵n nn个节点的树每个节点有一个初始权值v i v_ivi​范围为[ 0 , 2 30 ) [0, 2^{30})[0,230)。需要处理q qq次操作操作分为两种修改操作Update x y z将节点x xx到y yy的简单路径上所有节点的权值异或上z zz。查询操作Query x y询问从节点x xx到y yy的简单路径上的所有节点权值组成的集合中是否存在两个不相等的子集子集指节点集合的子集空集也包含在内使得这两个子集中所有节点权值的异或和相等。如果存在输出YES否则输出NO。问题等价于判断路径上的所有节点权值在异或意义下是否线性相关即是否存在一个非空子集的异或和为0 00。由于权值位数不超过30 3030若路径长度大于30 3030根据鸽巢原理必然线性相关答案一定为YES否则需要实际检查这些权值是否线性相关。From DeepSeek简单来说你需要实现的是对于一颗树你需要实现快速的单链异或单点查询。那我们如果想快速完成操作就想到把修改的东西放到一个区间内用线段树维护这样一段区间的复杂度时O ( log ⁡ 2 n ) O(\log_2 n)O(log2​n)的。那如何把一条链放到一个区间内呢树链剖分考虑一下如果我们在进行重链剖分的同时计算 DFS 序那么同一条重链上的结点的时间戳一定是连续的。所以修改的时候我们用类似求 LCA 的方法进行操作每次更新这条重链时间戳所对应的区间然后跳到当前链链头的父亲。这样我们就在O ( log ⁡ 2 n ) O(\log_2 n)O(log2​n)处理了一个区间而树链剖分在最坏情况下会有log ⁡ 2 n \log_2 nlog2​n个区间所以插入的时间复杂对时O ( log ⁡ 2 2 n ) O(\log_2^2n)O(log22​n)级别的。考虑查询。这里用到一个 trick。如果集合的规模很大那么答案必然有解。这道题树上所有结点的权值小于2 30 2^{30}230这意味着如果在31 3131个里面选择一些一共有2 31 2^{31}231种方案根据抽屉原理必然有一种满足要求的方案。对于l e n ≤ 30 len \le 30len≤30的部分来说考虑异或空间线性基的性质显然基中不能出现异或值为0 00的数。这意味着有两个方法表示同一个数。故一定有方法使两个子集的异或和相同。#includebits/stdc.h#definels(p1)#definers(p1|1)usinglllonglong;constexprintN1e55;std::vectorintadj[N];structSegment_Tree{structNode{intnum,l,r;inttag;}t[N2];voidbuild(intp,intpl,intpr){t[p].lpl;t[p].rpr;t[p].numt[p].tag0;if(plpr)return;intmidplpr1;build(ls,pl,mid);build(rs,mid1,pr);}voidpush_down(intp){if(t[p].tag){t[ls].tag^t[p].tag;t[ls].num^t[p].tag;t[rs].tag^t[p].tag;t[rs].num^t[p].tag;t[p].tag0;}}voidupdate(intp,intl,intr,intval){if(t[p].lr||t[p].rl)return;if(lt[p].lt[p].rr){t[p].num^val;t[p].tag^val;return;}push_down(p);update(ls,l,r,val);update(rs,l,r,val);}intquery(intp,intpos){if(t[p].lt[p].r)returnt[p].num;push_down(p);intmidt[p].lt[p].r1;if(posmid)returnquery(ls,pos);elsereturnquery(rs,pos);}voidprint(intp){if(t[p].lt[p].r)std::coutt[p].num ;elsepush_down(p),print(ls),print(rs);}}tree;intfa[N],dep[N],siz[N],top[N],dfn[N],v[N];inttim;voiddfs1(intu,intf){fa[u]f;dep[u]dep[f]1;siz[u]1;for(intv:adj[u]){if(v!f){dfs1(v,u);siz[u]siz[v];}}}voiddfs2(intu,intf){top[u]f;dfn[u]tim;intmx-1,s-1;tree.update(1,tim,tim,v[u]);for(intv:adj[u]){if(v!fa[u]siz[v]mx){mxsiz[v];sv;}}if(s!-1)dfs2(s,f);for(intv:adj[u]){if(v!fa[u]v!s)dfs2(v,v);}}voidupdate(intx,inty,intval){while(top[x]!top[y]){if(dep[top[x]]dep[top[y]])std::swap(x,y);tree.update(1,dfn[top[x]],dfn[x],val);xfa[top[x]];}if(dfn[x]dfn[y])std::swap(x,y);tree.update(1,dfn[x],dfn[y],val);}intlca(intu,intv){while(top[u]!top[v]){if(dep[top[u]]dep[top[v]])vfa[top[v]];elseufa[top[u]];}if(dep[u]dep[v])returnu;returnv;}constexprintM31;structleaner_basis{intb[M];voidinit(){memset(b,0,sizeofb);}boolinsert(intx){for(intiM-1;i0;i--){if(!(x(1i)))continue;if(!b[i]){b[i]x;return1;}x^b[i];}returnfalse;}}basis;intn,q,x,y,z;intmain(){std::cinnq;for(inti1;in;i)std::cinv[i];for(inti1;in;i){intu,v;std::cinuv;adj[u].push_back(v);adj[v].push_back(u);}tree.build(1,1,n);dfs1(1,0);dfs2(1,1);while(q--){std::string s;std::cinsxy;if(s[0]U){std::cinz;update(x,y,z);}else{intllca(x,y);intdisdep[x]dep[y]-2*dep[l]1;if(dis30)std::coutYES\n;else{basis.init();boolflagfalse;if(!basis.insert(tree.query(1,dfn[l])))flag1;if(!flag)while(x!l){if(!basis.insert(tree.query(1,dfn[x]))){flag1;break;}xfa[x];}if(!flag)while(y!l){if(!basis.insert(tree.query(1,dfn[y]))){flag1;break;}yfa[y];}std::cout(flag?YES\n:NO\n);}}}}