标签：le log 询问复杂度 ACM ICPC 2023 区间线段

Preface

学校针对大一新生的暑假前集训的第一个专题DS，由于要求集体写题解就顺便把写好的发上来了

由于下面都写了题意所以直接看也能有很多收获，当然非电专的学生的话就没法交题了

代码的话由于专题还没结束怕放上来然后被CV导致被爆破，所以应该在这周六专题结束后会放上来

下面都是上交学校验收的东西了，所以语言就会毕竟克制（即大大减少了不文明用语），理解一下咯

~~来点前言混混字数的说（bushi~~

感觉DS算是OI时期掌握地最牢的了，不过可能都是套路所以不用动脑，写起来也感觉还好

开局因为补CF的题，然后还有校赛的一些事情导致好多题一血没抢到，最后只能按难度倒序做

不过由于大部分东西之前都学过，就权当复习巩固了，但吉司机线段树和超哥线段树还是这次现学的，尤其是吉司机那题写加调了十几个小时，最后对着\(n=100\)的对拍数据才调出来，苦路西

OK废话环节结束进入正题的说

A 飞跃13号房

Prob

给定长度为\(n\)的序列\(\{a_i\}\)，有\(q\)次询问，每次询问给出参数\(l,r\)

求满足\(p<l,r<q,a_p=a_q\)的二元组\((p,q)\)的个数

非强制在线，\(1\le n,q,a_i\le 10^5\)

Tutorial

首先考虑将询问容斥，先统计出不考虑任何限制的二元组个数

不难发现一个询问将序列划分成了三个部分，设\(A=[1,l),B=[l,r],C=(r,n]\)

则询问\([l,r]\)的答案为全局的个数减去\(A,B,C\)内部的二元组个数，再减去\(A\)与\(B\)，\(B\)与\(C\)之间的二元组个数

而\(A,C\)内部的个数可以很容易预处理得出，又由于没有修改和强制在线，很容易想到莫队

每次移动区间的时候用桶维护\(B\)内部的二元组个数以及\(A\)与\(B\)，\(B\)与\(C\)之间的二元组个数即可

总复杂度\(O(q\sqrt n)\)

B 百战天虫：重装上阵

Prob

给一个长度为\(n\)的序列\(\{a_i\}\)，回答\(q\)次询问，每次询问给出\(d\)，要求所有长度为\(d\)的区间的最大值的最小值

区间可以不完全在\([1,n]\)内，\(1\le n,q\le 10^6\)

Tutorial

很容易想到枚举每个\(a_i\)，统计它什么时候会成为最大值对答案产生贡献

用单调栈维护出每个数的极大区间，不难发现对于所有\(d\)小于这个区间长度的询问，\(a_i\)都可以对它们造成贡献

那直接倒着维护一个后缀的答案即可，不过要注意区间不完全在\([1,n]\)的情况

总复杂度\(O(n)\)

C 蛋时间

Prob

对长度为\(n\)的序列\(\{a_i\}\)，\(q\)次询问区间最大值于区间最小值

\(1\le n,q\le 10^6\)

Tutorial

读懂题意之后就是要求区间最大最小值，设最大值为\(mx\)，最小值为\(mi\)，则只要看\(2g\times (mx-mi+h)\)和\(v^2\)的大小关系就行了

由于只有询问操作可以用小常数又好写的ST表，其核心思路就是通过倍增处理每个点\(i\)向后长度为\(2^j\)的区间的最大/最小值，然后询问就化成两个涵盖整个区间的子区间即可（因为\(\min/\max\)操作在区间有交时依然正确）

总复杂度\(O(n\log n)\)

D 买买买

Prob

有\(n\)个二元组\((s_j,p_j)\)和\(m\)个三元组\((x_i,y_i,z_i)\)，对于每个三元组求出满足\(x_is_j-y_ip_j\ge z\)的二元组的个数

\(1\le n,m\le 2\times 10^5\)，保证数据随机

Tutorial（分块+二分）

本来刚开始没拿到题目Tag的时候秒出了一个\(O(n\sqrt n\log n)\)的做法，但感觉绝对跑不过就没写了

大致思路就是先把每个二元组\((s_j,p_j)\)看作平面上的点，然后把限制的条件变个形得到\(\frac{x_i}{y_i}\cdot s_j-\frac{z_i}{y_i}\ge p_j\)

把上面的\((s_j,p_j)\)用坐标系的\(X,Y\)代入，就可以把三元组转化为一条直线\(Y=\frac{x_i}{y_i}\cdot X-\frac{z_i}{y_i}\)，然后相当于要求直线下方的点的个数

容易想到把所有点分块，块的内部用直接用\(S^2\)预处理出任意两点间的斜率

然后把询问离线，按照斜率从小到大考虑，每次询问的时候就把\(\frac{n}{S}\)个块都扫一遍把答案加起来即可

在每个块内再维护下\(y\)坐标的大小顺序，因为当询问的\(k\)增大\(\delta k\)时，每个点的\(\delta y=-kx\)

