「KDOI-06-S」合并序列

· · 题解

感觉我可能做麻烦了...

考虑设

首先转移 g，这个比较简单：

g(l,r,v)=g(l+1,r,v)\text{ or }g(l,r-1,v)\text{ or }(f(l,r)=1\text{ and } s(l,r)=v)

其中 s(l,r)=\oplus_{i=l}^ra_i；\oplus 表示异或。

然后转移 f。考虑最后一次操作，由于任意时刻当前序列中的一个数都对应原序列中的一个区间，因此最后一次操作时大概就是左右端点在原序列中分别代表 [l,p],[q,r]，然后 [p+1,q-1] 这个区间得能缩出来一个 s(l,p)\oplus s(q,r)。当然两边还得能缩起来。形式化来讲就是

f(l,p)=f(q,r)=g(p+1,q-1,s(l,p)\oplus s(q,r))=1

这样做是 O(n^4+n^2a)，考虑优化这个转移。实际上这个跑得比后面的 n^3 快一万倍

考虑把 g 再套一次，然后只枚举 p。具体来说设 h(l,r,v) 表示 [l,r] 中能否选出 p，使得

考虑怎么转移 h。显然可以枚举 p 直接做，但复杂度还是 O(n^3a)；不过我们发现，由于 g 具有某种意义上的区间单调性，也就是说如果 g(l,r,v)=1 那么对任意 L\le l\le r\le R 都有 g(L,R,v)=1。

因此，如果 h(l,r,v)=1，那么对任意 L\le l 均有 h(L,r,v)=1（我们只需要取 p 为 h(l,r,v) 选择的 p 就可以了）。只需要改成 h'(r,v) 表示最大的 l 使得原来的那个 h(l,r,v)=1 即可。

下面我们记 h(r,v)=h'(r,v)。为了计算 h(r,v)，大概还需要算 w(r,v) 表示最大的 l 使得 g(l,r,v)=1，然后算 h(r,v) 就只需要枚举 p 了。

这样这部分就是 O(n^2a) 了，于是总的复杂度就是 O(n^3+n^2a)。当然说的是单组数据。

关于构造方案：首先，我们可以在转移的时候顺便记录下 f(l,r) 选择的 p，然后在构造方案的时候直接取 q=r，这样显然也不会超过 O(n^3)；接下来找到 p 之后，我们先递归地构造出 [l,p] 的方案，然后对于 g 显然也只需要 f 的方案，因此差不多就可以构造了。

然后 g 大概还要记录一下合出来这个数之后位置在哪。

然后构造的时候顺便把下标偏移一下就可以了，想清楚还是比较好写的！

我写的 O(n^3+n^2a) 常数实在太大，这里是一份 O(n^3) 但是过不去的代码。

这里是一份 O(n^4) 但是跑得飞快的代码。