在已经掌握线段树的基本用法后的做题整理。给自己复习用的。
用 \(mid\) 表示 \((l+r)/2\)，\(u\) 表示当前区间节点（父区间），\(ls,rs\) 分别表示当前区间的左、右子区间节点。
普通维护序列
P2023 [AHOI2009] 维护序列
修改：区间加，区间乘；询问：区间求和。
双倍经验：P3373 【模板】线段树 2。
维护两个标记，加 add 和乘 mul。在 pushdown 函数中，要先乘再加，乘的时候把 add 标记也更新。
代码。
P4513 小白逛公园
修改：单点加；询问：区间最大子段和。
考虑如何合并。一个区间 \([l,r]\) 的最大子段可能在 \([l,mid]\) 中或 \((mid,r]\) 中，也可能横跨左右两个子区间。
对于前一种情况，我们直接对子区间的答案取 \(\max\)。对于后一种情况，我们记录前缀最大值 \(lmx\) 和后缀最大值 \(rmx\)，用 \(lmx_{ls}+rmx_{rs}\) 更新 \(u\) 的答案。
对于 \(lmx\) 的更新，可能在 \([l,mid]\) 中，也可能是 \([l,j]\)，其中 \(j\in(mid,r]\)。\(rmx\) 同理。
代码。
P1471 方差
修改：区间加；询问：区间平均数，区间方差。
区间平均数 \(avg\) 即为区间和 \(sum\) 除以区间长度 \(len\)，分别维护即可。
区间方差有点难搞，考虑区间加 \(k\) 时方差 \(dat\) 如何变化。对公式变形：
于是只需要维护区间平方和 \(sum2\) 如何变化。
代码。
P6327 区间加区间sin和
修改：区间加；询问：区间 \(\sin\) 和，即 \(\sum_{i=l}^r\sin a_i\)。
因此我们还需要维护一个 \(\cos\) 和。维护方式同理。注意更新时要先临时保存原来的 \(\sin\) 和与 \(\cos\) 和。
注意区间加的懒标记需要开 long long。
代码。
**P7706 「Wdsr-2.7」文文的摄影布置
定义 \(\psi(x,y)=A_x+A_y-\min\limits_{x<i<y}\{B_i\}\)。
修改：单点修改 \(A_i\) 或 \(B_i\)；询问：\(\max\limits_{l\le x<y\le r}\{\psi(x,y)\}\)（给定 \(l,r\)）。
\(1\le n,m\le5\times10^5\)，\(1\le A_i,B_i\le10^8\)。
考虑如何合并。设 \(ans\) 为维护的答案。首先肯定是对 \(ans_{ls}\) 和 \(ans_{rs}\) 取 \(\max\)。然后考虑横跨左右子区间的情况，即 \(x\le mid,y>mid\)。
讨论 \(\max B_i\) 在左子区间内还是右子区间内。
如果在左子区间内，我们转化式子：
注意到可以分成两部分，\(\max\left\{A_x-\min\limits_{x<i\le mid}\{B_i\}\right\}\) 只与左子区间有关，\(\max A_y\) 只与右子区间有关。
于是可以分别维护，设 \(ab_u=\max\limits_{l\le x\le r}\left\{A_x-\min\limits_{x<i\le r}\{B_i\}\right\}\)，\(mxa_u=\max\limits_{l\le i\le r}A_i\)。
考虑如何从子区间更新 \(ab_u\)。首先显然用 \(\max(ab_{ls},ab_{rs})\) 更新。
然后，考虑 \(x\in[l,mid]\)，但使得 \(B_i\) 最小的 \(i\) 在 \((mid,r]\) 内的情况。为了让两项都最大，我们用 \(\max\limits_{l\le x\le mid}A_x\) 减去 \(\min\limits_{mid<i\le r}B_i\)。
于是还要维护区间最小值 \(mnb_u=\min\limits_{l\le i\le r}B_i\)。
最后答案： \(ab_u=\max(ab_{ls},ab_{rs},mxa_{ls}-mnb_{rs})\)。
如果在右子区间内，同理有：
同样维护区间 \(\max\left\{A_y-\min\limits_{mid<i<y}\{B_i\}\right\}\)。\(\max A_x\) 即为 \(mxa_{ls}\)。设 \(ba_u=\max\limits_{l\le y\le r}\left\{A_y-\min\limits_{l<i<y}\{B_i\}\right\}\)。
同理，有 \(ba_u=\max(ba_{ls},ba_{rs},mxa_{rs}-mnb_{ls})\)。
然后就可以更新 \(ans_u\) 了。
具体见 代码。
这个似乎有 \(l,r,x,y\) 的边界问题但我不知道怎么搞。
*CF438D The Child and Sequence
区间取模，单点修改，区间求和。
\(1\le n,m\le10^5\)，值域 \(10^9\)。
对于多次取模、多次除法、多次开方这样的问题，我们首先需要考虑：一个数 \(x\) 经过若干次操作，最后是否会保持为 \(0\)，不管继续怎么操作都不变。
在本题中，我们可以发现，若 \(p\le x\)，则有 \(x\bmod p\) 总小于 \(x/2\)。因此，对于每个数 \(x\)，只需要取模 \(\log x\) 次就会变为 \(0\)。
因此，我们不断地找区间内的最大值 \(mx\)，若 \(\boldsymbol{p\le mx}\)，则将 \(mx\) 对 \(p\) 取模并更新区间最大值，然后对新的区间最大值重新执行该操作。单点修改和区间求和正常即可。
由于每个数最多取模 \(\log\) 次，因此时间复杂度为 \((n+m)\log n\log v\)，其中 \(v\) 为值域大小。
代码。
*P4344 [SHOI2015] 脑洞治疗仪
一个长度为 \(n\) 的 \(0/1\) 序列，初始均为 \(1\)。
- 操作 0：将 \([l,r]\) 设为 \(0\)；
- 操作 1：把 \([l_0,r_0]\) 内所有的 \(1\) 拿出来（原位置变成 \(0\)），填在 \([l_1,r_1]\) 内所有的 \(0\) 位置上，且尽量靠前填，如果不够则不填，如果有多出来的 \(1\) 则直接扔掉；
- 查询：\([l,r]\) 内最长的连续 \(0\) 的长度。
\(1\le n,m\le2\times10^5\)。
对于操作 0，直接区间打标记即可。
对于操作 1，我们数出区间 \([l_0,r_0]\) 内 1 的个数，然后把区间全部设为 \(0\)（即操作 0），最后用这些 1 按照题目要求填进 \([l_1,r_1]\) 内。
具体地，如果左区间的空位数 \(x\) 大于等于当前要填的 \(1\) 的个数 \(y\)，那么全部填到左区间；如果左区间的空位数 \(x\) 小于当前要填的 \(1\) 的个数 \(y\)，那么把左区间全部设为 \(1\)（方法同操作 0），并且用 \(y-x\) 个 \(1\) 填入右区间，这样就变成了一个子问题。
对于询问，我们考虑如何合并，讨论最大值是左、右还是横跨左和右即可。如上面的 P4513 小白逛公园。
要维护的有：标记、区间长度、\(1\) 的个数、前缀最长连续 \(0\)、后缀最长连续 \(0\)、区间最长连续 \(0\)。
代码。
维护某个值
实际上就是把题意所需要维护的东西转化，变成可以用线段树维护的序列上的问题。
P6864 [RC-03] 记忆
有一个括号串 \(S\)，一开始 \(S\) 中只包含一对括号（即初始的 \(S\) 为
()），接下来有 \(n\) 个操作，操作分为三种：
在当前 \(S\) 的末尾加一对括号（即 \(S\) 变为
S()）；在当前 \(S\) 的最外面加一对括号（即 \(S\) 变为
(S)）；取消第 \(x\) 个操作，即去除第 \(x\) 个操作造成过的一切影响（例如，如果第 \(x\) 个操作也是取消操作，且取消了第 \(y\) 个操作，那么当前操作的实质就是恢复了第 \(y\) 个操作的作用效果）。
每次操作后，你需要输出 \(S\) 的能够括号匹配的非空子串（子串要求连续）个数。
一个括号串能够括号匹配，当且仅当其左右括号数量相等，且任意一个前缀中左括号数量不少于右括号数量。
对于全部数据：\(1\leq n\leq 2\times 10^5\)，\(op\in \{1,2,3\}\)，\(1\leq x\leq n\)，一个操作在形式上最多只会被取消一次（即所有 \(x\) 互不相同）。