向未来说你好 ICPC 2023 Jinan R

[ICPC 2023 Jinan R] 向未来说你好

对你说再见。

题目链接： [ICPC 2023 Jinan R] 向未来说你好 。

题目内容：

给定长度为 nn 的序列 aa 的一个合法的子段划分为：设第 ii 个子段左右端点为 li,ril_i,r_i ，则需满足：

∀i, ∀j∈[li,ri], ,aj≤ri−li+1\forall i,\ \forall j\in [l_i,r_i],\ ,a_j\le r_i-l_i+1

对于任意一个 ii ，求当 aia_i 变为 11 ，合法子段划分数。

先考虑不带修改的情况。

设 fif_i 为以 ii 为结尾的合法字段划分总数，初始 f0=1f_0=1 ，则有：

fi=∑{fj ∣ ∀k∈[j+1,i], ak≤i−j}f_i=\sum\{f_j\ |\ \forall k\in[j+1,i],\ a_k\le i-j\}

考虑 CDQ 分治。设当前递归区间为 [l,r][l,r] ，区间中点是 midmid ，则需要计算 [l,mid]→[mid+1,r][l,mid] \to [mid+1,r] 的贡献。

注意到 ∀k∈[j+1,i], ak≤i−j ⇔ max⁡{ak}≤i−j\forall k\in[j+1,i],\ a_k\le i-j\ \Leftrightarrow\ \max\{a_k\}\le i-j ，那么自然的，我们可以记录从 midmid 开始，到 ll 结束的后缀最大值和从 mid+1mid+1 开始，到 rr 结束的前缀最大值，用来辅助转移。

具体的，设数组 maxnmaxn ，则：

  • 对于 i∈[l,mid], maxni=max⁡i<j≤mid{aj}i\in[l,mid],\ maxn_i=\max\limits_{i<j\le mid}\{a_j\} 。
  • 对于 i∈[mid+1,r], maxni=max⁡mid<j≤i{aj}i\in[mid+1,r],\ maxn_i=\max\limits_{mid<j\le i}\{a_j\} 。

那么对于 j∈[l,mid],i∈[mid+1,r]j\in[l,mid],i\in[mid+1,r] ， jj 转移到 ii 要满足：

maxni≤i−j ∧ maxnj≤i−jmaxn_i\le i-j\ \land\ maxn_j\le i-j

然后就是经典操作：

  • j≤i−maxnij\le i-maxn_i 。
  • maxnj+j≤imaxn_j+j\le i 。

这是一个二维偏序，直接扫描线树状数组就行。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
namespace BIT{
    int c[N];
    void add(int x,int y){
        for(int i=x;i<=n+1;i+=(i&-i))
            (c[i]+=y)%=P;
    }
    int query(int x){
        int cnt=0;
        for(int i=x;i>=1;i-=(i&-i))
            (cnt+=c[i])%=P;
        return cnt;
    }
    void clear(int x){for(int i=x;i<=n+1;i+=(i&-i))c[i]=0;}
}using namespace BIT;
namespace K1{
    struct node{int x,id;}p[N];
    int tot,maxn[N],f[N];
    void cdq(int l,int r){
        if(l==r)return ;
        int mid=(l+r)>>1;
        cdq(l,mid);
        tot=0;
        maxn[mid]=0;
        for(int i=mid-1;i>=l;i--)maxn[i]=max(maxn[i+1],a[i+1]);
        for(int i=mid+1;i<=r;i++)maxn[i]=max(maxn[i-1],a[i]);
        for(int i=l;i<=mid;i++)p[++tot]={maxn[i]+i,i};
        sort(p+1,p+1+tot,[](node x,node y){return x.x<y.x;});
        for(int i=mid+1,j=1;i<=r;i++){
            while(j<=tot&&p[j].x<=i)add(p[j].id+1,f[p[j].id]),j++;
            int R=i-maxn[i];
            if(R>=0)(f[i]+=query(R+1))%=P;
        }
        for(int i=1;i<=tot;i++)clear(p[i].id+1);
        cdq(mid+1,r);
    }
    void solve(int a[],int F[]){
        f[0]=1;
        for(int i=1;i<=n;i++)f[i]=0;
        cdq(0,n);
        for(int i=0;i<=n;i++)F[i]=f[i];
    }
}