而又因为我们已经预处理出了每个块内任意两点间的斜率了，所以每次增大\(k\)的时候看下跨越了几个预处理过的斜率值，把相应的点的\(y\)的交换一下

这样有一个好处就是可以把直线变成水平的，直接对\(y\)二分即可

如果我没记错的话可以调块的大小把\(\log\)吸收到根号里面，但这样预处理复杂度有点爆炸，总之大概就是这个复杂度级别的了

代码有点懒了就没写了，口胡一下

Tutorial（KD-Tree）

知道用KD-Tree后就很naive了，我们还是和之前一样转化题意，变成求直线下方的点的个数

考虑对于KD-Tree的每个节点，维护出包含了它们的最小的矩形，显然如果这个矩形全部在直线的某一侧时就可以剪枝统计答案了

复杂度分析类似于找平面最近距离点对的那种方法，应该是随机情况下\(O(n\sqrt n)\)的，事实上也跑的非常快

不过话说这题也没有强制在线，直接给所有点random_shuffle一下好像也能避免被构造数据卡

E 导航系统

Prob

给出一个由两个简单环构成的图，其中两个环仅有一条简单路径连接

有多次操作，包含修改一条边的可使用状态，以及询问两点间的最短路径

点数和询问次数\(\le 10^6\)

Tutorial

由于写之前在草稿纸上细心画图讨论了所有情况，所以写起来很快就一发入魂了

首先很显然可以直接用树状数组维护区间和，然后把一条边断开就是直接加上一个极小值，查询出来如果是个负值就说明不连通

讨论大体就先分三种情况，两个点都在\([1,n]\)中，都在\([n+1,n+m]\)中，以及跨越的情况

在环的内部的情况就是讨论下两种方向，但是要注意可以从另外一个环上走而不是一定要走那条公共弦

跨越的情况就是讨论下从哪个点（\(1\)还是\(S\)）走到另一个环即可

可以写函数表示某个点到\(1\)和\(S\)的最短距离，可以极大地优化代码复杂度

F 转生为lsr只能度过不如黎酱的人生

Prob

给一个长度为\(n\)的序列\(\{a_i\}\)，对其所有子区间\([l,r]\)求\(f(l,r)=\gcd_{i=l}^r a_i\)，求最后\(f(l,r)\)的所有取值可能以及相应的个数

Tutorial

经典的\(\gcd\)性质题，考虑确定右端点后暴力的向前枚举左端点，显然可能的不同的值是\(O(\log a_i)\)级别的（因为每次减小至少除以\(2\)）

因此在做完每个数后其实以它结尾的答案个数就是\(\log\)级别的，我们可以直接用map维护下以\(i\)结尾的所有区间的每种情形的二元组

最后输出的时候利用map的有序性可以省去排序的过程，代码就比较好写，不过复杂度是\(O(n\log^2 a_i)\)的

可以用链表优化向前跳的过程，最后统计答案的时候再排序，可以做到一个\(\log\)，不过代码就没写了

G Redcrown的数学题

Prob

给一个长度为\(n\)的序列\(\{a_i\}\)，强制在线给出\(q\)次询问\([l,r]\)

记\(p_i\)表示\(a_i\)在\([l,r]\)中出现的次数，要求选择一个\(i\in[l,r]\)使得\(a_i\times (n^{p_i}+\frac{1}{n})\)的值最大

\(1\le n,q\le 10^5\)

Tutorial

首先挖掘下式子的性质，不难发现当一个数出现次数对整个式子的值影响最大

考虑找出区间的最大的众数\(a_i\)，设其出现次数为\(p\)，那么所有出现次数不为\(p\)的数的出现次数最多为\(p-1\)

由于\(n-1<\frac{n^p+\frac{1}{n}}{n^{p-1}+\frac{1}{n}}<n\)，因此此时有且仅有一种特殊情况答案不为区间最大众数

即最大众数为\(1\)，其出现次数为\(p\)；而区间内其它数都是\(n\)，且其出现次数为\(p-1\)

但是还有一种Corner Case，当区间长度为\(1\)且内部仅有\(1\)时要特判答案输出\(1\)，否则会输出\(n\)（像我这种判的不好的就会挂）

所以说回来我们只要求区间最大众数了，这是个经典问题，可以用分块解决

我们可以先预处理出\(mode_{i,j}\)表示从块\(i\)到块\(j\)中所有数的最大众数，这部分复杂度是\(O(\frac{n^2}{S})\)的

然后考虑对于散块的每个数，我们暴力枚举它们，分别看它们是否能更新答案

可以把每个数出现的所有下标扔进vector里，然后查询一个数在某个区间内出现的次数时只要在对应的vector里二分即可，这部分复杂度是\(O(S\log n)\)的

取\(S=\sqrt{\frac{n}{\log n}}\)时，总复杂度\(O(n\sqrt {n\log n})\)

H The Crazy Ones

Prob

给一个长度为\(n\)的序列\(\{a_i\}\)，我们称它的一个子序列是crazy的，当且仅当这个子序列内部存在一个数只出现了一次

