ARC153C ± Increasing Sequence

adpitacor · 2023-01-15 10:44:31 · 题解

由于个人偏好原因，以下将用 a 表示原题的 A，b 表示原题的 x，A 和 x 失去其原本的含义。

题目大意

• 给定 n 和一个长度为 n 的序列 a，满足 a_i \in \{-1,+1\}。

• 你要尝试求出一个长度为 n 的序列 b，满足以下限制：

  • 序列严格递增，即 \forall 1 \leq i < n，b_i < b_{i+1}；

  • 将 a 中的正负号带入 b 中后，b 的和为 0，即 \sum\limits_{i=1}^n{a_ib_i} = 0。

• 如果存在这样的序列，输出 Yes 和一个满足条件的序列 b；如果不存在，则输出 No。

题解

记 s = \sum\limits_{i=1}^n{a_ib_i}。

发现样例 1 的输出没有规律，由于题目要求 b 递增，考虑先填入 1 \dots n，如果此时 s \neq 0，想办法修改 b，把和调整到 0。

由于填入的数两两相邻，无法直接修改 b_{2 \dots n-1}，考虑调整 b_1（将其减小）或 b_n（将其增大）。

于是可以得出结论：如果 a_1 = a_n，则必然有解。以 a_1 = a_n = 1 为例，调整方法如下：如果 s > 0，令 b_1 减去 |s|；如果 s < 0，令 b_n 加上 |s|。a_1 = a_n = -1 的情况只需把判断条件交换即可。

等等，会不会只改一个数超出数值大小限制了？是否会有把调整分摊到两个数的需要？

一方面，即使在 a_i 全部相等的情况下，填完 1 \dots n 之后仍有 |s| < (2 \cdot 10^5)^2 = 4 \cdot 10^{10} < 2 \cdot 10^{12}。

另一方面，这也引出了另一个突破口：在调整了 b_1 之后，是可以接着调整 b_2 的；依此类推可知，事实上，可以同时调整一个前缀或者后缀（也就是对 b 进行前缀减或者后缀加）。

以前缀为例，对于 1 \leq x \leq n，如果将 b_{1 \dots x} 全部减去 d_b，则这次调整会使 s 减去 \sum\limits_{i=1}^x{(a_i \cdot d_b)} = (\sum\limits_{i=1}^x{a_i})d_b（记为 d_a \cdot d_b）。后缀类似，只不过 \lbrack 1,x \rbrack 变为 \lbrack x,n \rbrack，减去变为加上。

在这里，d_b 一定是正数（一如前面的 |s| 用了绝对值），但是 d_a 的正负性与我们取的前后缀有关。如果存在 d_a 为正的前缀或者 d_a 为负的后缀，那么我们可以通过调整这个区间使 s 减小；能使 s 增大的情况与之相对。

那怎么控制改变的数值大小呢？以 d_a 为正的前缀为例，可以发现，只要存在 d_a = 1 的前缀，就可以通过令 d_b = |s| 进行调整来消去任意正 s。那会不会只存在 d_a > 1，却不存在 d_a = 1 的前缀呢？不会，因为一定可以从 d_a > 1 的前缀中拆出 d_a = 1 的前缀。所以，只需要找 |d_a| = 1 的前、后缀用于调整即可。

（如果还不清楚做法可以结合后面的代码理解）

说了这么多，让我们来手模一组数据吧：

一开始填入 1 \dots n 后，s = -1+2+3+4 = 8；在此例中，有两种调整策略：既可以将 d_a = 1 的前缀 \lbrack 1,3 \rbrack 整体减 8，也可以将 d_a = 2 的前缀 \lbrack 1,4 \rbrack 整体减 4。需要强调的是，并不是说 |d_a| > 1 不行，只是 |d_a| = 1 适用范围更广（比如此处使用 d_a = 2 的前缀调整要求 |s| 被 2 整除）。

显然，如果通过调整同时能使 s 减小或增大，就一定可以按如上方法得到一组答案。这是充分性。那是否有必要性呢？

考虑一个以 -1 开头的序列 a，它已经能够通过 d_a=1 的区间 \lbrack 1,1 \rbrack 使 s 增大了。我们尝试构造它，使得无论怎么调整，s 只能增大：

• 记 \{\underbrace{-1, \dots, -1}_{x\text{个}-1},\underbrace{+1, \dots, +1}_{x\text{个}+1}\} 为 U；

• 最后发现符合要求的 a 只能是形如若干个 U（x 不一定相等）拼接而成。

证明不够严谨，但可以感性理解这个结论。我不会写啊QwQ

构造是构造出来了，可惜这样的序列本身就是无解的。由于这样的 a 中 -1 和 +1 的总数相同，+1 又一定出现在至少一个 -1 之后，于是我可以建立对应关系，令每一个 a_i=+1 都对应它前面最近的 a_j=-1，对应关系可以覆盖每个位置；又由于 b 单调递增，对于每个这样的对 (i,j)，代入符号后，+b_i-b_j 一定为正；每个对的和都为正，那 s 一定也为正，也就不可能为 0 了。

开头是 +1 的情况同理。

至此可知，如果不是同时能使 s 减小或增大，那就无解了，所以必要性得证。

到这里我们终于可以说：初始设置的 b 可以任意取一个递增的数列（只要调整后不超过 b_i 大小限制），因为有解必然能调整出来，调整不不来一定无解。

关于时间复杂度：填入 1 \dots n，求出 s，找到 |d_a| = 1 的前、后缀位置，进行调整，都是 O(n) 的操作。

代码

#include<cstdio>
#define ll long long
#define N_ 200010
int n,sgn[N_];
int pre_n1,pre_p1,suf_n1,suf_p1;
//(前/后缀)_(d_a)
//pre(fix), suf(fix)
//n(egative)1, p(ositive)1
ll ans[N_],s;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&sgn[i]);
        ans[i]=i,s+=sgn[i]*i;
    }
    for(int i=1,cnt=0;i<=n;i++){
        cnt+=sgn[i];
        //由于变化量为 ±1，cnt 第一次变为正/负时绝对值一定为 1
        if(!pre_n1&&cnt<0)pre_n1=i;
        if(!pre_p1&&cnt>0)pre_p1=i;
        if(pre_n1&&pre_p1)break;
    }
    for(int i=n,cnt=0;i;i--){
        cnt+=sgn[i];
        if(!suf_n1&&cnt<0)suf_n1=i;
        if(!suf_p1&&cnt>0)suf_p1=i;
        if(suf_n1&&suf_p1)break;
    }
    int pre=0,suf=0;
    //根据 s 的正负性选择需要的区间
    if(s<0)s=-s,pre=pre_n1,suf=suf_p1;
    else if(s>0)pre=pre_p1,suf=suf_n1;
    if(s){
        if(pre){
            for(int i=1;i<=pre;i++)ans[i]-=s;
        }
        else if(suf){
            for(int i=suf;i<=n;i++)ans[i]+=s;
        }
        else{
            printf("No"); return 0;
        }
    }
    printf("Yes\n");
    for(int i=1;i<=n;i++){
        printf("%lld ",ans[i]);
    }
    return 0;
}