然后这题目有修改 ai=1a_i=1 。考虑 ai=1a_i=1 意味着什么。

容易发现 ai=1a_i=1 和没有对 ii 的限制是一样的，因为任意区间长度至少 11 。

那么当 ai=1a_i=1 时，答案应该有两类：

  1. 原本有限制时也合法的区间。
  2. 原本有限制时不合法，但删掉限制后合法的区间。

第一类就是我们上面算的 fnf_n 。所以我们只用考虑第二类。

简单想想，对于 ii ，一个原本不合法但现在合法的区间 [l,r][l,r] 要满足 ai>r−l+1a_i>r-l+1 ，且 max⁡j∈[l,r]∧j≠i{aj}≤i−j+1\max\limits_{j\in[l,r] \land j\ne i}\{a_j\}\le i-j+1 。

那么有一个暴力做法，就是正着反着按照无修改的方式 DP 两次，记正着为 ff ，反着为 FF ，那么 ii 的答案应该为：

fn+∑l,r[区间 [l,r] 合法]fl−1Fr+1f_n+\sum_{l,r} [\text{区间 }[l,r] \text{ 合法}]f_{l-1}F_{r+1}

容易发现 max⁡j∈[l,r]∧j≠i{aj}\max\limits_{j\in[l,r] \land j\ne i}\{a_j\} 就是 [l,r][l,r] 的次小值，那么我们又可以使用上面的套路了。

考虑 CDQ 分治，设当前分治区间 [l,r][l,r] ，区间中点 midmid ，那么要计算 [l,mid]→[mid+1,r][l,mid] \to [mid+1,r] 的贡献。

那么首先要确定次大值的位置，可能在 [l,mid][l,mid] 也有可能在 [mid+1,r][mid+1,r] ，要分类讨论。

当次大值在 [mid+1,r][mid+1,r] 时：

记录 [l,mid][l,mid] 的后缀最大值 lmilm_i ， [mid+1,r][mid+1,r] 的前缀最大值 rmirm_i ，次大值 rm2irm2_i ，最大值位置 rmposirmpos_i 。

那么 i∈[mid+1,r],j∈[l,mid]i\in[mid+1,r],j\in[l,mid] 能有贡献等价于：

lmj≤i−j+1 ∧ rm2i≤i−j+1 ∧ rmi>i−j+1lm_j\le i-j+1\ \land\ rm2_i\le i-j+1\ \land\ rm_i>i-j+1

拆开就是：

  • lmj+j−1≤ilm_j+j-1 \le i 。
  • i−rmi+1<j≤i−rm2i+1i-rm_i+1<j\le i-rm2_i+1 。

二维偏序，可以用扫描线树状数组。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
namespace K2{
    int lm[N],rm[N],rm2[N],rmpos[N],tot;
    struct node{int x,id;}p[N];
    void cdq(int l,int r){
        if(l==r)return ;
        int mid=(l+r)>>1;
        cdq(l,mid);cdq(mid+1,r);
        tot=0;
        lm[mid]=a[mid];
        for(int i=mid-1;i>=l;i--)lm[i]=max(lm[i+1],a[i]);
        for(int i=l;i<=mid;i++)p[++tot]={lm[i]+i-1,i};
        rm[mid+1]=a[mid+1];
        rm2[mid+1]=0;
        rmpos[mid+1]=mid+1;
        for(int i=mid+2;i<=r;i++){
            rm[i]=rm[i-1];
            rm2[i]=rm2[i-1];
            rmpos[i]=rmpos[i-1];
            if(a[i]>rm[i]){
                rm2[i]=rm[i];
                rm[i]=a[i];
                rmpos[i]=i;
            }
            else if(a[i]>rm2[i])rm2[i]=a[i];
        }
        sort(p+1,p+1+tot,[](node x,node y){return x.x<y.x;});
        for(int i=mid+1,j=1;i<=r;i++){
            while(j<=tot&&p[j].x<=i)add(p[j].id,f[p[j].id-1]),j++;
            int L=i-rm[i]+1,R=i-rm2[i]+1;
            int tl=(L<1?0:query(L));
            int tr=(R<1?0:query(R));
            (ans[rmpos[i]]+=1ll*F[i+1]*(tr-tl+P)%P)%=P;
        }
        for(int i=1;i<=tot;i++)clear(p[i].id);
    }
}