判断序列所有的子序列是否都是crazy的

\(1\le n\le 2\times 10^5\)

Tutorial（假算法）

这题头一天晚上看到就一眼出了一个挺有趣的假算法，WA了好多发之后仍然不知道错在哪里

先讲下这个假算法，考虑一个区间内所有数出现次数都大于等于\(2\)，手玩了一些小情况之后感觉可能可以转化成一个区间内所有数出现次数都是偶数

然后就很好办了，考虑用必要条件转化为区间内所有数的异或和为\(0\)，当然这样很容易被诸如1 2 3这样的数据卡掉

利用某道CF中解决这个问题的思路，把每个数随机映射到一个unsigned long long上去，此时被卡的可能性就极小了

然后快速写完喜提WA，不信邪写了对拍拍了一晚上也拍不出来（主要随机数据真没啥强度），主要还是证不出前面转化的正确性，但也找不出反例

后面还是不死心，把做法拿去问了maple276聚聚，然后他半夜终于构造出一种情况给我卡了，这下死而瞑目了

好吧我承认我的猜结论水平就是次，~~下次还猜~~

Tutorial

其实直接维护的正解也不难，我们先考虑所有左端点等于\(1\)的区间

不妨设每个数第一次出现时为\(1\)，第二次出现为\(-1\)，后面每一次出现都赋值为\(0\)

对此时序列求出前缀和，不难发现当某个位置的值为\(0\)时则说明存在一个区间，其中所有数出现次数大于等于\(2\)

由于所有位置的前缀和显然都大于等于\(0\)，以上操作就等价于找区间最小值

然后考虑当左端点向右移动时，只会影响被移动的那个数的贡献，我们可以预处理出每个位置向后第一个和它有相同的数的位置，这样就可以快速维护要修改的区间了

用线段树维护对前缀和数组的修改，总复杂度\(O(n\log n)\)

I 末日时在做什么？有没有空？可以来数兔子吗？

Prob

给定一个\(n\)个点的树，树上每个点\(i\)有两个权值\(a_i,b_i\)，其中\(b_i=Fib(a_i)\)（\(Fib(x)\)表示斐波那契数列的第\(x\)项，\(Fib(1)=Fib(2)=1\)）

需要维护\(m\)次操作，操作包含对某个子树/路径上所有点的\(a_i\)执行区间加，以及询问某个子树/路径上所有点的\(b_i\)的和

\(1\le n,m\le 10^5\)

Tutorial

先考虑在序列上如何维护这些操作

用矩阵\(D\)来表示斐波那契数列的转移矩阵，并存储每个点的状态矩阵

容易发现一次修改相当于将区间整体乘上\(D^x\)

由线性变换的性质，我们可以直接用某个区间的所有状态矩阵和与转移矩阵相乘来快速得到整个区间修改后的值

那么用一个能维护区间和与区间乘法的线段树即可维护以上信息，在树上做就直接套一个树剖的板子就好了

总复杂度\(O(n\log^2 n)\)

J 回村の诱惑

Prob

给一个长度为\(n\)的序列，初始时每个数都为\(0\)，有\(m\)次修改操作和\(q\)次询问操作

每次修改操作形如\(l_i,r_i,t1_i,t2_2\)，表示其效果为将区间\([l_i,r_i]\)赋值为\(1\)，其有效时间为\([t1_i,t1_i+t2_i)\)

每次询问则要求出某个时刻，某个区间内值为\(0\)的数的个数

\(1\le n,m,q\le 2\times 10^5\)

Tutorial

很显然可以把所有修改和询问都离线，修改按照起始时间和结束时间拆成两个，然后按时间顺序处理每个操作

考虑在询问时区间赋值和区间加法对答案没有影响，我们可以用容易维护和可撤销的区间加法来表示每个操作的影响

现在的问题就是怎么维护出区间内\(0\)的个数，这里的思路就和H题很像了

由于我们操作时每个位置的值一定是大于等于\(0\)的，因此问题就等价于求区间最小值以及其出现次数

直接用线段树维护一下就行了，总复杂度\(O(n\log n)\)

K 卡—美—哈—梅—哈——！！！

Prob

对一个\(n\times n\)的矩阵，每个位置有初值\(a_{i,j}\)，给出\(m\)次操作

操作包含单点修改，将一整行/列所有数置\(0\)，询问某个子矩形内所有数的和

\(1\le n\le 1000,1\le m\le 2\times 10^5\)

Tutorial

二维单点修改和区间求和，一般就是二维线段树或者CDQ分治，不过这里由于\(n\)的范围很小，直接建树会比较好写

二维线段树一般两种写法，一种是对每一维开线段树的树套树写法，令一种是没啥用复杂度还经常是假的四分树写法，由于我平时写数据结构一般会小小封装一下所以写树套树会很方便

但由于二维线段树不能打懒标记，遇到区间赋值操作就GG了，看起来好像有点走投无路了

但后面转念一想这个清空操作是很丁真的，由于我们只有单点修改，而要总的有效的清空的位置的数量是和\(m\)同阶的

