题解：P16313 [ICPC 2023 Jinan R] 向未来说你好

dyc2022 · 2026-07-20 22:38:30 · 题解

更好的阅读体验

某一天调这道题调到了 0:22，特此记录。

首先考虑静态情形，也就是没有 a_i 被修改的情况。

那么这个问题就是 [PA 2014] Druzyny 的弱化版，可以用类似地方法解决。具体地，我们假设 f_i 表示将 [1, i] 分段地方案数，有转移

转移不连续，一般手法不太好优化，因此考虑 cdq 分治。每次处理 [l, r] 的 dp 值，记 mid 为区间中点，则只考虑 [l, mid] 的 j 对 [mid+1, r] 的 i 的贡献。记 ml_j 表示 [j, mid] 上的最大值，mr_i 表示 [mid+1, i] 上的最大值。则一个 j 可以对一个 i 产生贡献可以写成 i - j \ge \max\{ml_{j+1}, mr_i\}。

拆掉 \max 可以得到以下两个式子：

由上可以发现，我们把每个 j 看作一个二维平面上的点 (j + ml_{j+1}, j)，则会对一个特定 i 产生影响的 j 位于一个矩形中。因此可以通过扫描线求解二位数点，来完成 j 对 i 的转移。

接下来考虑如何计算把一个 a_k 置于 1 后的影响。我们直接思考在原先的 f_n 基础上的增量。

那么我们用求 f 完全一样的方案求出一个 g_i 表示 [i, n] 的分段方案数。将 a_k 置为 1 后，应该多出一些包含 k 的合法的段。

现在考虑一个段 (j, i]，容易发现，如果 (j, i] 变成了一个合法的段，则会新增 f_j \cdot g_{i+1} 种分段方案。这一段会被计算为新增贡献，首先要满足这一段在 a_k 置于 1 之前是不合法的，也就是 i - j < \max\{a_{j+1}, a_{j+2}, \cdots, a_i\}。然后，将 a_k 赋值为 1 后这一段变合法了，则说明 a_k 是区间内唯一的最大值，而修改后区间的最大值变为了原区间的严格次大值，也就是 i - j \ge \operatorname{2^{nd}-max} \{a_{j+1}, a_{j+2}, \cdots, a_i\}。容易发现一个 (j, i] 会贡献到的 k 是唯一的。这启发我们，仍然通过分治计算新增的贡献。

仍旧对于区间 [l, r]，仅考虑 [l, mid] 的 j 和 [mid+1, r] 的 i 产生的新增贡献。接下来将要讨论 (j, i] 的最大值是在 (j, mid] 还是在 [mid+1, r] 两种情况，为减少篇幅，仅考虑最大值在 (j, mid] 的情况。

则记 ml_j 表示 [j, mid] 的最大值，ml2_j 表示 [j, mid] 的次大值，mr_i 表示 [mid+1, r] 的最大值。则要满足以下两个条件：

由第二个不等式，可以得到

此时在第一个式子中 i - j < mr_i 已经不成立，因此只有

由上述三个式子，可以发现，如果把每个 i 看作平面上的一个点 (i, i - mr_i)，则对每个 j 有贡献的 i 一定在二维平面上的一个矩形内！因此对于一个 j，所有 i 的贡献之和同样可以通过扫描线计算出。而由于最大值位于 (j, mid] 上，因此一个 j 对应的 k（也就是对 a 修改的位置）也是唯一的，因此直接将这个 j 的贡献累加到对应 k 上的答案即可！

最大值属于 [mid+1, i] 区间的情况是完全对称的，这里不再赘述。

那么这道题就做完了，由于外层分治带一个 \log，内层二维数点也带一个 \log，因此总复杂度为 O(n \log^2 n)。

