P1037 · OFFICIAL SOLUTION

P1037 重彩书遗年官方题解

Gioush OJ · P1037 重彩书遗年

重彩书遗年

【题意简述】

每次选择一个长度恰为 $m$ 的区间，并从左到右依次写入 $1,2,\ldots,m$ 。一个序列合法，当且仅当它可以通过若干次操作得到，并且每个位置都至少被覆盖一次。求将给定序列修改为合法序列所需的最少修改次数。

【Hint】

【提示】

考虑一个合法序列从左向右的变化。若当前值为 $j>1$ ，它只能接在 $j-1$ 后，或者接在某个值为 $m$ 的位置后。把“是否可行”改成“最多保留多少个原值”，即可得到动态规划。

【数据点 1∼61\sim 61∼6】

合法序列的第一个位置必须为 $1$ ，最后一个位置必须为 $m$ 。

若前一位不是 $m$ ，当前值只能接着增加到前一位加 $1$ ，或者从 $1$ 开始一次新的覆写。若前一位是 $m$ ，覆盖到前一位的操作已经结束，可以调整操作顺序，使当前位置接在任意合法前缀之后。

枚举保留不修改的位置集合。令 $g_{i,j}$ 表示处理到第 $i$ 位，当前位置最终为 $j$ ，并且集合中不超过 $i$ 的位置均保持原值时是否可行。

令 $w_{i,j}$ 表示第 $i$ 位不要求保留，或者 $a_i=j$ 。初值为 $g_{1,1}=w_{1,1}$ ，其余状态为假。转移为

\begin{cases} g_{i,1}=\left(\displaystyle\bigvee_{k=1}^{m}g_{i-1,k}\right)\land w_{i,1},\\[0.6em] g_{i,j}=(g_{i-1,j-1}\lor g_{i-1,m})\land w_{i,j},&2\leq j\leq m. \end{cases}

最终要求 $g_{n,m}$ 为真。枚举全部 $2^n$ 个集合，取可行集合大小的最大值。

【数据点 7∼127\sim 127∼12】

根据上一档部分分的启发，不再枚举保留集合，而是把状态改成最大保留位置数量。

定义 $f_{i,j}$ 表示处理到第 $i$ 位，当前位置最终为 $j$ 时，最多有多少个位置不需要修改。不可能的状态设为负无穷，初值为

f_{1,1}=[a_1=1].

当 $m\leq 2$ 时只有常数个状态，直接按照上一档的两种衔接更新。答案为 $n-f_{n,m}$ ，时间复杂度为 $\mathcal{O}(n)$ 。

【数据点 13∼1913\sim 1913∼19】

去掉 $m\leq 2$ 的限制后，完整转移为

\begin{cases} f_{i,1}=\displaystyle\max_{1\leq k\leq m}f_{i-1,k}+[a_i=1],\\[0.6em] f_{i,j}=\max\{f_{i-1,j-1},f_{i-1,m}\}+[a_i=j],&2\leq j\leq m. \end{cases}

滚动数组后，时间复杂度为 $\mathcal{O}(nm)$ ，空间复杂度为 $\mathcal{O}(m)$ 。

【转移的充要性】

上述局部转移等价于把合法序列划分为若干连续上升段。相邻两段之间，要么前一段以 $m$ 结尾，要么后一段从 $1$ 开始。

先证明必要性。考虑相邻两段分别由两次覆写留下。若左侧覆写较晚，它会继续向右写入，直到留下段尾的 $m$ ；若右侧覆写较晚，它会从自身区间的第一个位置留下 $1$ 。因此每个分段位置必然满足这两个条件之一。

再证明充分性。从左向右按照转移构造。段内使用 $j-1\to j$ ，新段从 $1$ 开始；当一段以 $m$ 结束时，对应覆写已经结束，之后可以接入任意合法状态。于是每个满足上述分段条件的序列都可以由若干次覆写得到。

因此，DP 枚举的恰好是全部合法序列。

【正解】

朴素转移中反复出现四类操作：

所有状态整体右移一位；
查询全部状态的最大值；
对 $j=2,3,\ldots,m$ 执行 $f_j\leftarrow\max(f_j,f_m)$ ；
对 $f_{a_i}$ 加 $1$ 。

使用线段树维护这些状态。处理第 $i$ 位之前，令线段树坐标 $nl+j-1$ 保存 $f_{i-1,j}$ 。

先查询旧的 $f_m$ ，记为 Last，再令 $nl\leftarrow nl-1$ 。这样旧的 $f_{j-1}$ 自动落到新的 $f_j$ 所在坐标，完成全部状态的整体右移。

