自动搬运

查看原文

来自洛谷，原作者为

	myee 与其诺诺以顺，不若谔谔以昌 | AFO

搬运于2025-08-24 22:18:27，当前版本为作者最后更新于2020-03-24 16:37:15，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

---

Update

$\LaTeX$ 又双叒叕炸了的话就到我博客上去看吧。

• 2020-7-6 这篇题解已经咕了大半年了,暑假里又开始更新

• 2020-7-10 这篇题解写完了!

---

引言

谔谔,月赛时做完了 $O(n^2)$ 算法AC

后来瞄了瞄题解发现大家都是至少 $O(n\log n)$ 的算法

于是滚回去加优化了,把时间复杂度加速到了 $O(n)$ 的层次

然鹅实际运行时间并没有多大变化,我谔谔

那么,我是如何加速的呢?

先看原算法。

---

$O(n^2)$ 算法

$10$ 分程序

算法思路: 考虑使用动态规划解决此问题。

对于输入数据数列(记作 $\{A_i\}$ )前 $n$ 项,欲求其答案,是否可以由前 $n-1$ 项的答案经一定的修改后获取原序列对此的答案?发现可以。

怎么做?

在第 $n$ 时刻,对于第 $m$ 项的答案,设为 $B_{n,m}$

易证 $B_{n,i}$ 跑遍 $1$ 到 $n$ 。(基于 $B_n$ 的定义)

建立辅助数组 M[],表示 $\{A_i\}$ 当前时刻前 $n$ 项至少两项的连续上升子序列的最后一项的值的位置,如有多个位置满足,取最后一项。

请仔细咀嚼一下上面那句话,这句话十分重要。

则定理:

• $\forall A_n>A_{n-1},B_{n,n}=n,B_{n,i}=B_{n-1,i}.\\$ 把M[ $A_n$ ]赋值为 $n$ （显然,此时单调栈 $\mathrm{push}$ 了一次而未 $\mathrm{pop}$ ）
• $\forall A_n\le A_{n-1},$ 则 $\mathrm{push}$ 了共 $A_{n-1}-A_n+1$ 次,用数组M往回翻一下,翻的过程中, $\\B_{n,n}=\mathrm{M}[A_n],B_{n,i}=B_{n-1,i}+1$ ,而最前面的 $\mathrm{M}[A_n]-1$项来说, $B_{n,i}=B_{n-1,i}$

然后我们发现 $B_n$ 就是答案。

空间爆炸

可是二维数组B开不下( ${(10^6)}^2$ 项)!

空间复杂度是 $O(n^2)$ 的！

前功尽弃了么?

不！

考虑使用滚动数组B,则可以把空间榨取到 $O(n)$

滚动数组就不细讲了,参见以下部分代码,可以意会。

注意以下代码是由 $0$ 开始计数的!

...

int A[1000010],B[1000010];
int M[1000010]={0};

int main()
{
    int n;scanf("%d",&n);
    for(int i=0;i<n;i++)//read
        scanf("%d",A+i);
    for(int i=1;i<n;i++)
    {
        if(A[i]<=A[i-1])
        {
            for(int j=M[A[i]];j<i;j++)B[j]++;//QAQ
            B[i]=M[A[i]]+1;
        }
        else M[A[i]]=i,B[i]=i+1;
    }
    for(int i=0;i+1<n;i++)printf("%d ",B[i]);
    printf("%d\n",B[n-1]);
    return 0;
}

马蜂清奇就不怪我了

代码源码 (内容不太一样,是我比赛时原码)

发现 $Sub2$ AK.

$100$ 分程序

先不考虑带 $-1$ 的情况,观察样例二,发现什么?

样例二输入输出数据:

10
1 1 2 2 3 2 3 3 4 5 

2 1 5 4 6 3 8 7 9 10

不难发现:

• $\forall A_n>A_{n-1},A_n=A_{n-1}+1$ (显然,上升时单调栈只会 $\mathrm{push}$ 一次而不 $\mathrm{pop}$ ,故如此)
• 首项值为 $1$ (同理)

考虑上述 $10$ 分程序的过程,易有总使 $\{A_i\}$ 中每项值为 $-1$ 的值最优情况为前一项的值再 $+1$ ,而首项值为 $1$ 。

于是如此 $O(n)$ 预处理即可。

然后你就切了这道题。

代码略。

---

$O(n)$ 算法

以上算法很快,但是如果最坏情况一切 $A_i=1$ ,直接 $O(n^2)$ 给T掉

其实,原先上述那份代码,我打了"QAQ"标记的地方,可以再优化!

连续一段区间同时增加相同值,最后求总序列,你想到了什么?

树状数组

线段树

考虑使用数据结构差分数列解决。

差分数列的讲解这里与网上都有很多,此处就略去不谈了。

贴一发 $O(n)$ 的AC代码:

#include<stdio.h>
#include<algorithm>

int A[1000010],B[1000010];
int M[1000010]={0};

int main()
{
    int n,wil;
    scanf("%d",&n);
    for(int i=0;i<n;i++)
        scanf("%d",A+i);
    wil=A[0]=B[0]=1;M[1]=0;
    for(int i=1;i<n;i++)
        if(A[i]==-1)
            A[i]=A[i-1]+1;
    for(int i=1;i<n;i++)
    {
        if(A[i]<=A[i-1])
        {
            B[M[A[i]]]++;
            B[i]=M[A[i]]-wil;
            wil=M[A[i]]+1;
        }
        else
        {
            B[i]=i+1-wil;
            M[A[i]]=i;
            wil=i+1;
        }
    }
    printf("%d",wil=B[0]);
    for(int i=1;i<n;i++)printf(" %d",wil+=B[i]);
    putchar('\n');
    return 0;
}

---

最后

谢谢观赏!