A、对一个有n个数的区间进行四种操作，该区间内每个数的初始值为$ a_i $，在输入的第二行进行输入 op = 1时，输入三个数$ L、R、k $,表示对区间$ [L,R] $的数全部加上$ k $op = 2时，输入三个数$ L、R、k $,表示对区间$ [L,R] $的数全部乘上$ k $op = 3时，输入三个数$ L、R、k $,表示对区间$ [L,R] $的数全部变成$ k $op = 4时，输入两个数$ L、R $,要求输出区间方差乘上样本数的平方后的结果 线段树 lazy标记 答案最后要求输出的是$ n^2S^2 $ 那么把方差的公式展开：$$\begin{align}n^2S^2&= n \sum ^ {n} _ {i = 1}(X_i - \bar X)^2 \&=n\sum ^ {n} _ {i = 1} (X_i ^ 2 - 2 X_i \bar X + \bar X^2) \&=n\sum ^ {n} _ {i = 1} X _ i ^2 - 2n\bar X \sum ^ {n} _ {i = 1}X_i + n\sum ^ ...

相关概念 对于字符串$ S $,其前缀为$ pre(s,r) = s[0…r] $,后缀为$ suf(s,r) = s[|s| - r - 1 …..|s|] $，其中$ 0 < r < |s| $如果对于字符串有$ pre(s,r) = suf(s,r) $，则称$ pre(s,r) $是该字符串的$ border $,此时可以得到字符串的一个周期为$ |s| - r $ 相关算法及数据结构KMP算法 对于模式串和匹配串在一个字符串中匹配另外一个字符串的时候，如果一位一位的匹配，在发现某个字符不一样的时候将匹配串进行右移进行匹配，算法的效率是十分低下的，这个时候可以考虑在匹配失败的时候直接移动到匹配失败的位置那么就需要求一个$ next $数组，即字符串在该位置已匹配的字符数量‘$ next $数组是当前位置之前的字符串字串前缀与后缀的最大长度 求一个字符串的next数组，需要将其本身作为匹配串，从第2位开始匹配，这里令$ nest[0] = 0 $，然后依次匹配求出该数组 123456789101112131415char s[len];int next[len]; ...

A. Sea Battle给出四个整数w1,h1,w2,h2 计算在方格上围出w1h1与w2h2的方形所需要的方块的数量 数学显然ans = (max(w1,w2)+h1+h2+2) * 2，凹入的部分可以换到方形凸出的地方，使得两个方形被围住 12345678int w1,h1,w2,h2,ans;int main(){ cin>>w1>>h1>>w2>>h2; ans = (max(w1,w2)+h1+h2+2) * 2; cout<<ans<<endl; return 0;} B. Draw!给出n个数对，对应某个时刻的比分，输出最大的平局的次数6 对于数对(a,b)和数对(c,d)，要平局次数最大，则中间可能出现(x,x)是最好的，而x小于c,d中最小的，大于a,b中最大的，所以取平均值，如果a，b不相等，则可能出现x = min(a,b)的情况，有1的贡献，所以每次输入的时候，ans = ans + max(0,min(c,d) - max(a,b) + (a!=b)) 12 ...