换句话说我们每次清空行/列操作时，只要暴力遍历所有不为\(0\)的元素进行单点修改即可

刚开始本来想写个类似于DLX中的二维链表来处理清空操作的，但后面转念一想这部分对总复杂度没有直接影响就直接写个set维护下非零的坐标就完事了

总复杂度\(O(m\log^2 n)\)

L 养鱼艺术家

Prob

给一个长度为\(n\)的序列\(\{a_i\}\)，有\(m\)次修改操作和\(q\)次询问

每次修改操作形如\(c_i,l_i,r_i,d_i,v_i\)，表示给\([l_i,r_i]\)加上初值为\(v_i\)，公差为\(d_i\)的等差数列，这次修改所有数的颜色都是\(c_i\)

每次询问一个区间内某个点上出现次数最多的数以及其颜色

\(1\le n,m\le 10^5,1\le q\le 2\times 10^5\)

Tutorial

刚开始没理解题意以为是把区间内所有同色的累计在一起，后面看了样例才知道是对于单点而言的

首先考虑若每次操作的颜色都各不相同，那么一次修改相当于在坐标系上加入一条线段（公差就是其斜率）

那么我们可以对每个点，在处理出它的答案后，最后用ST表来回答最后的询问即可

因此现在的问题就变成求\(x=i\)时，其最上方的一条线段，这是个李超线段树的模板题

李超线段树的大致思路就是用标记永久化的思想维护每个\(x\)区间上的最优势线段，这条线段满足在\(x=mid\)时其处于最上方

考虑新加入一条线段时的影响，考虑求出它和\(x=l,x=r\)的值并和原来的最优势线段比较，如果两个值都大于原来的就直接替换，都小于原来的就直接返回

否则则说明这两条线段在区间内存在交点，画画图分四种情况讨论下下传答案即可，代码其实是非常好写的

询问时由于利用了标记永久化的思想，直接对于每个遇到的区间的最优势线段尝试更新答案即可

但是对于本题还存在最后一个问题，当不同的修改操作拥有相同的颜色时就要把它们的影响合并起来而不能独立开来看

由于等差数列满足可加性，直接把初值和公差相加即可，刚开始想着是排序之后讨论下相邻有交的区间，但发现异常麻烦

后面发现可以直接用线段树把一个区间拆成至多\(\log n\)个，对于同种颜色的所有线段一起扔到线段树上处理，最后一起遍历一遍即可（就是类似于线段树分治的写法）

最后要插入的线段是\(O(n\log n)\)级别的，因此总复杂度\(O(n\log^2 n)\)

M 安全通行

Prob

给出一个\(n\)个点的图，有\(m\)条双向边，每条边有一个存续时间区间\([l_i,r_i]\)

对于\(k\)个时刻，每个时刻询问当前仅考虑存续时间区间包含了当前时刻的所有边，某两个点之间是否连通

\(1\le n,m,k\le 2\times 10^5\)

Tutorial

经典题了，可以算是线段树分治和可撤销并查集的板子题了

考虑把每条边在线段树上拆成\(\log n\)个区间，最后递归地把整棵树遍历一遍

在访问到一个点是把该点处的所有边的影响加入，在退出时撤销所有此次加入的边，最后当走到叶子节点时统计答案即可

由于DFS的性质，我们只要实现按栈顺序撤销并查集操作即可，直接把每次合并时被修改的信息扔进栈里，撤销的时候弹出恢复更新即可

要注意此时并查集就不能路径压缩了，只能老老实实按秩合并，总复杂度就是\(O(n\log^2 n)\)的

N 九把七鸡五连鸡

Prob

给定一个\(n\)个点的树和一个正整数集合\(S\)，初始时\(S=\{x|1\le x\le n,x\in N\}\)

树上每个点有一个\([1,n]\)范围的权值，有\(q\)次操作或询问

改变一个数\(x\)在集合中的状态，即若\(x\notin S\)就把\(x\)添加入\(S\)中，否则把\(x\)从\(S\)中去除
给定\(u,v\)，设树上\(u,v\)的路径上所有点的权值构成的集合\(S'\)，求\(|S\cup S'|\)

\(1\le n\le 10^5\)，并保证修改操作的次数不超过\(1000\)

Tutorial

首先考虑没有修改操作怎么做

显然就是个树上数颜色的问题，直接上树上莫队即可

树上莫队，即在树的欧拉序（注意与DFS序的区别）上处理询问，但是要注意询问点之间的\(LCA\)是否要统计入答案

比如对于如下的树：

其欧拉序为：

那么我们手玩一下路径的两个端点\(u,v\)间的关系就有：

\(u,v\)的LCA为其中之一，则\(u,v\)间的路径就是\(In[u],In[v]\)区间或\(Out[u],Out[v]\)区间
\(u,v\)的\(LCA\)为\(w\)，则\(u,v\)间的路径就是\(In[u],Out[v]\)区间或\(In[v],Out[u]\)区间，但还需额外加上\(w\)

