NOI 2025 选做 | Sevenki's Blog

D1T1

这也是题？

D2T1

考虑挖掘题目的性质。容易发现：

当序列中出现 110 时，设其中 0 的下标为 $k$ ，答案就是所有 110 的 $n - k + 1$ 的最大值。特别地，如果序列中没有 110，但是出现了 101，那么答案为 1。

又因为要支持区间取反，于是我们可以搞一棵线段树，维护：

区间左右端点与长度
区间 110 出现位置
区间 001 出现位置
区间是否出现 101
区间是否出现 010
区间取反 tag
区间首两个元素和末两个元素

然后相邻两个区间信息合并就是把原来的算上，再考虑两个区间相邻的边界会不会出现新的某特定串。

inline node merge(node L,node R){
    node ret;
    //Part 1
    ret.len = L.len+R.len;
    ret.st1 = L.st1;
    if(L.len>1)ret.st2=L.st2;else ret.st2=R.st1;
    ret.ed2 = R.ed2;
    if(R.len>1)ret.ed1=R.ed1;else ret.ed1=L.ed2;
    ret.l=L.l; ret.r=R.r;
    //Part 1.5
    ret.app101 = L.app101 || R.app101;
    ret.app010 = L.app010 || R.app010;
    ret.pos110 = min(L.pos110,R.pos110);
    ret.pos001 = min(L.pos001,R.pos001);
    //Part 2
    static int tmp[6],pos[6];
    int v=0;
    if(L.len>1)tmp[v++]=(L.ed1),pos[v-1]=(L.r-1);
    tmp[v++]=(L.ed2),pos[v-1]=(L.r);
    tmp[v++]=(R.st1),pos[v-1]=(R.l);
    if(R.len>1)tmp[v++]=(R.st2),pos[v-1]=(R.l+1);
    
    if(v<=2)return ret;
    
    auto chk = [&](int st,int x,int y,int z){
        return tmp[st]==x && tmp[st+1]==y && tmp[st+2]==z;
    };
    ret.app101 |= chk(0,1,0,1); ret.app010 |= chk(0,0,1,0);
    if(chk(0,1,1,0))chkMin(ret.pos110,pos[2]);
    if(chk(0,0,0,1))chkMin(ret.pos001,pos[2]);
    if(v<=3)return ret;
    
    ret.app101 |= chk(1,1,0,1); ret.app010 |= chk(1,0,1,0);
    if(chk(1,1,1,0))chkMin(ret.pos110,pos[3]);
    if(chk(1,0,0,1))chkMin(ret.pos001,pos[3]);
    return ret;
}

然后修改某个节点就是把记录的相对应的东西交换一下，并对记录的首尾四个元素取反。

D1T2

考虑操作的方式。我们不妨把每次操作中较小的那个元素向较大的元素连边，易得每个节点至多只有一条出边，且不会形成环。（请不要对相邻的 0 和 0 做无谓的操作！）

于是可以想象，操作完成后，一个序列由若干个形如下图的东西组成：

\dots \to x - 3 \to x - 2 \to x - 1 \to x \leftarrow x + 1 \leftarrow x + 2 \leftarrow x + 3 \leftarrow \dots

以下将形如此状的 $x$ 称为 top。

第一问

接下来讨论第一问。

我们考虑可以把序列划分成段，每段按照上述形状计算出段内最大值。设 $f_{i}$ 为以 $i$ 结尾，前面部分的最大值。有转移方程：

f_{i} = max_{0 \leq j < i} {f_{j} + calc (j + 1, i)}

然后考虑在 $O (n^{2})$ 的复杂度内预处理出 $calc$ 。

对于每个左端点，我们预处理出他能贡献到的最远的 top $R m a x_{l}$ ，右端点同理预处理出 $L m i n_{r}$ 。

这样子对于每个询问，端点只会在区间 $[max (l, L m i n_{r}), min (r, R m a x_{l})]$ 之中。

考虑什么样的点能成为 top。

对于一段区间，我们考虑每个数对 top 的贡献。容易发现与 top 距离为偶数的点有正贡献，否则有负贡献。

那么我们计算区间 $s = \sum_{i \in [l, r]} (- 1)^{i + 1} a_{i}$ 的值。

当 $s = 0$ 时，显然任意位置上的数都可以作为 top。
当 $s > 0$ 时，这意味着最后有数残余，且残余那一位系数为正，因为只有残余的那一位可以作为 top，所以 top 一定在 $(- 1)^{i + 1} = 1$ 的点位上，即奇数下标点位。
当 $s < 0$ 时，这意味着最后有数残余，且残余那一位系数为负，top 一定在 $(- 1)^{i + 1} = - 1$ 的点位上，即偶数下标点位。

当 $s = 0$ 时，无论 top 怎么选最后整段区间都会变成 $0$ ，于是这段区间的 $calc (l, r)$ 就是区间 $b_{i}$ 的和。

否则，top 位置无法造成贡献，这段区间的 $calc (l, r)$ 就是区间 $b_{i}$ 的和减去 top 处的 $b_{i}$ 。我们想最大化贡献，就得最小化 top 处贡献，于是在 top 可取区间内找到满足下标限制的 $b_{i}$ 最小值即可。注意 top 是有奇数下标或偶数下标限制的，因此要对两种下标分别预处理区间 min，这个可以直接暴力 $O (n^{2})$ 处理。

另外，【某数没有被进行操作】可以通过 $l = r$ 的情况转移（以下第二问也是如此）。

第二问

以上我们做完了第一问，到了第二问，我们沿用第一问的思路，但是你会发现形似 ${1, 1, 1, 1}$ 的区间会有 ${1, 1, 1, 1}$ 或 ${1, 1}, {1, 1}$ 等多种表现方式，我们不妨规定：在计算之前的【最远左右端点】时对于能消为 0 的不再扩展。

如此便处理完了大多数情况，避免算重，但是你会发现对于 $r = l + 1$ 且 $a_{l} = a_{r}$ 的区间上述做法不会统计下来，但是这恰恰是我们需要统计的最小单元，于是特判一下即可。

剩下的就和以前的做法差不多了：我们设 $g_{i}$ 为截止下标 $i$ ，题目所求式子的值。有转移方程：

g_{i} = \sum_{0 \leq j < i} g_{j} \times Bcalc (j + 1, i)

其中 $g_{0} = 1$ 。

然后对于 $Bcalc$ 的计算，我们考虑先处理出区间 $[l, r]$ 中 $c$ 的乘积（设为 $p$ ）。

沿用第一问时的 $s$ 。

当 $s = 0$ 时，无论怎么选 top 最终都是 0，答案即为 $p$ 。
当 $s > 0$ 时，top 在奇数下标。
当 $s < 0$ 时，top 在偶数下标。

对于一个 top 下标为 $t$ ，其答案即为 $p \times {invC}_{t}$ 。

那么我们对每个点位的 $c$ 的逆元进行前缀和（同样也要分两种下标进行）。

然后设 top 可行区间中满足下标条件的点位的逆元之和为 $v$ ，那么 $Bcalc (l, r)$ 就是 $p \times v$ 。

如此，我们做完了这道题目。