新的 $f_1$ 等于旧状态最大值 Best，因此在坐标 $nl$ 单点赋值。对 $j=2,3,\ldots,m$ 统一执行

f_j\leftarrow\max(f_j,\texttt{Last}),

对应在线段树上进行一次区间取最大值。最后在坐标 $nl+a_i-1$ 单点加 $1$ ，并用返回值更新 Best。

线段树维护区间最大值，支持区间取最大值与单点加。懒标记 Tag 表示整段至少取到的下界，两个标记的复合为取最大值。

初始时全部位置为负无穷，只在表示 $f_{1,1}$ 的位置写入 $[a_1=1]$ 。处理完成后，查询表示 $f_{n,m}$ 的位置，答案为 $n-f_{n,m}$ 。

【复杂度分析】

每个位置进行常数次线段树操作。时间复杂度为 $\mathcal{O}(n\log(n+m))$ ，空间复杂度为 $\mathcal{O}(n+m)$ 。

【参考代码】

1/*2Author:Ehundategh3Date:2026/6/184Name:F.cpp5You steal,I kill.6*/7#include <cstdio>8#include <cstring>9#include <algorithm>10#define LSon Node[Now].LeftSon11#define RSon Node[Now].RightSon12using namespace std;13 14int T,n,m,Line[500010],cnt=0;15 16struct node {17    int l,r;18    int LeftSon,RightSon;19    int Max,Tag,Add;20}Node[4000010];21 22void Update(int Now) {23    Node[Now].Max=max(Node[LSon].Max,Node[RSon].Max);return;24}25 26void PushDown(int Now) {27    if (Node[Now].Tag==-1) return;28    Node[LSon].Max=max(Node[Now].Tag,Node[LSon].Max);29    Node[RSon].Max=max(Node[Now].Tag,Node[RSon].Max);30    Node[LSon].Tag=max(Node[LSon].Tag,Node[Now].Tag);31    Node[RSon].Tag=max(Node[RSon].Tag,Node[Now].Tag);32    Node[Now].Tag=-1;return;33}34 35inline int Build(int l,int r) {36    int Now=++cnt;37    Node[Now]={l,r,0,0,-0x3f3f3f3f,-1,0};38    if (l==r) return Now;39    int Mid=(l+r)>>1;40    LSon=Build(l,Mid);RSon=Build(Mid+1,r);Update(Now);41    return Now;42}43 44inline void Modify(int Now,int l,int r,int Val) {45    if (l>r) return;46    if (Node[Now].l>r||Node[Now].r<l) return;47    else if (Node[Now].l>=l&&Node[Now].r<=r) Node[Now].Tag=max(Node[Now].Tag,Val),Node[Now].Max=max(Node[Now].Max,Val);48    else {49        PushDown(Now);50        Modify(LSon,l,r,Val);Modify(RSon,l,r,Val);Update(Now);51        return;52    }53}54 55inline int Add(int Now,int Pos) {56    int Ret;57    if (Node[Now].l==Node[Now].r) {Node[Now].Max++;return Node[Now].Max;}58    else {59        PushDown(Now);60        if (Node[LSon].r>=Pos) Ret=Add(LSon,Pos);61        else Ret=Add(RSon,Pos);62        Update(Now);63    }64    return Ret;65}66 67inline int Query(int Now,int l,int r) {68    if (l>r) return -0x3f3f3f3f;69    if (Node[Now].l>r||Node[Now].r<l) return -0x3f3f3f3f;70    else if (Node[Now].l>=l&&Node[Now].r<=r) return Node[Now].Max;71    else {72        PushDown(Now);Update(Now);73        return max(Query(LSon,l,r),Query(RSon,l,r));74    }75}76 77void Solve() {78    scanf("%d%d",&n,&m);79    for (int i=1;i<=n;i++) {80        scanf("%d",&Line[i]);81    }82    int nl=n;cnt=0;83    Build(1,n+m+10);84    Modify(1,nl,nl,(Line[1]==1));85    int Best=(Line[1]==1);86    for (int i=2;i<=n;i++) {87        int Last=Query(1,nl+m-1,nl+m-1);88        nl--;89        Modify(1,nl,nl,Best);90        Modify(1,nl+1,nl+m-1,Last);91        int NewVal=Add(1,nl-1+Line[i]);92        Best=max(Best,NewVal);93    }94    printf("%d\n",n-Query(1,nl+m-1,nl+m-1));95    return ;96}97 98int main() {99    int c;100    scanf("%d%d",&c,&T);101    while (T-->0) Solve();102    return 0;103}