考虑先求出原序列的方案数
设 \(f_i\) 表示 \(1 \sim i\) 被划分为若干区间的方案数,若一段区间合法当且仅当 \(r-l+1 \ge \max \{a_{l \sim r}\}\),可以发现数据结构难以维护且由于不是最优性问题,考虑 \(\texttt{cdq}\) 分治优化
对于每个分治中心 \(m\),令 \(mxL_i=\max \{a_{i \sim m} \}\),\(mxR=\max \{a_{m+1 \sim i} \}\),那么跨过分治中心的合法区间有 \(r-l+1 \ge \max(mxL_l,mxR_r)\),化简未知量分开有 \(r \ge l + mxL_l -1\),\(l \le r - mxR_r+1\),此时转化为二维偏序,记后者为 \(b_i\),那么把 \([l,m]\) 按照 \(b_i\) 从小到大排序后,使用指针与 BIT
分别维护即可
考虑增加修改,可以发现修改相当于使 \(i\) 没有限制,那么可以求出增量,记 \(g_i\) 为 \(i \sim n\) 的方案数,同样是区间计数,考虑普通分治结构
先考虑 \(p \in [l,m]\) 的增量(\(p\in (m,r]\) 请读者自行思考),若现在左端点枚举到 \(i\),此时 \(p\) 为最大值,由于 \(p\) 没了限制,可以多加维护一个次大值,然后利用最大值和次大值差分求出增量,即减去 \(r \ge l+mx1-1\) 的方案数,加上 \(r \ge l +mx2-1\) 的方案数,然后扫 \((m,r]\) 的时候利用指针维护第一维限制(代码是 vector
维护的,参考了下前最短解),BIT
维护第二维即可
#include<bits/stdc++.h>
using namespace std;
#define mid ((l+r)/2)
struct node{
int x,d,v;
node(int x=0,int d=0,int v=0):x(x),d(d),v(v){}
};
int n,a[200001],b[200001],p[200001];
long long f[210001],g[210001],ans[200001];
vector <node> G[200001];
const int mod=998244353;
struct tree{
long long n,t[200001];
void init(int m){n=m;for(int i=1;i<=n;i++)t[i]=0;}
void add(int x,int v){for(int i=x;i<=n;i+=i&-i)(t[i]+=v)%=mod;}
long long ask(int x){long long s=0;for(int i=x;i>=1;i-=i&-i)(s+=t[i])%=mod;return s;}
}t;
bool cmp(int x,int y){return b[x]<b[y];}
void cdq(long long *dp,int l,int r){//cdq优化dp
if(l==r){
if(a[l]==1) (dp[l]+=dp[l-1])%=mod;
return;
}
cdq(dp,l,mid),t.init(mid-l+1);
for(int i=mid,mx=0;i>=l;i--) mx=max(mx,a[i]),b[i]=i+mx-1,p[i]=i;
for(int i=mid+1,mx=0;i<=r;i++) mx=max(mx,a[i]),b[i]=i-mx+1;
sort(p+l,p+mid+1,cmp);
for(int i=mid+1,j=l;i<=r;i++){
while(j<=mid&&i>=b[p[j]]) t.add(p[j]-l+1,dp[p[j]-1]),j++;
(dp[i]+=t.ask(min(b[i],mid)-l+1))%=mod;
}
cdq(dp,mid+1,r);
}
void solve(int l,int r){
if(l==r){
if(a[l]!=1) (ans[l]+=f[l-1]*g[l+1])%=mod;
return;
}
solve(l,mid),solve(mid+1,r);
for(int i=mid,mx=0;i>=l;i--) mx=max(mx,a[i]),b[i]=i+mx-1;
for(int i=mid+1,mx=0;i<=r;i++) mx=max(mx,a[i]),b[i]=i-mx+1;
t.init(mid-l+1);
for(int i=mid+1;i<=r;i++) G[i].clear();
for(int i=mid,mx1=0,mx2=0,p=0;i>=l;i--){//处理 [l,mid] 的增量
if(a[i]>mx1) mx2=mx1,mx1=a[i],p=i;
else if(a[i]>mx2) mx2=a[i];
if(i+mx1-1<=r) G[max(mid+1,i+mx1-1)].push_back(node(i,p,mod-f[i-1]));//维护 r>=l+mxL[l]-1
if(i+mx2-1<=r) G[max(mid+1,i+mx2-1)].push_back(node(i,p,f[i-1]));
}
for(int i=r;i>mid;i--){
if(b[i]>=l) t.add(min(b[i],mid)-l+1,g[i+1]);//维护 l<=r-mxR[r]+1
for(auto j:G[i]) (ans[j.d]+=j.v*(t.ask(mid-l+1)-t.ask(j.x-l)+mod))%=mod;
}
t.init(r-mid);
for(int i=l;i<=mid;i++) G[i].clear();
for(int i=mid+1,mx1=0,mx2=0,p=0;i<=r;i++){//处理 (mid,r] 的增量
if(a[i]>mx1) mx2=mx1,mx1=a[i],p=i;
else if(a[i]>mx2) mx2=a[i];
if(i-mx1+1>=l) G[min(i-mx1+1,mid)].push_back(node(i,p,mod-g[i+1]));//维护 l<=r-mxR[r]+1
if(i-mx2+1>=l) G[min(i-mx2+1,mid)].push_back(node(i,p,g[i+1]));
}
for(int i=l;i<=mid;i++){
if(b[i]<=r) t.add(max(mid+1,b[i])-mid,f[i-1]);//维护 r>=l+mxL[l]-1
for(auto j:G[i]) (ans[j.d]+=j.v*t.ask(j.x-mid))%=mod;
}
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
f[0]=g[0]=1,cdq(f,1,n),reverse(a+1,a+1+n),cdq(g,1,n),reverse(a+1,a+1+n),reverse(g,g+2+n),solve(1,n);
for(int i=1;i<=n;i++) printf("%lld ",(f[n]+ans[i])%mod);
return 0;
}
标签:200001,int,mx2,Say,mid,QOJ7899,Future,mx1,mx
From: https://www.cnblogs.com/zyxawa/p/18328054