Ynoi 线段树入门
flywen
·
·
算法·理论
事先声明我很菜。没写过数据结构文章啊。
这篇文章简单讲 15 道我能力范围内的 Ynoi 线段树题，简要分析题目逻辑，以掌握方法与思想。主要内容包括但不限于：离线思想、扫描线、静态转动态等。大多是比较基础的内容，个人觉得很适合初学者。
也许你认为 Ynoi 以卡常闻名，但~这何尝不是一种特色~其实 Ynoi 大部分简单题并不卡常，反而往往藏着许多巧妙的模型转换技巧，总能令我大受震撼。
限于水平，很多题目我只能阅读题解，但依旧因题目思路的精巧而感到印象深刻。同时，文中不少思路也是我反复琢磨、参考题解才得以理解，难免存在疏漏与不足之处，欢迎指正。
题目按编号排序。
因为 lxl 以前貌似不希望有人抄代码，所以仅在少数题放关键代码。
::::info[@Rabo]
感谢您对我的鼎力相助，我对您感激不尽。
::::info[@Cute_Lime。]
感谢让我拥有宝贵的青春，感谢让我能走上 oi 这条路。
无论成功与否，感谢遇到你，线段树。
我会永远铭记你我的那份精彩。
《她，我的线段树......》
::::
麻烦善良的管理员请通过一下。
---
### [P3792 由乃与大母神原型和偶像崇拜](https://www.luogu.com.cn/problem/P3792)
给定长度为 $n$ 的序列 $a_i$，$m$ 次操作：单点修改或查询区间是否可重排为值域上连续一段。
$n,m\leq5\times10^5$。
---
#### 算法一
充分发挥人类智慧，维护区间 $\max$ 与 $\min$、区间和、区间平方和、区间立方和。根据公式（见下）计算是否满足条件。
$$\sum_{i=1}^ni^2=\frac{n(n+1)(2n+1)}{6}$$
$$\sum_{i=1}^ni^3=(\sum_{i=1}^ni)^2=(\frac{n(n-1)}{2})^2$$
其实是哈希思想。时间复杂度 $O(n+m\log n)$。
#### 算法二
既然如此，我们可以再将每个数映射到一个随机数上。在满足区间和合法的前提下，如果随机数异或和也合法，则判定为连续。
应该要离线，时间复杂度 $O(n+m\log n)$。
#### 算法三
正解。
如果最大值和最小值之差等于区间长度情况下，我们只要判定区间内数是否重复即可。维护每个数的同值前驱，则合法条件为区间内同值前驱最大值小于区间左端点。
时间复杂度 $O(n+m\log n)$。
---
### [P3934 [Ynoi Easy Round 2016] 炸脖龙 I](https://www.luogu.com.cn/problem/P3934)
给定长度为 $n$ 的序列 $a_i$，$m$ 次操作：区间加或查询区间 $[l,r]$ 的：
$$a_l^{a_{l+1}^{\cdots^{a_r}}}\bmod p$$
$n,m\leq5\times10^5,p\leq2\times10^7,1\leq a_i\leq2\times10^9$。
---
有拓展欧拉定理：
>对于正整数 $p$，整数 $a$ 和非负整数 $k$ 有：
>
>$$a^k\equiv\begin{cases}a^k,&k<\varphi(p)\\a^{(k\bmod\varphi(p))+\varphi(p)},&k\geq\varphi(p)\end{cases}\pmod p$$
预处理 $\varphi(p)$，查询暴力算到模数为 $1$ 为止，递归深度为 $O(\log p)$。因为若 $p\geq3$，$\varphi(p)$ 为偶数；对于偶数 $p$，显然 $\varphi(p)\leq\frac{p}{2}$（一半以上数都为偶数，故不互质），故减半。
查询每次要捞出前面 $O(\log p)$ 个数，单点查询 $O(\log n)$，故总复杂度 $O(n+p+m\log p(\log n+\log p))$。
---
### [P5069 [Ynoi Easy Round 2015] 纵使日薄西山](https://www.luogu.com.cn/problem/P5069)
给定长度为 $n$ 的序列 $a_i$，$m$ 次操作：单点修改后查询区间需要进行多少次“操作”才能均小于等于 $0$。一次“操作”的定义为选取最大值中下标最小的 $a_i$，将 $a_{i-1},a_i,a_{i+1}$ 减 $1$。
$n,m\leq10^5$。
---
被操作后 $a_i$ 依然大于 $a_{i-1}$ 和 $a_{i+1}$，故答案其实为间隔的数之和，当然也要满足“操作”的条件。
比如 $a_i=(1,4,5,3,2,5)$ 被选为操作的 $a_i$ 的为 $a_1=1,a_3=5,a_6=5$，操作次数为 $1+5+5=11$。
考虑区间合并。显然只需要考虑区间边界的情况，于是就可以用线段树做了。
具体地，对于区间 $[l,r]$，我们需要计算 $[l,r],[l+1,r-1],[l+1,r],[l,r-1]$ 的操作次数，以及这四种情况的左右端点 $l,r$ 分别是否选择。
这种题目还挺常见的，但是这题未免有点复杂吧。代码就不放了。
时间复杂度 $O(n+m\log n)$。
---
### [P5354 [Ynoi Easy Round 2017] 由乃的 OJ](https://www.luogu.com.cn/problem/P5354)
树上单点修 [P2114 [NOI2014] 起床困难综合症](https://www.luogu.com.cn/problem/P2114)。
给定 $n$ 个点的一棵树，每个节点有运算符：按位与、按位或、按位异或，和运算权值，经过这个点就操作目前状态。$m$ 次操作，修改单点运算符和权值，或询问选定一个不超过 $z$ 的初始状态，使得从 $u$ 出发到 $v$ 后状态最大。
$n,m\leq10^5$，权值不超过 $2^{k},k\leq64$。
---
Ynoi 第一道自己做出的题，尽管调试很久才过。
拓展原题做法——按位贪心。因为按位独立，所以显然对于每一位处理以 $0$ 或 $1$ 为初始状态出发，经过路径后是 $0$ 还是 $1$。查询时高位能是 $1$ 就让它是 $1$。
注意路径经过节点是有顺序的，线段树需要维护正反两个方向。在查询时需要格外注意代码含义与合并顺序。
直接树剖时间复杂度 $O(n+qk\log^2n)$，LCT $O(n+qk\log n)$，显然过不了。
将 $k$ 位的状态压在一起合并即可。先经过其中一半区间，按照出来的值对应到另一半区间的两种初始情况，最后出来的值即为整个区间的情况。
常规树剖时间复杂度 $O(n+q(\log^2n+k))$，LCT 和单 $\log$ 树剖为 $O(n+q(\log n+k))$。
注意 $k=64$，需要使用 unsigned long long。然而我写挂了，调了很久，改成 __int128 直接过了。
```cpp lines=16,20,24-25,27-28
node pushup(node lx,node rx){ //合并
node res=seg[0];
res.l=lx.l,res.r=rx.r;
res.lft0=(lx.lft0&rx.lft1)|((~lx.lft0)&rx.lft0);
res.lft1=(lx.lft1&rx.lft1)|((~lx.lft1)&rx.lft0);
res.rgt0=(rx.rgt0&lx.rgt1)|((~rx.rgt0)&lx.rgt0);
res.rgt1=(rx.rgt1&lx.rgt1)|((~rx.rgt1)&lx.rgt0);
return res;
}
ll query_path(int u,int v,ll z){
sgt::node lx=sgt::seg[0],rx=sgt::seg[0];
lx.lft1=lx.rgt1=rx.lft1=rx.rgt1=mx;
while(top[u]!=top[v]){
if(dpt[top[u]]>dpt[top[v]]){
rx=sgt::pushup(sgt::query(1,dfn[top[u]],dfn[u]),rx);
u=fa[top[u]];
}
else{
lx=sgt::pushup(sgt::query(1,dfn[top[v]],dfn[v]),lx);
v=fa[top[v]];
}
}
if(dpt[u]<dpt[v])lx=sgt::pushup(sgt::query(1,dfn[u],dfn[v]),lx);
else rx=sgt::pushup(sgt::query(1,dfn[v],dfn[u]),rx);
//这里的合并不同,因为是先经过u->lca(dfn序为倒序)再lca->v(dfn序为顺序)
ll g0=(rx.rgt0&lx.lft1)|((~rx.rgt0)&lx.lft0);
ll g1=(rx.rgt1&lx.lft1)|((~rx.rgt1)&lx.lft0);
ll cur=0,res=0;
for(int i=k-1;i>=0;--i){ //按位贪心
if(g0&(1ull<<i))res|=(1ull<<i);
else if((g1&(1ull<<i))&&(cur|(1ull<<i))<=z)res|=(1ull<<i),cur|=(1ull<<i);
}
return res;
}
```
---
### [P5524 [Ynoi2012] NOIP2015 充满了希望](https://www.luogu.com.cn/problem/P5524)
长为 $n$ 的全 $0$ 序列，给定 $m$ 次操作：两点交换，区间覆盖，单点求值。$q$ 次问询，求出依次进行**操作区间** $[l,r]$，类型为单点求值的操作返回值之和是多少。
$n,m,q\leq10^6$。
---
没说在线就离线。维护每个位置的值，是从哪个区间覆盖操作来的，并且预处理出每个单点求值的结果是从哪个区间覆盖操作来的，用线段树可以轻松完成。
关于操作区间的题一般也要在操作序列上开数据结构。假设现在扫到单点求值操作 $r$，设其值为 $v$，来自操作编号 $x$。因为只有左端点 $l\leq x$ 时单点求值操作 $r$ 的结果才会是 $v$，否则是 $0$。故将 $a_x$ 加上 $v$，对于询问 $[l,r]$，答案为区间和 $\sum\limits_{i=l}^ra_i$。
时间复杂度 $O(m\log n+q\log m)$。
---
### [P6109 [Ynoi2009] rprmq1](https://www.luogu.com.cn/problem/P6109)
$n\times n$ 的全 $0$ 矩阵，先进行 $m$ 次矩形加，再求 $q$ 次矩形最大值。
$n,m\leq5\times10^4,q\leq5\times10^5$。
---
没说在线就离线。扫描线将行这维度转化为时间。在列上开线段树，矩阵 $[L,R]\times[l,r]$ 加操作差分为两个区间加：$L$ 时 $[l,r]$ 加上，$R+1$ 时 $[l,r]$ 减掉。
由于行变成时间维度，对于查询 $[L,R]\times[l,r]$ 我们要查询的是区间 $[l,r]$ 在历史 $[L,R]$ 的最大值。具体维护方式为维护目前最大值、懒标记、历史最大值以及距离上次 pushdown 的最大懒标记。也因此，同一时刻应当先进行区间减操作。
对于每个问询 $[L,R]\times[l,r]$ 需要先进行 $[1,L-1]$ 的修改，且不计入历史最大值，再进行 $[L,R]$ 的修改，且计入历史最大值，最后更新答案。
实现上，可以让所有操作都计入历史最大值，对于不计入历史最大值，在之后首个需要计入历史最大值的操作完成后，给根节点打上标记表示将历史最大值重置为当前最大值。标记下传时先重置左右儿子，故空间要多开一倍，或者特判也行，防止左右儿子越界。
```cpp
struct node{ ll mx,t,hmx,ht,st; }seg[N*8];
void addtag(int x,ll t,ll ht){
seg[x].ht=max(seg[x].t+ht,seg[x].ht);
seg[x].hmx=max(seg[x].mx+ht,seg[x].hmx);
seg[x].t+=t,seg[x].mx+=t;
}
void pushtag(int x){
if((!seg[x].t)&&!(seg[x].ht))return;
addtag(ls,seg[x].t,seg[x].ht);
addtag(rs,seg[x].t,seg[x].ht);
seg[x].t=seg[x].ht=0;
}
void reset(int x){
pushtag(x);
seg[x].hmx=seg[x].mx;
seg[x].st=1;
}
void pushdown(int x){
if(seg[x].st){
reset(ls);
reset(rs);
seg[x].st=0;
}
pushtag(x);
}
```
不过这个时间复杂度显然过不了一点。列这一维度已经有线段树，我们只能从行——时间这维度下手（注意区分历史最值线段树和时间维度）。容易想到线段树分治，但是直接拆成 $O(\log n)$ 个区间没有任何改善，必须拆成 $O(1)$ 个区间。
拆成 $O(1)$ 个区间可以想到猫树分治。套路地，假设区间为 $[L,R]$，$mid=\lfloor\frac{L+R}{2}\rfloor$，该节点负责处理在 $[L,R]$ 范围内的问询。对于只在左区间和右区间的询问交给子节点处理即可。对于跨越 $mid$ 的问询，预先记录在当前节点上，表示交给该节点解决。因为需要的是前缀被完成，直接做很难，所以我们考虑把猫树分治魔改一下。首先我们肯定要将问询按 $mid$ 切成两半。
假设恰好区间 $[1,L-1]$ 的操作被完成。我们先将 $[L,mid]$ 的操作全部完成，并不计入历史最大值；再对于每个问询右端点 $qr$ 从小到大排序，依次进行操作，并计入历史最大值，同时更新每个问询的答案；最后倒着撤销掉 $[mid+1,R]$ 的修改，递归入右子树 $[mid+1,R]$，容易发现右子树满足恰好 $[1,mid]$ 的操作被完成。
右子树完成后，完成左边的贡献。对于每个问询左端点 $ql$ 从大到小排序，从 $mid$ 往左依次撤销操作，现在的历史最大值就是从目前左端点到 $mid$ 的了，故我们更新每个问询的答案；最后递归入左子树 $[L,mid]$，容易发现左子树满足恰好 $[1,L-1]$ 的操作被完成。
分析一下时间复杂度。$O(m)$ 个矩阵加操作被拆成 $O(m)$ 个区间加。分治结构有 $O(\log n)$ 层，每层每个操作都要进行 $O(1)$ 次，故共 $O(m\log n)$ 次区间加。单次操作为 $O(\log n)$，故总时间复杂度为 $O(m\log^2n+q\log n)$。
```cpp
#define qj qe[x][j]
void solve(int x,int L,int R){
for(int i=L;i<=mid;++i)opt(i,1); //完成[L,mid]的操作
sort(qe[x].begin(),qe[x].end(),cmp1); //按右端点从小到大排序
for(int i=mid+1,j=0;i<=R;++i){
opt(i,1);
if(i==mid+1)sgt::reset(1); //前面已经提过,从mid+1开始算最大值
while(j<qe[x].size()&&qj.R<=i){
ans[qj.idx]=max(ans[qj.idx],sgt::qry(1,1,n,qj.l,qj.r));
++j;
}
}
for(int i=R;i>mid;--i)opt(i,0); //撤销[mid+1,R]的操作
sgt::reset(1);
if(L!=R)solve(rs,mid+1,R); //递归右子树
sort(qe[x].begin(),qe[x].end(),cmp2); //按左端点从大到小排序
for(int i=mid,j=0;i>=L;--i){
while(j<qe[x].size()&&qj.L>=i){
ans[qj.idx]=max(ans[qj.idx],sgt::qry(1,1,n,qj.l,qj.r));
++j;
}
opt(i,0);
}
if(L!=R)solve(ls,L,mid); //递归左子树
}
```
---
### [P7447 [Ynoi2007] rgxsxrs](https://www.luogu.com.cn/problem/P7447)
给定长度为 $n$ 的序列 $a_i$，$m$ 次操作：区间 $[l,r]$ 中大于 $v$ 的数减 $v$ 或求区间和、最大值、最小值。强制在线。
$n,m\leq5\times10^5,1\leq a_i,v\leq10^9$。
---
全文实现难度最高、细节最多、最为卡常的一题。此题的核心旨意就是在时间和代码常数与空间中找到平衡。
值域倍增分块！？
取一个底数 $b$，将值域分为：
$$[1,b),[b,b^2),[b^2,b^3),\cdots,[b^{\log_b V},b^{\log_b V+1})$$
块的量级显然是 $O(\log_b V)$。对于每个块，我们开一个序列维度的线段树，只维护值在这一块的 $a_i$。对于区间问询，问询每个块的线段树，最后合起来即可。
对于区间修改操作：
* 如果是叶子节点：
* 将 $a_i$ 减去 $v$；
* 如果 $a_i$ 掉出值域块的下界，就把它从当前线段树删掉，插到掉到块的线段树中。
* 否则：
* 区间 $\max\leq v$，忽略；
* 区间 $\min>v$，且减完还在该值域块内，打上区间减 $v$ 的标记；
* 否则递归。
每个元素每换块一次最多被暴力操作 $b$ 次，最多换块 $O(\log_b V)$ 次，故时间复杂度 $O((n+m)b\log_bV\log n)$。然而空间复杂度是 $O(n\log_bV)$，被卡飞。
很巧的是，上午出题的时候恰好想到对于长度较小的线段树区间，可以直接暴力算，不需要再递归下去。相当于先分块，修改查询的时候直接在块上暴力扫一遍，再在块上开线段树。
我们发现时间复杂度变为 $O((n+m)b\log_bV(\log n+B))$，这可真是太棒了，因为如果 $B$ 取得较小，时间复杂度没有很大影响。
取块长 $B=\log_bV$，共 $O(\frac{n}{\log_bV})$ 块，故单棵线段树空间为 $O(\frac{n}{\log_bV})$，而总共 $\log_bV$ 棵树，故总空间复杂度 $O(n)$。
简单分析可以发现我们要最小化 $b\log_bV$，根据换底公式：
$$b\log_bV=b\frac{\log V}{\log b}$$
求导 $\frac{b}{\log b}$ 发现 $b=e$ 时最小，所以取 $b=2,3$ 是比较合理的。
然而，经过 5 小时的调试与卡常，我悲惨地发现我太菜了，根本卡不过去。这时候大神 @[Rabo](https://www.luogu.com.cn/user/692863) 告诉我：“实测取 $b=32$ 比较快。”然后我调了一下块长就过了，原理是：“调用函数常数很大，常数抵消掉了轻微的区别。特别是封装结构体里面的递归函数调用超级慢。”膜拜 Rabo。
所以我最终取的是 $b=32,B=4$，根据代码常数调整吧。
---
### [P7880 [Ynoi2006] rldcot](https://www.luogu.com.cn/problem/P7880)
给定一棵 $n$ 个节点，以 $1$ 为根的带权树，$m$ 次问询区间 $[l,r]$ 所有点对 $lca$ 到 $1$ 距离的不同值个数。
$n\leq10^5,m\leq5\times10^5$。
---
考虑找出尽量少的三元组 $(u,v,dpt_{lca})$，使得依旧提供足够的信息（代替其他的三元组）。
对于一个 $lca$，必要的点对 $(u,v)$ 一定不在同一子树。$v$ 一定是 $lca$ 子树中剔除掉 $u$ 所在子树的点集中，$u$ 编号的前驱或后继。
引用第一篇题解：考虑树上启发式合并，维护一个 set 表示当前子树及之前子树中所有点构成的点集，每次继承重儿子，遍历轻儿子时在 set 中找前驱、后继，并将该子树合并进 set。
时间复杂度为 $O(n\log n)$，同时三元组 $(u,v,dpt_{lca})$ 的数量也被控制到 $O(n\log n)$。
我们令 $u\leq v$，考虑将 $dpt_{lca}$ 作为颜色，则转化为有两边限制的矩阵颜色计数。如图所示，点因为 $u\leq v$ 所以只在左上半，而且查询 $(l,r)$（图中灰色矩形）恰好被 $u=v$ 的斜线切开。
于是我们考虑扫描线（图中竖着的黑线），$u$ 从右往左扫，对于每个颜色维护最小（最低）的 $v$（图中实色点），同时更新到 $v$ 维度的数据结构上，查询就变成区间和了。
由于有 $O(n\log n)$ 个三元组，故时间复杂度 $O(n\log^2 n+m\log n)$。线段树常数有点大。
---
### [P7907 [Ynoi2005] rmscne](https://www.luogu.com.cn/problem/P7907)
给定长度为 $n$ 的序列 $a_i$，$m$ 次询问区间 $[l,r]$，求最小的子区间长度，使得 $[l,r]$ 中出现的数均在子区间中出现。
$n,m\leq2\times10^6$。
---
没说在线就离线。右端点 $r$ 从左往右扫，对于左端点 $l$ 处理出区间 $[l,r]$ 以 $l$ 为左端点的最小合法子区间右端点 $p_l$，即右端点至多能缩到哪个位置。
具体地，设上次 $a_r$ 出现在 $lst_{a_r}$，则对于 $l\in[lst_{a_r}+1,r]$，将 $p_l$ 设置为 $r$。区间覆盖使用线段树即可。
现在我们需要去缩左端点。当 $a_r$ 被包含时，$lst_{a_r}$ 不需要再被包含，则对于右端点 $R\geq r$ 的区间 $[lst_{a_r},R]$，可以缩短为 $[lst_{a_r}+1,R]$。于是我们可以使用并查集，每次将 $lst_{a_r}$ 连接至 $lst_{a_r}+1$，同时维护连通块中的最大下标。
对于问询 $[l,r]$，查询左端点 $l$ 所在连通块最大下标 $L$，则答案为：
$$\min_{i=l}^Lp_i-i+1$$
这是一个带偏移量的区间查询，直接处理带偏移量的目标函数可能比较麻烦，但是我们发现操作是区间覆盖，对于被覆盖区间最小值一定在最右端取到，于是就很好解决了。
时间复杂度 $O((n+m)(\log n+\alpha(n)))$。
---
### [P8512 [Ynoi Easy Round 2021] TEST_152](https://www.luogu.com.cn/problem/P8512)
长为 $n$ 的全 $0$ 序列，给定 $m$ 次区间覆盖操作。$q$ 次问询，求出依次进行**操作区间** $[l,r]$，所有数之和是多少。
$n,m,q\leq5\times10^5$。
---
没说在线就离线。右端点 $r$ 从左往右扫，依次进行每个操作，用珂朵莉树维护。
关于操作区间的题一般也要在操作序列上开数据结构。将每个操作目前的覆盖位置之和记录在一棵线段树中。则询问 $[l,r]$ 的结果为该区间的和。
时间复杂度 $O(m\log n+(m+q)\log m)$。
---
### [P9989 [Ynoi Easy Round 2023] TEST_69](https://www.luogu.com.cn/problem/P9989)
给定长度为 $n$ 的序列 $a_i$，$m$ 次操作：区间取 $a_i\leftarrow\gcd\{a_i,v\}$ 和查询区间和。
$n\leq2\times10^5,m\leq5\times10^5$。
---
类似区间开根，当区间 $\operatorname{lcm}$ 是 $v$ 的因数时忽略操作，否则暴力更新。因为 $\operatorname{lcm}$ 可能很大，所以太大时设置为值域 $+1$ 即可。
由于暴力更新会导致至少失去一个因数，而一个数的因数个数在 $O(\log V)$ 级别，故时间复杂度为 $O(n\log V+m\log n\log V))$。
有理论单 log 解法，但实际发挥一般。目前不明白。
---
### [P9990 [Ynoi Easy Round 2023] TEST_90](https://www.luogu.com.cn/problem/P9990)
给定长度为 $n$ 的序列 $a_i$，$m$ 次询问区间 $[L,R]$，求多少个子区间 $[l,r]$ 满足区间中不同数数量 $\operatorname{UV}$ 为奇数。
$n,m\leq10^6$。
---
没说在线就离线。定义 $lst_{a_i}$ 表示 $a_i$ 上一次出现位置。当扫描线扫到 $a_i$ 时，对于区间 $[lst_{a_i}+1,i]$ 的 $\operatorname{UV}$ 都会加 $1$，奇偶性翻转。设 $f^{(i)}_j$ 为区间 $[j,i]$ 的 $\operatorname{UV}$ 奇偶性，用线段树维护。
本题关键：**子区间问题转历史和**。对于问询 $[L,R]$，即对于 $i\in[L,R]$ 求出扫到 $i$ 后 $[L,i]$ 的区间和之和：
$$\sum_{i=L}^{R}\sum_{j=L}^{i}f^{(i)}_{j}$$
相当于 $[L,R]$ 和的历史和。
对于扫描到 $a_i$ 时的线段树节点 $[l,r]$，维护：
* $len$：区间长度 $r-l+1$。
* $sum$：目前区间和，即 $\sum\limits_{j=l}^rf^{(i)}_j$。
* $his$：历史上区间和的和，即 $\sum\limits_{t=1}^i\sum\limits_{j=l}^rf^{(t)}_j$。
* $rev$：区间是否被翻转的标记。
* $tag_0,tag_1$：$sum$ 关于 $his$ 的系数标记，具体地：
$$his\leftarrow sum\times tag_1+(len-sum)\times tag_0$$
在每次加入 $a_i$ 后，我们对根节点的 $tag_1$ 打上 $+1$ 的标记即可。
时间复杂度 $O((n+m)\log n)$。
```cpp
void revers(int x){
seg[x].rev^=1;
seg[x].sum=seg[x].len-seg[x].sum;
swap(seg[x].tag0,seg[x].tag1);
}
void addtag(int x,ll tag0,ll tag1){
seg[x].his+=seg[x].sum*tag1+(seg[x].len-seg[x].sum)*tag0;
seg[x].tag0+=tag0;
seg[x].tag1+=tag1;
}
```
---
### [P9991 [Ynoi Easy Round 2023] TEST_107](https://www.luogu.com.cn/problem/P9991)
给定长度为 $n$ 的序列 $a_i$，$m$ 次询问区间 $[l,r]$，求最长的子区间，使得其中不同数数量 $\operatorname{UV}$ 小于区间 $[l,r]$ 的不同数数量。
$n,m\leq2\times10^6$。
---
即要去掉一种颜色 $c$。
对于询问 $[l,r]$，分类讨论：
* 设在 $[l,r]$ 中最左侧的 $c$ 出现在 $p$ 位置，则保留 $[l,p-1]$，答案为 $p-l$。左端点 $l$ 从右到左扫描，每次启用当前位置，并删除上一次的 $lst_{a_i}$。
* 设在 $[l,r]$ 中最右侧的 $c$ 出现在 $p$ 位置，则保留 $[p+1,r]$，答案为 $r-p$。右端点 $r$ 从左到右扫描，每次启用当前位置，并删除上一次的 $lst_{a_i}$。
* 设在 $[l,r]$ 中 $c$ 相邻出现两次的位置为 $p<q$，则保留 $[p+1,q-1]$，答案为 $q-p-1$。右端点 $r$ 从左到右扫描，记录为上一次出现的位置 $lst_{a_i}$ 的贡献。
时间复杂度 $O((n+m)\log n)$。
---
### [P11620 [Ynoi Easy Round 2025] TEST_34](https://www.luogu.com.cn/problem/P11620)
给定长度为 $n$ 的序列 $a_i$，$m$ 次操作：区间异或修改或给出某数，区间所有数可以选择是否异或上去，最大化异或和。
$n,m\leq5\times10^4,a_i\leq10^9$。
---
以前思考过这种问题，但我太菜了没什么进展。学长 @[ix35](https://www.luogu.com.cn/article/zc398ndb) 的方法没有很看懂。本题还有更优解，显然我不会。
不会线性基的看我的这篇专栏——[《初中生都能看懂的线性基详解》](https://www.luogu.com.cn/article/dmoytx33)。
差分一下区间修改就变成单点修改。原序列相当于选择一个差分序列上的前缀，由于异或两次相等于没有影响，故实质上是问询 $[l,r]$ 是选取差分序列上 $[l+1,r]$ 上的若干个数与原序列的 $a_l$。于是维护差分序列上的线性基，查询时多插入一个 $a_l$ 即可。$l=r$ 要特判。
依旧是线段树维护区间线性基，时间复杂度 $O((n+m)\log n\log^2V)$。
---
### [P12013 [Ynoi April Fool's Round 2025] 牢夸](https://www.luogu.com.cn/problem/P12013)
给定长度为 $n$ 的序列 $a_i$，$m$ 次操作：区间加或问询区间 $[l,r]$ 中长度大于等于 $2$ 的子区间最大平均值。
$n,m\leq10^6$。
---
假设选了长度大于 $3$ 的子区间，将其均分为 $2$ 半，必定有一半平均值与原来相同或更优，于是选择那一半即可。故用线段树维护所有长度为 $2$ 或 $3$ 的最大子区间和即可。具体实现就很套路了，额外维护边界情况即可。
时间复杂度 $O(n+m\log n)$。
```cpp
node pushup(node lx,node rx){
node res=seg[0];
res.l=lx.l,res.r=rx.r;
res.lft1=lx.lft1;
res.rgt1=rx.rgt1;
if(lx.l==lx.r)res.lft2=lx.lft1+rx.lft1;
else res.lft2=lx.lft2;
if(rx.l==rx.r)res.rgt2=lx.rgt1+rx.rgt1;
else res.rgt2=rx.rgt2;
res.s2=max(max(lx.s2,rx.s2),lx.rgt1+rx.lft1);
res.s3=max(max(lx.s3,rx.s3),max(lx.rgt2+rx.lft1,lx.rgt1+rx.lft2));
return res;
}
```
---
:::align{center}
您是中国数据结构领域第一人。
:::