当次大值在 [l,mid][l,mid] 时：

记录 [mid+1,r][mid+1,r] 的前缀最大值 rmirm_i ， [l,mid][l,mid] 的后缀缀最大值 lmilm_i ，次大值 lm2ilm2_i ，最大值位置 lmposilmpos_i 。

那么 i∈[mid+1,r],j∈[l,mid]i\in[mid+1,r],j\in[l,mid] 能有贡献等价于：

rmi≤i−j+1 ∧ lm2j≤i−j+1 ∧ lmj>i−j+1rm_i\le i-j+1\ \land\ lm2_j\le i-j+1\ \land\ lm_j>i-j+1

拆开就是：

  • j≤i−rmi+1j\le i-rm_i+1 。
  • j+lm2j−1≤i<j+lmj−1j+lm2_j-1\le i<j+lm_j-1 。

二维偏序，可以用扫描线树状数组。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
namespace K3{
    struct node{int x,id;}p[N];
    int lm[N],lm2[N],lmpos[N],rm[N],tot;
    void cdq(int l,int r){
        if(l==r)return ;
        int mid=(l+r)>>1;
        cdq(l,mid);cdq(mid+1,r);
        tot=0;
        rm[mid+1]=a[mid+1];
        for(int i=mid+2;i<=r;i++)rm[i]=max(rm[i-1],a[i]);
        for(int i=mid+1;i<=r;i++)p[++tot]={i-rm[i]+1,i};
        lm[mid]=a[mid];
        lm2[mid]=0;
        lmpos[mid]=mid;
        for(int i=mid-1;i>=l;i--){
            lm[i]=lm[i+1];
            lm2[i]=lm2[i+1];
            lmpos[i]=lmpos[i+1];
            if(a[i]>lm[i]){
                lm2[i]=lm[i];
                lm[i]=a[i];
                lmpos[i]=i;
            }
            else if(a[i]>lm2[i])lm2[i]=a[i];
        }
        sort(p+1,p+1+tot,[](node x,node y){return x.x>y.x;});
        for(int i=mid,j=1;i>=l;i--){
            while(j<=tot&&p[j].x>=i)add(p[j].id,F[p[j].id+1]),j++;
            int L=lm2[i]+i-2,R=lm[i]+i-2;
            int tl=(L<1?0:query(min(n,L)));
            int tr=(R<1?0:query(min(n,R)));
            (ans[lmpos[i]]+=1ll*f[i-1]*(tr-tl+P)%P)%=P;
        }
        for(int i=1;i<=tot;i++)clear(p[i].id);
    }
}

