给出长度为 \(n\) 的排列 \(a_1\sim a_n\),\(m\) 次询问有多少对 \([l,r]\) 满足 \(L\le l\le r\le R\) 且 \(\forall \,i\in [L,R],a_i\in[X,Y]\)。
\(n,m\le 2\times 10^5\)。
\(\text{3 s}\sim\text{7 s / 125 MB}\)。
下文中默认 \(\mathcal{O}(n)=\mathcal{O}(m)\),分块以 \(\mathcal{O}(\sqrt{n})\) 为块长。
考虑对 \([X,Y]\) 这个限制莫队。设当前维护的值域区间是 \([x,y]\),令 \(w_i=[x\le a_i\le y]\)。对于一个询问我们要求当 \(x,y\) 分别扫到 \(X,Y\) 时,\(w\) 数组的区间 \([L,R]\) 内有多少全部为 \(1\) 的子区间。
由于给出的是一个排列,\(x,y\) 移动一步时只会带来 \(b\) 数组一个位置的改变。相当于要支持单点 \(0\) 变 \(1\)(或 \(1\) 变 \(0\)),区间查询 \([L,R]\) 内有多少全部为 \(1\) 的子区间(简称为答案)。
考虑线段树,一个节点维护一下几个信息:
-
\(\text{len}\):代表这个节点对应的区间长度。
-
\(\text{llen}\):代表这个节点对应的区间中,以左端点开始的最长连续 \(1\) 段长度。
-
\(\text{rlen}\):代表这个节点对应的区间中,以右端点结束的最长连续 \(1\) 段长度。
-
\(\text{sum}\):代表这个节点对应的区间的答案。
合并两个节点 \(u,v\) 的信息时,都考虑该信息是否跨过中点。具体地,设 \(\otimes\) 为合并操作:
-
\(\text{len}_{u\otimes v}=\text{len}_u+\text{len}_v\)
-
\(\text{llen}_{u\otimes v}=\begin{cases}\text{len}_u+\text{llen}_v,\text{len}_u=\text{llen}_u\\\text{llen}_u,\text{otherwise}\end{cases}\)
-
\(\text{rlen}_{u\otimes v}=\begin{cases}\text{len}_v+\text{rlen}_u,\text{len}_v=\text{rlen}_v\\\text{rlen}_v,\text{otherwise}\end{cases}\)
-
\(\text{sum}_{u\otimes v}=\text{sum}_u+\text{sum}_v+\text{rlen}_u\cdot\text{llen}_v\)
容易支持单点修改。这样做时间复杂度为 \(\mathcal{O}(n\sqrt{n}\log n)\),空间复杂度为 \(\mathcal{O}(n)\)。不够优美。
原因是修改数量为 \(\mathcal{O}(n\sqrt{n})\),而询问数量仅有 \(\mathcal{O}(n)\)。考虑换成 \(\mathcal{O}(1)\) 修改 \(\mathcal{O}(\sqrt{n})\) 查询的分块。
记:
-
\(\text{bl}_i,\text{br}_i\) 为第 \(i\) 块的左右端点。
-
\(\text{bel}_i\) 为 \(i\) 位置所在块。
-
\(A_i\) 为第 \(i\) 块的信息。
-
\(\text{pos}_i\) 的意义如下:若 \(i\) 是这个块中一个极长 \(1\) 连续段的端点,则 \(\text{pos}_i\) 的值为它所在极长 \(1\) 连续段的另一个端点;否则 \(\text{pos}_i=0\)。
考虑 \(w_i\) 由 \(0\) 变 \(1\) 怎么修改。考虑修改后极长 \(1\) 连续段的情况怎么变,显然它只可能接上修改前 \(i-1\) 所在极长 \(1\) 连续段和 \(i+1\) 所在极长 \(1\) 连续段。以此来处理 \(\text{pos}\) 数组的变化。注意不存在这两个位置或这两个位置与 \(i\) 不在同一块中的情况,具体可以看代码,个人认为讨论了所有可能的情况,虽然有一些繁杂。
处理好修改后 \(i\) 所在极长 \(1\) 连续段后,新增的答案就是这个段中包含 \(i\) 的子区间数量,是容易计算的。
至于 \(\text{llen}\) 和 \(\text{rlen}\) 的变化,容易通过修改后的 \(\text{pos}\) 数组求出。
但是发现 \(w_i\) 由 \(1\) 变 \(0\) 的情况不好处理,于是考虑回滚莫队,每次撤销最新的一次 \(0\) 变 \(1\) 回退上一个版本。用栈按时间顺序存储修改的量即可。
查询可以考虑从左往右遍历每个查询区间中的块(包括散块),散块暴力计算信息,整块就用维护好的 \(A_i\),然后像上面那样合并。
处理询问时,对于左右端点在莫队中分出的块相同时,对于 \([X,Y]\) 这个值域,让指针 \(j\) 从 \(X\) 扫到 \(Y\) 暴力更新 \([X,j]\) 的信息。然后查询、撤销。单次时间复杂度为 \(\mathcal{O}(\sqrt{n})\)。
剩下的询问离线跑回滚莫队。每次做一段左端点在莫队中分出的块相同的询问。假设这一块的右端点为 \(R_0\),我们只考虑撤销 \([X,R_0]\) 的操作,保留 \((R_0,Y]\) 的操作。这样对于排序后的每一个询问 \(i\),可以先从上一个询问的 \((R_0,Y_{i-1}]\) 扩展到这个询问的 \((R_0,Y_i]\),再添加 \([X,R_0]\) 的操作,再查询,再撤销这些操作回到 \((R_0,Y_i]\) 的版本,再继续做下一个询问。
做完一段左端点所在块相同的询问后,暴力清空分块。由于只会有 \(\mathcal{O}(\sqrt{n})\) 种左端点所在块,即这么多次清空,所以清空的总时间复杂度是 \(\mathcal{O}(n\sqrt{n})\)。
修改的和查询的总复杂度都是 \(\mathcal{O}(n\sqrt{n})\)。因此,回滚莫队的做法时间复杂度为 \(\mathcal{O}(n\sqrt{n})\),空间复杂度为 \(\mathcal{O}(n)\)。可以接受。
标签:游戏,text,复杂度,Cnoi2019,sqrt,len,端点,P5386,mathcal From: https://www.cnblogs.com/MnZnOIerLzy/p/18047996