tj

A

操作实际上是对于从前往后数第 \(i\) 个数若为 \(1\)，则可以删除从后往前数第 \(i\) 个数。只用最靠边的 \(1\) 来删是最优的，因为 \(1\) 边上的 \(0\) 一定不会被删掉。

所以答案为

\[n-2\times\min_{a_i=1}\{i-1,n-i\} \]

所以不管怎么删，一定都会走那些步数。

询问是个 Nim 游戏，需要快速求出每个区间的答案。需要支持区间取反，区间求最靠边缘的 \(1\)。

最靠边缘的 \(1\) 可以拆分成第一个 \(1\) 和最后一个 \(1\)，这样就可以直接用线段树维护区间第一个出现的 0,1 以及区间最后一个出现的 0,1 即可解决问题。

B

把 \(a_i,Y\) 都除掉 \(X\)，然后质因数分解一下，把质因数看成元素，每个点权值看成集合。

现在问题是对连通块计数，连通块内的点权的交集为空，并集为全集。

考虑这个等价于：对于每个元素，出现了 0，也出现了 1。

这个等价于：存在一条边，其两端点一个存在这个元素，一个不存在这个元素。

那就边权为点权的异或，然后作树形 dp，用 FMT 优化转移。

\[f_{u,S}=f_{u,S}+\sum_{T_1\cup T_2\cup w=S}f_{u,T_1}f_{v,T_2} \]

但是注意到不需要每次都 FMT，维护 FMT 的点值就可以了。

然后我还要求出每个 FMT 点值 IFMT 回来的某一项，考虑到 FMT 的本质实际上做高维前缀和，那么在
这个点处做高维差分（其实就是子集反演）就可以了。

C

记 \(f_i(j,k)\) 为 \(S[i,j]\) 和 \(T[1,k]\) 的 LCS（原问题线段树分治后的问题）。我们断言存在 \(p\) 和 \(q\) 使得

• \(f_i(j,k)=f_i(j-1,k)+[p(j,k)\leq i\leq j]\)

• \(f_i(j,k)=f_i(j,k-1)+[i<q(j,k)]\)

证明：考虑把求 LCS 视为求在带有一些斜边的网格图上的最大权路径。特判掉一些边界之后，我们证明

• 对于 \(i\leq j-1\)，如果 \(f_i(j,k)>f_i(j-1,k)\)，那么 \(f_{i+1}(j,k)>f_{i+1}(j-1,k)\)
• 对于 \(i\leq j\) 如果 \(f_i(j,k)>f_i(j,k-1)\)，那么 \(f_{i-1}(j,k)>f_{i-1}(j,k-1)\)

那么考虑从 \((i,0)\) 走到 \((j,k)\) 和从 \((i+1,0)\) 走到 \((j-1,k)\) 的最优路径，记为 \(C_1,C_2\)。显然它们一定有交点，我们随便取一个。如果把 \(C_2\) 在交点前的部分换成 \(C_1\) 的，我们就得到了一条 \(\leq f_i(j-1,k)\) 的路径，因此在 \(X\) 后面的部分 \(C_1>C_2\)。而如果我们把 \(C_1\) 在 \(X\) 前的部分换成 \(C_2\)，我们就得到了一条 \(\leq f_{i+1}(j,k)\) 的路径，从而 \(f_{i+1}(j,k)>f_{i+1}(j-1,k)\)。

第二个是类似的，只需要考虑从 \((i-1,0)\) 走到 \((j,k-1)\) 和从 \((i,0)\) 走到 \((j,k)\) 的路径即可。这就完成了证明。

于是可以按照公式给出两种递推：

\[\begin{aligned} f_i(j,k)=&f_i(j-1,k-1)+[p(j,k)\leq i\leq j]+[i<q(j-1,k)]\\ =&f_i(j-1,k-1)+[i<q(j,k)]+[p(j,k-1)\leq i\leq j] \end{aligned} \]

令 \(P=p(j,k-1),Q=q(j-1,k)\)。如果 \(P<Q\) 那么 \([i<Q]\) 和 \([P\leq i\leq j]\) 关于 \(i\) 分别取值如下（省略的部分为 \(0\)）

	\([1,P)\)	\([P,Q)\)	\([Q,j+1)\)
\([i<Q]\)	1	1
\([i\geq P]\)		1	1

由于 \(f_i(j,k)-f_i(j-1,k-1)\leq 1\)，\([P,Q)\) 段不能再继续增加了，所以我们只能让 \(p(j,k)=Q,q(j,k)=P\)。

如果 \(P\geq Q\) 那么这两部分提供的增量为

	\([1,Q)\)	\([Q,P)\)	\([P,j+1)\)
\([i<Q]\)	1
\([i\geq P]\)			1

那么我们还需要决定 \([i<q(j,k)\) 和 \([i\geq p(j,k)\) 在 \([Q,P)\) 段的取值。下面设 \(i\in[Q,P)\)。注意我们已经得到 \(f_i(j-1,k)=f_i(j,k-1)=f_i(j-1,k-1)\)。所以，如果 \(S_j\neq T_k\)，就有 \(f_i(j,k)=\max(f_i(j-1,k),f_i(j,k-1))=f_i(j-1,k-1)\)，从而这一段应该取 \(0\)，故 \(p(j,k)=P,q(j,k)=Q\)。否则，如果 \(S_j=T_k\)，那么 \(f_i(j,k)=f_i(j-1,k-1)+1\)，从而这段应该取 \(1\)，故 \(p(j,k)=Q,q(j,k)=P\)。

这样我们就得到了递推式

\[(p(j,k),q(j,k))=\begin{cases}(Q,P)&S_j=T_k\lor P<Q \\(P,Q)& \text{otherwise}\end{cases} \]

最后是边界。我们需要知道所有 \(p(\cdot,0)\) 和 \(q(0,\cdot)\) 的值。按照含义取为 \(p(j,0)=j+1\) 和 \(q(0,k)=1\) 即可。

现在我们可以对固定的 \(k\) 在 \(O(r-l)\) 时间内计算所有 \(i\in[l,r]\) 的 \(f_{i}(r,k)\)：枚举 \(l\leq j\leq r\)，让 \([p(j,k),j]\) 范围内的 \(i\) 对应的 \(f_i(r,k)+=1\)即可。

可以转置 \(p,q\) 使得询问时缓存友好。

事实上和所谓“海草”是等价的，上面的问题也可以用 bitset 优化位运算之类的技巧做。