那么这个问题就解决了。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <bits/stdc++.h>
using namespace std;
const int N=200010,P=998244353;
int n,a[N],f[N],F[N],ans[N];
void print(int a[]){
    for(int i=1;i<n;i++)printf("%d ",a[i]);
    printf("%d",a[n]);
}
namespace BIT{
    int c[N];
    void add(int x,int y){
        for(int i=x;i<=n+1;i+=(i&-i))
            (c[i]+=y)%=P;
    }
    int query(int x){
        int cnt=0;
        for(int i=x;i>=1;i-=(i&-i))
            (cnt+=c[i])%=P;
        return cnt;
    }
    void clear(int x){for(int i=x;i<=n+1;i+=(i&-i))c[i]=0;}
}using namespace BIT;
namespace K1{
    struct node{int x,id;}p[N];
    int tot,maxn[N],f[N];
    void cdq(int l,int r){
        if(l==r)return ;
        int mid=(l+r)>>1;
        cdq(l,mid);
        tot=0;
        maxn[mid]=0;
        for(int i=mid-1;i>=l;i--)maxn[i]=max(maxn[i+1],a[i+1]);
        for(int i=mid+1;i<=r;i++)maxn[i]=max(maxn[i-1],a[i]);
        for(int i=l;i<=mid;i++)p[++tot]={maxn[i]+i,i};
        sort(p+1,p+1+tot,[](node x,node y){return x.x<y.x;});
        for(int i=mid+1,j=1;i<=r;i++){
            while(j<=tot&&p[j].x<=i)add(p[j].id+1,f[p[j].id]),j++;
            int R=i-maxn[i];
            if(R>=0)(f[i]+=query(R+1))%=P;
        }
        for(int i=1;i<=tot;i++)clear(p[i].id+1);
        cdq(mid+1,r);
    }
    void solve(int a[],int F[]){
        f[0]=1;
        for(int i=1;i<=n;i++)f[i]=0;
        cdq(0,n);
        for(int i=0;i<=n;i++)F[i]=f[i];
    }
}
void init(){
    K1::solve(a,f);
    reverse(a+1,a+1+n);
    K1::solve(a,F);
    reverse(a+1,a+1+n);
    reverse(F+1,F+1+n);
    F[n+1]=1;
}
namespace K2{
    int lm[N],rm[N],rm2[N],rmpos[N],tot;
    struct node{int x,id;}p[N];
    void cdq(int l,int r){
        if(l==r)return ;
        int mid=(l+r)>>1;
        cdq(l,mid);cdq(mid+1,r);
        tot=0;
        lm[mid]=a[mid];
        for(int i=mid-1;i>=l;i--)lm[i]=max(lm[i+1],a[i]);
        for(int i=l;i<=mid;i++)p[++tot]={lm[i]+i-1,i};
        rm[mid+1]=a[mid+1];
        rm2[mid+1]=0;
        rmpos[mid+1]=mid+1;
        for(int i=mid+2;i<=r;i++){
            rm[i]=rm[i-1];
            rm2[i]=rm2[i-1];
            rmpos[i]=rmpos[i-1];
            if(a[i]>rm[i]){
                rm2[i]=rm[i];
                rm[i]=a[i];
                rmpos[i]=i;
            }
            else if(a[i]>rm2[i])rm2[i]=a[i];
        }
        sort(p+1,p+1+tot,[](node x,node y){return x.x<y.x;});
        for(int i=mid+1,j=1;i<=r;i++){
            while(j<=tot&&p[j].x<=i)add(p[j].id,f[p[j].id-1]),j++;
            int L=i-rm[i]+1,R=i-rm2[i]+1;
            int tl=(L<1?0:query(L));
            int tr=(R<1?0:query(R));
            (ans[rmpos[i]]+=1ll*F[i+1]*(tr-tl+P)%P)%=P;
        }
        for(int i=1;i<=tot;i++)clear(p[i].id);
    }
}
namespace K3{
    struct node{int x,id;}p[N];
    int lm[N],lm2[N],lmpos[N],rm[N],tot;
    void cdq(int l,int r){
        if(l==r)return ;
        int mid=(l+r)>>1;
        cdq(l,mid);cdq(mid+1,r);
        tot=0;
        rm[mid+1]=a[mid+1];
        for(int i=mid+2;i<=r;i++)rm[i]=max(rm[i-1],a[i]);
        for(int i=mid+1;i<=r;i++)p[++tot]={i-rm[i]+1,i};
        lm[mid]=a[mid];
        lm2[mid]=0;
        lmpos[mid]=mid;
        for(int i=mid-1;i>=l;i--){
            lm[i]=lm[i+1];
            lm2[i]=lm2[i+1];
            lmpos[i]=lmpos[i+1];
            if(a[i]>lm[i]){
                lm2[i]=lm[i];
                lm[i]=a[i];
                lmpos[i]=i;
            }
            else if(a[i]>lm2[i])lm2[i]=a[i];
        }
        sort(p+1,p+1+tot,[](node x,node y){return x.x>y.x;});
        for(int i=mid,j=1;i>=l;i--){
            while(j<=tot&&p[j].x>=i)add(p[j].id,F[p[j].id+1]),j++;
            int L=lm2[i]+i-2,R=lm[i]+i-2;
            int tl=(L<1?0:query(min(n,L)));
            int tr=(R<1?0:query(min(n,R)));
            (ans[lmpos[i]]+=1ll*f[i-1]*(tr-tl+P)%P)%=P;
        }
        for(int i=1;i<=tot;i++)clear(p[i].id);
    }
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    init();
    K2::cdq(1,n);
    K3::cdq(1,n);
    for(int i=1;i<=n;i++)(ans[i]+=f[n])%=P;
    for(int i=1;i<=n;i++)if(a[i]>1)(ans[i]+=1ll*f[i-1]*F[i+1]%P)%=P;
    print(ans);
    return 0;
}