题解：CF1416E Split

· · 题解

过于离谱了。

首先 dp。设 dp_{i,j} 表示考虑了前 i 个数，最后一位为 j 时的答案。那么转移有两种：

  1. 从上一个接过来，dp_{i,j}\gets dp_{i-1,a_i-j}+1-[a_i=2j]。
  2. 不接了开摆，dp_{i,j}\gets dp_{i-1,k}+2-[a_i=2j]。

朴素转移是 \mathcal{O}(nV) 的。不过可以发现重要性质：只有取到全局最小值的状态是有用的。

为什么呢？先尝试描述一下转移，形如：

全局 +1 放到最后 +n 即可，暂时不考虑。最烦的情况当然是全局 chkmin。不过事实上，chkmin 成功，相当于非小值干过最小值了。而这是几乎不可能发生的，因为最小值转移不会多加东西，甚至次小值也至少要 -2 才能干过他。唯一的一种情况是最大值全部被截断了，无法转移。但这个时候依然可以选择开摆，还是能赢过次小值。

因此可以直接用 set 维护最小值对应的位置。注意，当最小值被删空后，当前这个数会直接选择开摆，转移形如全局推平。这个时候再维护位置就爆炸了。不过可以发现当且仅当删空时会出现这种操作，所以单独记录区间 [l,r] 表示插入了这段区间即可。总时间复杂度 \mathcal{O}(n\log n)。

全局反转平移的处理方法稍微说明一下：维护数轴原点 p 和正方向 t，转移 a_i 就是 t\gets -t,p\gets a_i-p。方便起见可以全部映射回初始坐标。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 5e5 + 10;

int T, n, a[MAXN], ans;

ll t, p, l, r; set<ll> s;

int main() {
    for (scanf("%d", &T); T--; ) {
        scanf("%d", &n), s.clear(), ans = 0, t = 1, p = 0, l = 1, r = 0;
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) {
            t *= -1, p = a[i] - p;
            ll tl = (1 - p) * t, tr = (a[i] - 1 - p) * t;
            if (t < 0) swap(tl, tr);
            for (; !s.empty() && *s.begin() < tl; s.erase(s.begin()));
            for (; !s.empty() && *--s.end() > tr; s.erase(--s.end()));
            l = max(l, tl), r = min(r, tr);
            if (s.empty() && l > r) t = 1, p = 0, l = 1, r = a[i] - 1, ans++;
            if (~a[i] & 1) {
                ll x = a[i] >> 1, y = (x - p) * t;
                if (s.find(y) != s.end() || l <= y && y <= r) {
                    s.clear(), s.emplace(x);
                    t = 1, p = 0, l = 1, r = 0, ans--;
                } else s.emplace(y);
            }
        }
        printf("%d\n", ans + n);    
    }
}