考虑加入修改操作，不难发现由于其次数小于等于\(1000\)所以我们完全可以暴力处理

对于每个询问，维护出所有在这个时刻\(S\)集合中被刨除了哪些数，在莫队统计完后暴力统计一遍即可

总复杂度\(O(q\times (\sqrt n+1000))\)

O Princess Principal

Prob

给定一个\(n\)个点的树，每个点有黑白两种颜色，同时还有权值\(a_i\)

定义点\(x\)的同色连通块为从\(x\)出发只经过与点\(x\)颜色相同的点所能到达的点集

现在要维护以下\(m\)次操作

修改某个点\(x\)的颜色（即黑变白，白变黑）
修改某个点\(x\)的权值\(a_x\)
询问\(x\)所在的同色连通块内最小的权值

\(1\le n,m\le 5\times 10^5\)

Tutorial（树剖）

考虑动态地维护出每个点\(x\)到根节点的路径上每种颜色的个数\(cnt_{x,0/1}\)

对于一个点\(x\)与它的祖先\(y\)，判断它们是否连通只要看\(cnt_{x,c_x\oplus 1}\)与\(cnt_{y,c_x\oplus 1}\)是否相等即可

对于每一个连通块，令其中深度最小的点为这个连通块的管辖点

通过树剖+set，在每个重链的top处，存入每个链上的节点于对应的颜色和深度

然后考虑暴力地沿着重链向上跳，结合上面的性质，可以轻易地求出每个点\(x\)的管辖点\(y\)

因此在询问\(x\)的同色连通块信息时，就相当统计在\(y\)的子树内所有满足\(cnt_{x,c_x\oplus 1}=cnt_{z,c_x\oplus 1}\)的点\(z\)的信息

可以用线段树来实现，对于线段树的每个节点，记录这个区间的\(LCA\)到根路径上每种颜色节点的数量

同时再顺带维护下这个区间内和\(LCA\)在同一个连通块内的点权的最大值

询问时时刻注意判断是否满足上式的限制，同时在pushup的时候也有细节要注意

总复杂度\(O(m\log^2 n)\)

然后对于这种做法我们显然可以扩展到对于某个点的同色连通块的权值集体修改

只需要对两种颜色分别开修改标记，然后在pushdown的时候判断下下传条件即可，不过细节挺繁琐的

Tutorial（LCT）

其实这类题我OI时期遇到我都是用\(LCT\)写的

一个trivial的想法就是对于两种颜色分别开\(LCT\)，然后每次修改颜色的时候断开原来颜色的树中的边，然后在另一种颜色的树中连边即可

但是遇到菊花图之类的就寄了

考虑用经典套路，把点权转化成边权

把每个点的颜色赋值给它与父亲相连的边（\(1\)号点就新建一个虚点当它的父亲即可）

此时同色的连通块就转化成了减去顶部节点后的边的连通块

那么在修改颜色操作时，只要断开在原来的\(LCT\)中该点与父亲的边，然后在另一棵\(LCT\)中连上这条边即可

复杂度\(O(m\log n)\)，但常数较大，可能还跑不过树剖的做法

小小地口胡一下，代码就没写了

P Stack Merge

Prob

给\(n\)个栈，初始时每个栈\(i\)内仅有一个元素\(i\)，进行\(m\)次操作

（略去转移至临时栈等操作）每次操作形如把某个栈接在另一个栈后面，以及询问某个元素在其所属的栈中的排名

\(1\le n\le 10^6,1\le m\le 2\times 10^6\)

Tutorial

带权并查集的裸题，考虑我们在维护集合从属关系的时候顺带维护两个值

\(sz_i\)表示\(i\)所属的连通块（即所属的栈）中的元素个数，\(dep_i\)表示\(i\)到栈顶的距离

在合并的时候顺带更新这两个值即可，不过要注意在路径压缩中要先记录下原来的父亲，从该处传来正确的\(dep\)的值

总复杂度\(O(n\cdot\alpha(n))\)

Q Keep the least!!!

Prob

给定一个\(n\)个点的树，每个点有点权\(a_i\)，同时给出一个点集\(S\)

进行\(q\)次操作，每次操作即向\(S\)中加入或删除一个元素

求每次操作之后，\(S\)中的点形成的极小连通子树的点权和

\(1\le n,q\le 10^5\)

Tutorial

很容易发现这棵极小连通子树就是所有关键点形成的虚树

联系虚树的建树规则，很容易想到把\(S\)中的所有点按照DFS序排序，则答案就由相邻的点之间的路径构成

先假设我们现在要求的极小连通子树的权值不是点权而是边权

设\(dist(u,v)\)表示树上两点\(u,v\)的距离，则此时\(S=\{a_1,a_2,\cdots,a_n\}\)的答案为

\[\frac{\sum_{i=1}^{n-1} dist(a_i,a_{i+1})+dist(a_n,a_1)}{2} \]

显然在插入/删除一个点时只会对它和它的前驱/后继之前的贡献产生影响

