加入

嗨嗨嗨

PS：由于本菜坤能力有限，把很多实边写成了实链，大家就将就着看吧嘿嘿。 引入：仨链部分 我们一般提到的三种剖分是：重链剖分，实链剖分，和长链剖分。 前面我们已经讲过的树链剖分实际上就是重链剖分的别称。长链剖分不太常用（但是sslz_fsy非常强三个都会orz），而本次LCT用到的就是实链剖分。 实链部分 这个不需要特别学习，你只需要知道这种剖分的优点在于：可以调整，即可以变化。（不像重链剖分那样是固定的） 同样，每个节点对儿子只有一个实链，其它都是虚链。这样做的原因是方便splay来维护。（后话） 它的体现是：所有子节点都有father，但father的son只有实链链接的子节点或者原树上的父节点。意思是说你从叶子节点可以一直跳跳跳跳到根节点，每个叶子节点都可以，但对于一个根节点往下走，它的路径是唯一的。 接下来我们说一下，splay在树里面的运转方式。 SPLAY 首先明确：每一个splay维护的是一个深度严格单调递增的链（简单说就是一个严格从祖先到后代的链）。用实链连接起来的一堆点在同一个splay里面。所以整个森林实际上也有很多个splay。 所以说实边虚边在LCT中的体现实际上就是在不在一个splay里面。 每个splay结点维护的值是其在splay中的整个子树的信息和。（比如取最大最小啦，求和或者异或啦） 因为维护的是信息和，所以在作修改的时候为了不影响到别的点，你要先splay上去。 这样就方便我们调用。至于为什么方便，我也说不清楚 (手动doge)。 基本函数学习 1.ACCESS access函数是非常基本的函数。非常重要。它的意义是：将该点到根节点的这个路径上的所有链变成实链。 这句话的潜含义有两点。 1. 因为每个点只有一条向下的实链，所以实际上它是将一些实边转换成了轻边，然后硬生生的把一些虚边变成了实边。 2. 因为splay维护实边连接起来的点，所以现在，根节点到该节点路径上的所有点包括它们二位都在一个splay里面了。 既然在一个splay里面了，那，就好办了噻嘿嘿。通过完美的pushup和pushdown，我们就能轻松调用里面的信息了。 相信我，代码比你们想的简单多了。 2.MARKEROOT makeroot的含义是，将这个点变成所在树的根，也就是换根。怎么办呢QAQ？ 首先，为了让这位可怜的点点和十万八千里外的根节点联系上，我们进行的第一步是：access。 现在它们在一个splay里面啦！然后呢？然后我们会注意到这么一个性质。 由于splay按照深度严格递增维护，所以access完后的这个点是splay里面深度最深的点，换句话说 > 将这个点SPLAY到根节点，它就不会有右儿子了(OVO) 于是我们splay了。emm然后?既然我们要换根，那如何在splay里面，把这个点变成深度最浅的那个根呢？ 所以我们用上了大名鼎鼎的：翻转打标记。想想看，splay完后的这个splay实际上很左倾（doge)，但翻转完后，就变成彻彻底底的右倾了（doge。 是的，总的来说，access，splay，打标记。 3.FINDROOT findroot顾名思义，找这个点所在树的根节点。 同样，为了和根节点擦出 爱的 火花，我们要先access一下。然后splay。 还是一个左倾树（乱编的名字），那我们就一直找左儿子，一直找下去就可以啦！记得下传标记哦！ 顺带一提，为了防止pushup对splay上维护的值产生影响，我们要把这个点splay后才能pushup。 4.LINK 链接操作，非常优秀。 对于两个点要链接，首先我们还是要makeroot其中一个点。然后要判重的话，就要判findroot另一个点的返回值是不是上一个点，是，说明有边不需要了，不是，说明要连边。 5.CUT 删边操作，也很优秀(万物皆油锈优秀)。 对于两个点要删边，首先我们还是要makeroot其中一个点。然后access，splay都是常规操作。然后如果要判是否有边的话，就要判断三个东西。 第一是findroot另一个点是不是上一个点，注意findroot完后，上一个点又又被splay成了根，覆盖了splay(y)。 第二个自然是这个点的父亲是不是上一个点。 第三个就是这个点不能有左儿子。 为什么呢？ 因为findroot第二个点的时候把第一个点旋转成了splay 的根，则第二个点现在是第一个点的右儿子。而如果两者有边，说明二者深度必然是+1关系的，那在splay上，根的右儿子不能有左儿子。 6.SPLIT 提取操作，非常优秀。 提取指定两点间的链，方便查询，思想跟树剖有点相似。具体而言就是makeroot，access，splay，查询。 7.SPLAY变化了。 由于LCT的性质，导致翻转标记有时候可能在上面没有下传。所以splay之前，我们有一个下传标记的工作。 具体而言就是开一个栈，不断跳父亲把能装的都装进去，然后从上至下pushdown。 同样与splay本身不同的是，此处我们判定旋转到根的意义就是，根的父亲的儿子不是根。（实边定义）（认父不认子） 所以noroot操作就是这样的： 同时在rotate里面也要用noroot判断。 另外顺带一提，在LCT里面，我们建议pushdown的时候，每次都把自己孙子给push了。 也就是这样： 据说这样很严谨不会被卡？ pushup就是基本的操作就不写了。 例题可以参照某谷省选斗兽场的动态树。 放一个LCT某谷模板的代码。 > 解释一下，对于3号操作，修改操作，为了防止修改完后对平衡树造成不当影响，我们先把它转到根，再修改。

