成都网站建设思乐科技公司清远公司网站建设

成都网站建设思乐科技公司,清远公司网站建设,赶集网官网,广告模板免费2025-12-11 hetao1733837的刷题笔记 LG5787 【模板】线段树分治 / 二分图 原题链接#xff1a;【模板】线段树分治 / 二分图 分析 我好像有点理解了…… 13点39分 卧槽#xff0c;豁然开朗#xff01;这玩意就是说利用线段树#xff0c;把一段区间扔进整棵树#xf…2025-12-11 hetao1733837的刷题笔记LG5787 【模板】线段树分治 / 二分图原题链接【模板】线段树分治 / 二分图分析我好像有点理解了……13点39分卧槽豁然开朗这玩意就是说利用线段树把一段区间扔进整棵树然后线段树每个点用v e c t o r vectorvector记录这段时间消失的节点在分治的时候取出对应时间段的线段树然后判断是不是二分图就行了并查集。行继续理解撤销。那似乎很容易想了。哎我的二分图并不熟练。正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN200005;intn,m,k;intfa[N1],sz[N1];structnode{intp,v;node(intpos,intval){ppos;vval;}};stacknodefather,size;vectorinttr[N2];vectorboolres;intfind(intx){returnxfa[x]?x:find(fa[x]);}voidmerge(intx,inty){intfxfind(x),fyfind(y);if(fxfy)return;if(sz[fx]sz[fy])swap(fx,fy);size.push(node(fy,sz[fy]));sz[fx]sz[fy];father.push(node{fy,fa[fy]});fa[fy]fx;}voidwork(){fa[father.top().p]father.top().v;father.pop();sz[size.top().p]size.top().v;size.pop();}voidmodify(intp,intl,intr,ints,intt,intval){if(slrt){tr[p].push_back(val);return;}intmid(lr)1;if(smid)modify(p1,l,mid,s,t,val);if(tmid)modify(p1|1,mid1,r,s,t,val);}structedge{intu,v;}e[N];voidsolve(intp,intl,intr){autolvlfather.size();boolflag1;for(autotmp:tr[p]){intfufind(e[tmp].u),fvfind(e[tmp].v);if(fufv){for(intil;ir;i)res.push_back(false);flagfalse;break;}merge(e[tmp].u,e[tmp].vn);merge(e[tmp].v,e[tmp].un);}if(flag){if(lr){res.push_back(true);}else{intmid(lr)1;solve(p1,l,mid);solve(p1|1,mid1,r);}}while(father.size()lvl){work();}}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnmk;for(inti1;i(n1);i){fa[i]i;sz[i]1;}for(inti1;im;i){intx,y,l,r;cine[i].ue[i].vlr;modify(1,1,k,l1,r,i);}solve(1,1,k);for(autov:res){if(v)coutYes\n;elsecoutNo\n;}}LG4219 [BJOI2014] 大融合原题链接[BJOI2014] 大融合分析首先应该明确的是如何求取树上经过某一条边的路径数量比较显然的就是呃还是有个图好一点我找一个。好的对于节点1 11和节点2 22之间那一条边其左部有2 , 4 , 5 , 8 , 9 , 10 2,4,5,8,9,102,4,5,8,9,10共6 66个点其右部有1 , 3 , 6 , 7 1,3,6,71,3,6,7共4 44个点则经过该边的路径数量共6 × 4 24 6\times 4246×424条。从这个角度出发我要多维护每个连通块内部每个点的子树大小。同样对于时间去处理那我会有种离线思路。我直接建出最终的树然后对于一条边的加入令其在初始时间到加入时间这段时间不可用就变成了模板但我好像不太会动态维护子树大小细想起来其实也不难吧……好像给的思路差不多行我搓一下代码。比模板多的恐怕也只有各种map了其实可以统一存进一个s t r u c t structstruct里显得优雅一些正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN100005;charop;intn,q,fa[N],sz[N];structnode{intpos,val;node(intp,intv){posp;valv;}};stacknodesiz,father;intfind(intx){returnxfa[x]?x:find(fa[x]);}voidmerge(intx,inty){xfind(x);yfind(y);if(xy)return;if(sz[x]sz[y])swap(x,y);siz.push(node(x,sz[x]));sz[x]sz[y];father.push(node(y,fa[y]));fa[y]x;}voidwork(){fa[father.top().pos]father.top().val;father.pop();sz[siz.top().pos]siz.top().val;siz.pop();}vectorpairint,inttr[N4];voidmodify(intp,intl,intr,ints,intt,pairint,intv){if(slrt){tr[p].push_back(v);return;}intmid(lr)1;if(smid)modify(p1,l,mid,s,t,v);if(tmid)modify(p1|1,mid1,r,s,t,v);}inttim;mappairint,int,inttims;structopt{intl,r;pairint,intv;}opp[N3];intncnt;mapint,intask;mapint,pairint,intasklr;intans[N3];voidsolve(intp,intl,intr){intlvlfather.size();for(autou:tr[p]){merge(u.first,u.second);}if(lr){if(ask[l]){intxasklr[l].first,yasklr[l].second;ans[l]sz[find(x)]*sz[find(y)];}}else{intmid(lr)1;solve(p1,l,mid);solve(p1|1,mid1,r);}while(father.size()lvl){work();}}signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnq;for(inti1;in;i){fa[i]i;sz[i]1;}for(intcs1;csq;cs){cinop;intx,y;cinxy;if(opA){tims[{x,y}]tim;}else{pairint,inttmp{x,y};opp[ncnt]{tims[tmp],tim,tmp};ask[tim]1;asklr[tim]tmp;tims[tmp]tim;}}inttmptim;for(autoi:tims){opp[ncnt]{tims[i.first],tmp,i.first};}for(inti1;incnt;i){modify(1,1,tim,opp[i].l,opp[i].r,opp[i].v);}solve(1,1,tim);for(inti1;itim;i){if(ask[i]){coutans[i]\n;}}}LG2056 [ZJOI2007] 捉迷藏原题链接[ZJOI2007] 捉迷藏分析这不是我昨天被h a c k hackhack的点分树题吗今天又碰到了这是让我和他死磕到底吗大课间之前最好能吃出来坏了代码里有b i t s e t bitsetbitset我还没学那咋办现学并不很难吧难道我可以做LG11831 [省选联考 2025] 追忆了假的黑题要是随便做场上碰见的都成不可做题了。从点分治的角度去想距离最长的点显然最好分别在两棵子树内。改变颜色似乎是在一段时间不可选亮了一段时间可选不亮那就成了板子真假的找题解求证一下。错误总结错误点在于两点最长距离的计算方式正确的方式是找到树上黑点作为端点构成的直径然后对于每次新加入黑点点集后的直径只可能维持不变、一个端点不变另一个端点变成新加入的黑点。感觉被骗了ber阴成啥了这个所谓直径的说法不过是我说法的形式化感觉我理解地还算对。但是树上最长链问题就要往直径上想详情参考L G 8173 [ C E O I 2021 ] N e w s p a p e r s LG8173 [CEOI 2021] NewspapersLG8173[CEOI2021]Newspapers。正解#includebits/stdc.h#defineintlonglongusingnamespacestd;constintN500005,M500005;intn,q;charop;structnode{intpos,val;node(intp,intv){posp;valv;}};vectorinte[N];intsz[N],de[N],fa[N],top[N],son[N];//树剖求 LCAvoiddfs1(intu,intpa){de[u]de[pa]1;fa[u]pa;sz[u]1;for(autov:e[u]){if(vpa)continue;dfs1(v,u);sz[u]sz[v];if(sz[v]sz[son[u]])son[u]v;}}voiddfs2(intu,inttp){top[u]tp;if(son[u]){dfs2(son[u],tp);}for(autov:e[u]){if(vfa[u]||vson[u])continue;dfs2(v,v);}}intLCA(intx,inty){while(top[x]!top[y]){if(de[top[x]]de[top[y]])swap(x,y);xfa[top[x]];}if(de[x]de[y])returnx;returny;}intdist(intx,inty){returnde[x]de[y]-de[LCA(x,y)]*2;}vectorinttr[N2];voidmodify(intp,intl,intr,ints,intt,intval){if(slrt){tr[p].push_back(val);return;}intmid(lr)1;if(smid)modify(p1,l,mid,s,t,val);if(tmid)modify(p1|1,mid1,r,s,t,val);}stackpairint,intstk;intu,v,ans[N];voidsolve(intp,intl,intr){autolvlstk.size();for(autox:tr[p]){stk.push({u,v});if(!u!v){ux;vx;}else{vectorintvct{dist(u,v),dist(u,x),dist(x,v)};sort(vct.begin(),vct.end(),greaterint());if(vct[0]dist(u,x))vx;elseif(vct[0]dist(x,v))ux;}}if(lr){if(!u||!v)ans[l]-1;elseans[l]dist(u,v);}else{intmid(lr)1;solve(p1,l,mid);solve(p1|1,mid1,r);}while(stk.size()!lvl){autotopstk.top();utop.first;vtop.second;stk.pop();}}intlst[N];bitsetNcol;bitsetMha;signedmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(inti1;in;i){intu,v;cinuv;e[u].push_back(v);e[v].push_back(u);}dfs1(1,0);dfs2(1,1);for(inti1;in;i){lst[i]1;}cinq;for(inti2;iq1;i){cinop;if(opC){intx;cinx;if(!col[x]){col[x]1;modify(1,1,q2,lst[x],i,x);}else{col[x]0;lst[x]i;}}else{ha[i]1;}}for(inti1;in;i){if(!col[i]){modify(1,1,q2,lst[i],q2,i);}}solve(1,1,q2);for(inti1;iq2;i){if(ha[i])coutans[i]\n;}}LG4556 【模板】线段树合并 / [Vani有约会] 雨天的尾巴原题链接【模板】线段树合并 / [Vani有约会] 雨天的尾巴分析啊难道开值域棵线段树有点恐怖了假的线段树合并即可。思想我显然理解了但是吧pyd上课不变代码写全是何意味发现还得套 LCA正解#includebits/stdc.husingnamespacestd;constintN100005;constintV100001;intn,m,f[N][22],de[N],ans[N];vectorinte[N];structnode{intid,cnt;friendbooloperator(node tmp1,node tmp2){if(tmp1.cnttmp2.cnt){returntmp1.idtmp2.id;}returntmp1.cnttmp2.cnt;}friendnodeoperator(node tmp1,node tmp2){return(node){tmp1.id,tmp1.cnttmp2.cnt};}};vectornodetag[N];structsegtree{node tr[N*40];intls[N*40],rs[N*40];intncnt;voidinit(){ncntn;for(inti1;in;i){tr[i]{0,0};ls[i]rs[i]0;}}voidpushup(intp){tr[p]max(tr[ls[p]],tr[rs[p]]);}voidmodify(intp,intl,intr,node val){if(r-l1){tr[p]valtr[p];return;}intmid(lr)1;if(val.idmid){if(!ls[p]){ls[p]ncnt;tr[ls[p]]{0,0};}modify(ls[p],l,mid,val);}else{if(!rs[p]){rs[p]ncnt;tr[rs[p]]{0,0};}modify(rs[p],mid,r,val);}pushup(p);}voidmerge(intx,inty,intl,intr){if(!x||!y)return;if(r-l1){tr[x]tr[x]tr[y];return;}intmid(lr)1;if(ls[x]ls[y]){merge(ls[x],ls[y],l,mid);}elseif(ls[y]){ls[x]ls[y];}if(rs[x]rs[y]){merge(rs[x],rs[y],mid,r);}elseif(rs[y]){rs[x]rs[y];}pushup(x);}}T;voidinit(){for(inti1;i20;i)for(intu1;un;u)f[u][i]f[f[u][i-1]][i-1];}voiddfs(intu){for(autov:e[u]){if(v!f[u][0]){f[v][0]u;de[v]de[u]1;dfs(v);}}}intlca(intx,inty){if(de[x]de[y]){swap(x,y);}intkde[x]-de[y];for(inti0;i20;i){if(k(1i))xf[x][i];}if(xy)returny;for(inti20;i0;i--)if(f[x][i]!f[y][i]){xf[x][i];yf[y][i];}returnf[x][0];}voidMerge(intu){for(autov:e[u]){if(v!f[u][0]){Merge(v);T.merge(u,v,0,V);}}for(autok:tag[u]){T.modify(u,0,V,k);}ans[u]T.tr[u].id;}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinnm;T.init();for(inti1;in;i){inta,b;cinab;e[a].push_back(b);e[b].push_back(a);}dfs(1);init();for(inti1;im;i){intx,y,z;cinxyz;intLCAlca(x,y);tag[x].push_back((node){z,1});tag[y].push_back((node){z,1});tag[LCA].push_back((node){z,-1});if(f[LCA][0]0)tag[f[LCA][0]].push_back((node){z,-1});}Merge(1);for(inti1;in;i){coutans[i]\n;}return0;}何意味凭啥我左移 5 位开 32 倍凭啥卡我开40倍你过了LG6773 [NOI2020] 命运原题链接[NOI2020] 命运分析19点28分不行我先写到蓝这样洛谷上蓝题数量就和黄题一样了嘻嘻。20点37分哦终于把下面那道题过了。回家打 CF这题太……难以评价……正解LG2279 [HNOI2003] 消防局的设立原题链接[HNOI2003] 消防局的设立分析自己打了一发过了小样例交上去 10pts哭晕在厕所/(ㄒoㄒ)/~~显然我是从 ZR 题单的树形D P DPDP里把这题扒出来的所以直接树形D P DPDP设f u , 0 / 1 / 2 f_{u,0/1/2}fu,0/1/2​表示u uu节点其子树内最近的消防站距离他0 / 1 / 2 0/1/20/1/2的建造消防站个数。错误分析我们只考虑了u uu的子树但是u uu为什么不能从其祖先转移而来那么多设两种状态即设f u , 0 / 1 / 2 / 3 / 4 f_{u,0/1/2/3/4}fu,0/1/2/3/4​表示从节点u uu向上覆盖2 / 1 / 0 / − 1 / − 2 2/1/0/-1/-22/1/0/−1/−2层的最小消防站个数。转移显然f u , 0 1 ∑ v ∈ s o n [ u ] f v , 4 f_{u, 0}1\sum\limits_{v\in son[u]}f_{v, 4}fu,0​1v∈son[u]∑​fv,4​f u , 1 min ⁡ v ∈ s o n [ u ] ( f v , 0 ∑ t ∈ s o n [ u ] , t ≠ v f t , 3 , f u , 0 ) f_{u, 1}\min\limits_{v\in son[u]}(f_{v,0}\sum\limits_{t\in son[u],t\neq v}f_{t,3}, f_{u,0})fu,1​v∈son[u]min​(fv,0​t∈son[u],tv∑​ft,3​,fu,0​)f u , 2 min ⁡ v ∈ s o n [ u ] ( f v , 1 ∑ t ∈ s o n [ u ] , t ≠ v f t , 2 , f u , 0 , f u , 1 ) f_{u, 2}\min\limits_{v\in son[u]}(f_{v,1}\sum\limits_{t\in son[u],t\neq v}f_{t,2}, f_{u,0},f_{u,1})fu,2​v∈son[u]min​(fv,1​t∈son[u],tv∑​ft,2​,fu,0​,fu,1​)f u , 3 min ⁡ ( ∑ v ∈ s o n [ u ] f v , 2 , f u , 0 , f u , 1 , f u , 2 ) f_{u,3}\min(\sum\limits_{v\in son[u]}f_{v,2},f_{u, 0},f_{u, 1},f_{u, 2})fu,3​min(v∈son[u]∑​fv,2​,fu,0​,fu,1​,fu,2​)f u , 4 min ⁡ ( ∑ v ∈ s o n [ u ] f v , 3 , f u , 0 , f u , 1 , f u , 2 , f u , 3 ) f_{u,4}\min(\sum\limits_{v\in son[u]}f_{v,3},f_{u, 0},f_{u, 1},f_{u, 2},f_{u, 3})fu,4​min(v∈son[u]∑​fv,3​,fu,0​,fu,1​,fu,2​,fu,3​)正解直接建有向少记录一个f a fafa。#includebits/stdc.husingnamespacestd;constintN1005;intn;vectorinte[N];intf[N][5];voiddfs(intu){f[u][0]1;f[u][3]0;f[u][4]0;for(autov:e[u]){dfs(v);f[u][0]f[v][4];f[u][3]f[v][2];f[u][4]f[v][3];}if(e[u].size()0){f[u][1]f[u][2]1;}else{f[u][1]f[u][2]0x3f3f3f3f;for(autov:e[u]){intf1f[v][0],f2f[v][1];for(autot:e[u]){if(vt)continue;f1f[t][3];f2f[t][2];}f[u][1]min(f[u][1],f1);f[u][2]min(f[u][2],f2);}}for(inti1;i4;i){f[u][i]min(f[u][i],f[u][i-1]);}}intmain(){ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cinn;for(inti2;in;i){inta;cina;e[a].push_back(i);}dfs(1);coutf[1][2];}