用set维护下这个过程即可

如果是询问点权和的话，直接这么做会让中间的某些点贡献计算重复

还是考虑把点权赋给它与父亲相连的那条边，此时我们发现原来\((u,v)\)的点权和就是现在\((u,v)\)的边权和再加上\(LCA(u,v)\)的点权

因此扩展到一个集合的点时贡献就是边权和再加上所有点的\(LCA\)的权值

而我们知道，一堆点的\(LCA\)就是其中DFS序最小和最大点之间的\(LCA\)

总复杂度\(O(q\log n)\)

R How Many Fruits

Prob

给一个长度为\(n\)的序列\(\{a_i\}\)，有\(m\)次操作，操作包含区间加法和区间取\(\lfloor \log\rfloor\)，询问区间和

\(1\le n,m\le 3\times 10^5\)

Tutorial

经典的势能分析线段树的题目，不难发现由于一个数被做极少次操作后就会变成\(0\)

因此我们对于一个区间，若其中所有的数都是同一个数就直接转化成区间减法，否则就暴力递归

可以证明这样每个点被暴力更新到的次数是\(O(4n)\)的，因此复杂度正确，为\(O(n\log n)\)

和这个类似的还有区间开方、区间整除某数、区间对某数求\(\gcd\)等，复杂度分析和处理方法都一样

S 肯德吉全家桶

Prob

给一个长度为\(n\)的序列\(\{a_i\}\)，有\(m\)次操作，每次操作形如：

区间加上某个数
区间对某个数取\(\min\)，即对于\(\forall i\in [l,r],a_i=\min(a_i,x)\)
询问区间\(a_i\)之和
令\(f(i)\)表示\(a_i\)被修改的次数，求区间\(f(i)\)之和
令\(b_i\)表示到当前为止\(a_i\)所有出现过的值中的最大值，求区间\(b_i\)的最大值
令\(c_i\)表示到当前为止\(a_i\)所有出现过的值中的最小值，求区间\(c_i\)的最小值

\(1\le n,m\le 2\times 10^5\)

Tutorial

正如题目提示的那样，这是一道吉司机线段树的模板题

考虑没有区间取\(\min\)时怎么做，此时有个相对新颖的区间历史最值询问

考虑在用线段树维护区间加法时，除了要下传的标记的值，我们再额外维护下这个标记的最大/最小值

不过这样的话在下传中不同标记间的顺序就很重要了，写的时候需要注意下

然后考虑加入区间取\(\min\)操作后怎么维护修改，根据吉老师2016年的论文，可以把它转化成区间加来处理

具体的，对于线段树上的每个区间，我们维护其最大值\(mxa\)、最大值的个数\(cnt\)、严格次大值\(smx\)

考虑当前修改的值为\(mv\)，分情况讨论：

若\(mv\ge mx\)，则本次修改对该区间无任何影响，直接返回
若\(mx\le smx\)，暴力递归子树，更新信息
若\(smx<mx<mx\)，则把本次取\(\min\)操作看作仅针对区间最大值的加法操作，更新信息后打上标记并返回

吉老师在论文中证明了其均摊复杂度是\(O(\log n)\)的，这个具体看论文吧，我也没有太懂的说

然后考虑有了这个之后求\(f(i)\)操作自然是水到渠成，同时只要把我们之前所有的标记都开双份分别表示仅针对区间最大值的操作的标记和仅针对区间非最大值的标记即可

当然说起来容易写起来是极其痛苦的，还要注意一些区间是没有严格最大值的，此时的处理就有很多细节

（以下仅展示我个人写法的一个节点的信息量，这题整整写+调花了10h+，算是这场组题里最卡我的一道了）

struct segment
{
    int sum,len,mxa,cnt,smx,mxb,f,mia,mib;
    int add1,add2,add3,add4,add5,add6,add7,add8;
}s[N<<2];

总复杂度\(O(n\log n)\)（这个常数就毁天灭地了，其实可以开一个变量表示这个点是否要下传信息，可以大大优化效率的说）

T 冉冉的树

Prob

给定一个\(n\)个点的树，每个点有编号\(i\)和权值\(a_i\)，有\(m\)次询问

每次询问形如\(l_i,r_i,x_i\)，表示询问只保留编号在\([l_i,r_i]\)的点时，\(x_i\)所在的连通块内有多少个点的权值小于\(a_{x_i}\)

\(1\le n,m\le 10^5\)

Tutorial

本来听周六讲题之前大致YY了一个做法，不过没有想到可以把询问往上挂来避免向上走，所以感觉很难写

后面听了包大爷的讲课后豁然开朗，上手一写果然很好写，狠狠地好评（写完这题后花费8天终于堪堪做完DS专题了）

树上静态可离线问题，不是Dsu on Tree就是点分治，这里显然只能是用点分治了

求出点分树后我们考虑此时某个点可以想下走，也可以向子树内走，向上走显然很不利于我们统计答案

因此我们考虑把每个点的询问挂到和它最近且可达的点分治中心上，这个在每个点分治重心暴力遍历子树内所有点的时候可以轻松维护出来