桃心输出 后续还会优化改进 第四次改进 输入样例 输出样例 注释:输入数字为桃心底部大三角的高

祝各位老师教师节快乐！

@覃 我也在小五班奥数群里，你有隐私设置，我加不了你，你加一下我，或取消一下隐私设置

PS:我的个人博客出了，点击访问

题是这样的（没错就是欢乐赛题）：给出 nnn，求 a+b+c=na + b + c = na+b+c=n 中 a,b,ca,b,ca,b,c 的方案数，a,b,ca,b,ca,b,c 须满足 0<a<b<c≤n0 \lt a \lt b \lt c \leq n0<a<b<c≤n。保证 n≤1200n \le 1200n≤1200。 形象化的话答案就是：∑i=1⌊n3⌋−1⌈n−i2⌉−1−i\sum ^ {\lfloor \frac{n}{3} \rfloor-1} _ {i=1} \lceil {\frac{n-i}{2}} \rceil - 1 - i∑i=1⌊3n ⌋−1 ⌈2n−i ⌉−1−i。 由于我太卷了，从开始的 O(n2)O(n^2)O(n2) 卷到了现在的 O(n)O(n)O(n)，想问一下大佬可能做到时间复杂度为 O(1)O(1)O(1) 吗。

#include<iostream> using namespace std; void stoh(string s,int a[]){ a[0]=s.length(); for(int i=1;i<=a[0];i++){ a[i]=s[a[0]-i]-'0'; } } void mul(int a[],int b[],int c[]){ c[0]=a[0]+b[0]-1; for(int i=1;i<=a[0];i++){ for(int j=1;j<=b[0];j++){ c[i+j-1]+=a[i]*b[j]; c[i+j]+=c[i+j-1]/10; c[i+j-1]%=10; } } if(c[c[0]+1]>0)c[0]; while(c[c[0]]==0&&c[0]>1)c[0]--; } void printf(int c[]){ for(int i=1;i<=c[0];i){ cout<<c[0]; } } int main(){ string s1,s2; int a[105]={},b[105]={},c[105]={}; cin>>s1>>s2; stoh(s1,a); stoh(s1,b); mul(a,b,c); return 0; }

申请了一个GitHub Galaxy，果然GitHub速度蹭蹭快

https://www.acgo.cn/contest/947/detail?matchRoundId=947&examId=30837&openLevel=2&teamCode=1683405115827593216 Invite码：HCn2

11111111111

就会爆炸

这次欢乐赛的题目第九题为什么死活不对，能把样例再发一遍吗（要正确的）

原神

太可恶了，你们今天不上学吗，我才开始做就一堆人做完了（）

现在不会还有广深营x01,2的吧

我在Dev运行的时候结果是正确的啊，为什么一到ACGO就直接全变0了，还全WA

------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 欢乐赛#11第6题 官方，你是故意的还是不小心的！！！ 下次整个1919810 最后的最后，放个这道题的答案↓ 前往复制　　　　　　　　　←