#include<bits/stdc++.h>
#define endl '\n'
#define N 400006
#define MOD 998244353
using namespace std;
inline void add(int &x,int y) {x+=y,x-=x>=MOD?MOD:0;}
inline void dec(int &x,int y) {x+=MOD-y,x-=x>=MOD?MOD:0;}
// mx_l[j+1] + j <= i
// i - j >= mx_r[i]
// j <= i - mx_r[i]
int n,a[N],f[N],g[N],mx_l[N],mxpos[N],mx2_l[N],mx_r[N],mx2_r[N],ans[N];
int bn,b[N];
vector<int> vec[N];
struct BIT {
  int tree[N];
  void upd(int k,int x) {for(;k<=n+1;k+=k&-k)add(tree[k],x);}
  int query(int k)
  {
    int ret=0;
    for(;k;k-=k&-k)add(ret,tree[k]);
    return ret;
  }
  int query(int l,int r)
  {
    if(l>r||l>n+1||r<1)return 0;
    l=max(1,l),r=min(n+1,r);
    return (query(r)-query(l-1)+MOD)%MOD;
  }
} T;
void cdq1(int l,int r,int *dp)
{
  if(l==r)return;
  int mid=l+r>>1;
  cdq1(l,mid,dp);
  bn=0,mx_l[mid+1]=mx_r[mid]=-2e9;
  for(int i=mid;i>=l;i--)mx_l[i]=max(mx_l[i+1],a[i]);
  for(int i=mid+1;i<=r;i++)mx_r[i]=max(mx_r[i-1],a[i]);
  for(int j=l;j<=mid;j++)b[++bn]=j+mx_l[j+1];
  for(int i=mid+1;i<=r;i++)b[++bn]=i;
  sort(b+1,b+1+bn),bn=unique(b+1,b+1+bn)-b-1;
  for(int i=1;i<=bn;i++)vec[i].clear();
  for(int j=l;j<=mid;j++)
  {
    int id=lower_bound(b+1,b+1+bn,j+mx_l[j+1])-b;
    vec[id].push_back(j);
  }
  vector<pair<int,int> > change;
  for(int x=1;x<=bn;x++)
  {
    for(int j:vec[x])
      T.upd(j+1,dp[j]),change.push_back({j,dp[j]});
    if(b[x]>mid&&b[x]<=r)
    {
      int i=b[x];
      if(i-mx_r[i]>=0)add(dp[i],T.query(i-mx_r[i]+1));
    }
  }
  for(auto [x,y]:change)T.upd(x+1,(MOD-y)%MOD);
  cdq1(mid+1,r,dp);
}
void cdq2(int l,int r)
{
  if(l==r)return;
  int mid=l+r>>1;
  cdq2(l,mid);
  bn=0,mx_l[mid+1]=mx2_l[mid+1]=-2e9,
  mx_r[mid]=mx2_r[mid]=-2e9;
  for(int j=mid;j>=l;j--)
  {
    mxpos[j]=mxpos[j+1];
    mx_l[j]=mx_l[j+1],mx2_l[j]=mx2_l[j+1];
    if(a[j]>=mx_l[j])mx2_l[j]=mx_l[j],mx_l[j]=a[j],mxpos[j]=j;
    else if(a[j]>mx2_l[j])mx2_l[j]=a[j];
  }
  for(int i=mid+1;i<=r;i++)
  {
    mxpos[i]=mxpos[i-1];
    mx_r[i]=mx_r[i-1],mx2_r[i]=mx2_r[i-1];
    if(a[i]>=mx_r[i])mx2_r[i]=mx_r[i],mx_r[i]=a[i],mxpos[i]=i;
    else if(a[i]>mx2_r[i])mx2_r[i]=a[i];
  }

  for(int i=mid+1;i<=r;i++)b[++bn]=i-mx_r[i];
  for(int j=l;j<=mid;j++)b[++bn]=j;
  sort(b+1,b+1+bn),bn=unique(b+1,b+1+bn)-b-1;
  for(int i=1;i<=bn;i++)vec[i].clear();
  for(int i=mid+1;i<=r;i++)
  {
    int id=lower_bound(b+1,b+1+bn,i-mx_r[i])-b;
    vec[id].push_back(i);
  }
  vector<pair<int,int> > change;
  for(int x=bn;x;x--)
  {
    for(int i:vec[x])
      T.upd(i+1,g[i+1]),change.push_back({i,g[i+1]});
    if(b[x]>=l&&b[x]<=mid)
    {
      int j=b[x],val=T.query(j+mx2_l[j+1]+1,j+mx_l[j+1]);
      if(val)add(ans[mxpos[j+1]],1ll*f[j]*val%MOD);
    }
  }
  for(auto [x,y]:change)T.upd(x+1,(MOD-y)%MOD);
  change.clear(),bn=0;
  for(int j=l;j<=mid;j++)b[++bn]=j+mx_l[j+1];
  for(int i=mid+1;i<=r;i++)b[++bn]=i;
  sort(b+1,b+1+bn),bn=unique(b+1,b+1+bn)-b-1;
  for(int i=1;i<=bn;i++)vec[i].clear();
  for(int j=l;j<=mid;j++)
  {
    int id=lower_bound(b+1,b+1+bn,j+mx_l[j+1])-b;
    vec[id].push_back(j);
  }
  for(int x=1;x<=bn;x++)
  {
    for(int j:vec[x])
      T.upd(j+1,f[j]),change.push_back({j,f[j]});
    if(b[x]>mid&&b[x]<=r)
    {
      int i=b[x],val=T.query(i-mx_r[i]+2,i-mx2_r[i]+1);
      if(val)add(ans[mxpos[i]],1ll*g[i+1]*val%MOD);
    }
  }
  for(auto [x,y]:change)T.upd(x+1,(MOD-y)%MOD);
  cdq2(mid+1,r);
}
main()
{
  scanf("%d",&n);
  for(int i=1;i<=n;i++)scanf("%d",&a[i]);
  f[0]=1,cdq1(0,n,f),reverse(a+1,a+1+n);
  g[0]=1,cdq1(0,n,g),reverse(a+1,a+1+n);
  reverse(g,g+2+n);
  for(int i=1;i<=n;i++)ans[i]=f[n];
  cdq2(0,n);
  for(int i=1;i<=n;i++)
    printf("%d%c",ans[i]," \n"[i==n]);
  return 0;
}