同时对于每个分治中心，我们可以暴力求出其到子树内每个点\(u\)的路径的信息\((L,R,y)\)，表示到\(y\)的路径上点编号的最小值\(L\)和最大值

\(R\)

那么对于同样挂在这个点上的询问\((l,r,x)\)，我们发现\((L,R,y)\)能对\((l,r,x)\)造成贡献，当且仅当\(l\le L\and R\le r\and a_y\le a_x\)

不难发现这就是个经典的三维偏序问题，直接用CDQ分治处理即可（后面有个CDQ模板这里就不展开讲了）

总复杂度\(O(n\log^2 n)\)

U Stack Rearrange

Prob

给定一个长度为\(n\)的序列，其中的每个元素都有两个属性——序号与权值，序号不随元素位置的改变而改变

现在有以下\(m\)种操作，形如：

把序号为\(x\)的元素放在序号为\(y\)的元素的前面
将序号为\(x\)的元素对应的权值改成\(y\)
查询序号为\(x\)的元素在序列的哪个位置
查询从前往后第\(x\)个元素的编号
查询从前往后第\(x\)到第\(y\)个元素的权值和

\(1\le n,m\le 2\times 10^5\)

Tutorial

首先一眼平衡树维护序列题，但刚开始猪脑过载，先是没想清怎么实现把\(x\)提到\(y\)前面WA了好几发

后面听了讲课才发现可以转化成两次区间reverse操作，但写完还是挂

然后又是大力调试许久后发现是犯了个经典错误：fhq_treap不能同时按照权值和排名分裂！

因此这题我们要直接用这个点的下标表示编号，然后维护按中序遍历时保证是按序列顺序得出的

对于操作\(1\)，先找出要修改的两个数的排名\(u,v\)，然后分情况讨论：

若\(u<v\)，则移动操作等价于翻转\([u,v-1]\)和\([u,v-2]\)
若\(u>v\)，则移动操作等价于翻转\([v,u-1]\)和\([v,u]\)

但此时找序号为\(x\)的元素的排名时就要有所修改了，由于已知这个点的编号，可以直接暴力向上跳到根，如果向上的链上的某个点是其父节点的右儿子，就可以累计它的父节点的左子树和其父节点到排名中了

当然由于我们有区间翻转操作需要打标记，所以要像splay一样先把要查询的链上所有的点扔到栈里，pushdown完所有标记后再重新向上跳

同理修改操作也非常简单了，直接暴力向上跳修改区间和的信息即可

总复杂度\(O(n\log n)\)

V 星星与薰衣草

Prob

给定\(n\)个点的图，有\(m\)次操作，每次操作为在两点间连一条边，或者询问两点是否连通

\(1\le n\le 2\times 10^6,1\le m\le 4\times 10^6\)

Tutorial

这就直接来并查集裸题了，虽然数据范围很大但好像只路径压缩也能过

严格来说要同时利用路径压缩和按秩合并才能使并查集复杂度降到线性，大致是\(\alpha(n)=4\)？

W 葬花：暗黑桃花源

Prob

给定\(n\)个三元组\((a_i,b_i,c_i)\)，每维范围都在\([1,k]\)中，定义\(g(i)\)表示所有满足\(a_j\le a_i\and b_j\le b_i\and c_j\le c_i\)的\(j\)的个数（不包含自身）

对\(t=0,1,2,\dots,n-1\)，分别求出使得\(g(i)=t\)的\(i\)的数量

Tutorial

三维偏序模板题，做法很多（树套树、整体二分等），这里写了一般最常用的CDQ分治

考虑先给第一维排序，然后考虑对于某个分治区间\([l,r]\)，先把它的两个子区间\([l,mid],[mid+1,r]\)按照第二维排序

此时用two pointers，我们从左到右枚举右边区间的每个元素，然后把左边区间内所有第二维小于等于它的元素的第三维的信息用数据结构维护下，再右边区间个元素d1第三维进行查询即可

这里要求小于等于某个数的个数，显然直接用树状数组就好了

不过要注意一定要去重，不然同样值的元素被分在不同的区间是贡献计算就会出问题，这也是个老生常谈的问题了

总复杂度\(O(n\log^2 n)\)

X Colorful Scarf

Prob

给一个长度为\(n\)的序列\(\{a_i\}\)，其中每个位置有一个颜色\(c_i\)

有\(m\)次操作，每次操作为把某个颜色全部涂成另一种颜色，或者询问当前序列中有多少个颜色段

\(1\le n,m\le 10^6\)

Tutorial

由于同样的颜色段只会随着操作的进行不断减少，因此可以考虑一个看似暴力的做法

用set维护每种颜色覆盖的区间，考虑在修改操作时直接暴力合并两个集合，合并的过程中如果有区间连成连续的就直接把它们合起来

考虑用启发式合并，每个数对应的区间最多会被操作\(\log n\)次，因此总复杂度\(O(n\log n)\)（这里不知道怎么算set对复杂度的影响，感觉应该是不影响的，当然用unordered_map肯定是可以的）

