抱歉,您的浏览器无法访问本站
本页面需要浏览器支持(启用)JavaScript
了解详情 >

传送门 考虑离线+差分。 将∑l≤i≤rdep[LCA(i,z)]\sum _{l \le i \le r} dep[LCA(i,z)]∑l≤i≤r​dep[LCA(i,z)]转化成∑1≤i≤rdep[LCA(i,z)]−∑1≤i≤l−1dep[LCA(i,z)]\sum _{1 \le i \le r} dep[LCA(i,z)]-\sum _{1 \le i \le l-1} dep[L...

传送门 本质一样的一道YNOI 首先明确一件事情,这个换根其实是吓你的, 1.1.1.只有最近的一次换根才会对答案有影响(显然) 2.2.2.分情况讨论,我们始终以111节点为根,设现在查询的节点为uuu,上一次换根的根为rtrtrt(rtrtrt是一个假的根) ,我们画出333个图: 若u==rtu==rtu==rt,显然现在查询的是整棵树,对应到区间[1,n][1,n][1,n]: 若...

传送门 树链剖分裸题 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979...

传送门 安装操作其实就是把这个节点及其祖先节点变成111,卸载操作其实就是把这个节点及其子树之内的所有节点变成000 树链剖分实现即可。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686...

传送门 线段树实现区间查询最大值,查询最小值,查询和,区间∗−1*-1∗−1,前面333种都没有什么好讲的,最后一种就是把区间和∗−1*-1∗−1,最小值,最大值交换以后∗−1*-1∗−1 注意:下标从000开始。 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849...

传送门 翻译有误,应该是查询uuu到vvv上最大值。 线段树查询最大值和区间+1+1+1, 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980...

传送门 需要一棵支持区间加,区间和查询的线段树 其他没什么好说的,注意开long\rm longlong long\rm longlong 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768...

传送门 树链剖分模板题,用支持区间加,区间覆盖,查询区间最大的线段树实现。 注意覆盖标记cotagcotagcotag优先级比加标记tagtagtag要高,所以覆盖时直接设tag=0tag=0tag=0 需要把ChangeChangeChange操作转化为顶点U[k]U[k]U[k]和V[k]V[k]V[k]的覆盖操作 其他没什么好说的,注意细节即可 12345678910111213141...

传送门 考虑每个宗教建立一棵线段树,但是空间会炸,考虑动态开点。 时间复杂度O(nlog⁡n)O(n \log n)O(nlogn),空间复杂度O(nlog⁡n)O(n \log n)O(nlogn) 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525...

传送门 考虑先把这张图的最小生成树GGG建出来,假设查询的边为EEE, 发现: 1.1.1.如果EEE本来就在GGG里面,那么直接输出GGG的边权和,因为没有比这个更优的解。 2.2.2.如果EEE不在GGG里面,那么EEE一定和GGG 形成一个环,根据贪心的原则,我们把这条环上面最大边权的边删去,这样新的图仍然是一棵树,而且边权和最小。 在实际操作过程中,我们并不用找到那个环,可以这么想,...