QOJ7899 Say Hello to the Future

考虑先求出原序列的方案数

设 \(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;
}