注意要特判两种颜色相同的情况，没注意给WA惨了

Y 新型背包

Prob

有\(n\)个物品，每个物品有单位体积价格\(p_i\)，总体积\(v_i\)，奇异值\(s_i\)

给出\(m\)次询问\(V_i,C_i\)表示询问当装载了至少\(C_i\)个元素，价值总和不超过\(V_i\)时，所装入的物品中的最小奇异值的最大值是多少

\(1\le n,m,s_i,p_i,v_i\le 10^5\)

Tutorial

最小值最大一眼二分答案，考虑怎么检验一个解\(mid\)是否合法

一个暴力的想法就是把所有奇异值大于等于\(mid\)的所有元素按\(p_i\)从小到大排序，然后贪心地先取\(p_i\)小的即可

但是多组询问肯定不能直接暴力搞，结合上面贪心的过程我们可以想到以\(p_i\)为下标开一棵权值线段树，顺带维护下每个区间的数量合以及总代价和

不难发现此时检验合法的过程只要在线段树上二分即可，能向左子树走就向左边走

那么每次只用奇异值大于等于\(mid\)的限制也很简单了，按照奇异值从大到小排序后用主席树来维护上述的权值线段树即可

一般这种涉及到两位的两次贪心/二分的操作都可以考虑定下一维之后对另一维开主席树，是很常用的技巧

总复杂度\(O(n\log^2 n)\)

Z Segment Balance

Prob

给长度为\(n\)的序列\(\{a_i\}\)，维护\(m\)次操作，形如：

查询数\(k\)在\([l,r]\)中的排名
查询\([l,r]\)中排名为\(k\)的数的权值
修改某个位置的值
查询数\(k\)在\([l,r]\)中的前驱
查询数\(k\)在\([l,r]\)中的后继

\(1\le n,m\le 5\times 10^4\)

Tutorial

这题一眼树套树模板，然后当我找到Luogu上以前写的这题时发现我原来时用分块写的233

（不过话说这题\(O(n\sqrt n)\)的分块做法就是要比\(O(n\log^2 n)\)的跑的快，而且还很优美的说）

所以秉承着练习一下板子的目的还是重写了一个树状数组套权值线段树的又好写复杂度也优秀的做法，那种要二分的线段树套平衡树就不太行的说

考虑借鉴用主席树求区间第\(k\)大的思路，维护每种权值出现的次数，然后询问就是差分对应的权值线段树，在上面二分即可

但由于有修改操作，我们肯定不能暴力修改每个受影响的树，那么再套一个树状数组来维护修改就行了，这样每次询问先把所有要处理的树的信息求出来，然后一起放在权值线段树上跑即可，代码非常好写

当然这种做法的缺点就是由于要离散化，所以是个离线做法，而且空间复杂度也是\(O(n\log^2 n)\)的，可能稍有不慎就会MLE

不过时间复杂度是标准的\(O(n\log^2 n)\)，跑的还是很快的说

Postscript

终于写完咯，撒花撒花，~~26个题写完加题解真是让人神清气爽~~

一下没注意也陆陆续续写了1W多字了，看来我的废话还是挺多的，\kel

下次专题可能由于要准备期中考不会像这次那么肝了，不过肯定还是会尽力而为的说

标签：le,log,询问,复杂度,ACM,ICPC,2023,区间,线段
From： https://www.cnblogs.com/cjjsb/p/17353944.html

2023年电子科技大学ACM-ICPC暑假前集训-数据结构

Preface

A 飞跃13号房

Prob

Tutorial

B 百战天虫：重装上阵

Prob

Tutorial

C 蛋时间

Prob

Tutorial

D 买买买

Prob

Tutorial（分块+二分）

Tutorial（KD-Tree）

E 导航系统

Prob

Tutorial

F 转生为lsr只能度过不如黎酱的人生

Prob

Tutorial

G Redcrown的数学题

Prob

Tutorial

H The Crazy Ones

Prob

Tutorial（假算法）

Tutorial

I 末日时在做什么？有没有空？可以来数兔子吗？

Prob

Tutorial

J 回村の诱惑

Prob

Tutorial

K 卡—美—哈—梅—哈——！！！

Prob

Tutorial

L 养鱼艺术家

Prob

Tutorial

M 安全通行

Prob

Tutorial

N 九把七鸡五连鸡

Prob

Tutorial

O Princess Principal

Prob

Tutorial（树剖）

Tutorial（LCT）

P Stack Merge

Prob

Tutorial

Q Keep the least!!!

Prob

Tutorial

R How Many Fruits

Prob

Tutorial

S 肯德吉全家桶

Prob

Tutorial

T 冉冉的树

Prob

Tutorial

U Stack Rearrange

Prob

Tutorial

V 星星与薰衣草

Prob

Tutorial

W 葬花：暗黑桃花源

Prob

Tutorial

X Colorful Scarf

Prob

Tutorial

Y 新型背包

Prob

Tutorial