专栏文章

CF2144E题解

FForgive_Me
CF2144E2题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@minv3e49
此快照首次捕获于
2025/12/02 08:50
3 个月前
此快照最后确认于
2025/12/02 08:50
3 个月前
查看原文

CF2144E1&E2

E1
首先可以单调栈预处理出来 L,RL,R。
发现这两部分实际上最多交一个最大值。
然后就可以分别做。以 LL 为例。
fi,jf_{i,j} 表示前 ii 个凑出了 LL 的前 jj 个的答案。
fi,j={fi−1,j−1+2×fi−1,jif ai=lj2×fi−1,jelse if ai<ljfi−1,jelsef_{i,j} = \begin{cases} f_{i-1,j-1}+2\times f_{i-1,j} & if\ a_{i}=l_{j}\\ 2\times f_{i-1,j} & else\ if\ a_{i}<l_{j}\\ f_{i-1,j} & else \end{cases}
但是好像会算重啊！赛时卡在这里。
发现我们只需要钦定一个为后半段提供最大值的位置就可以了，答案就对于每一个等于最大值的位置求和，top2,top1 分别表示 L,RL,R 的 size：
ans=∑ai=ltop2(fi−1,top2+fi−1,top2−1)×gi+1,top1−1ans=\sum_{a_{i} = l_{top2}}(f_{i-1,top2}+f_{i-1,top2-1}) \times g_{i+1,top1-1}。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=998244353,N=5010;
int l[N],r[N],a[N],f[N][N],g[N][N];
void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int top1=0,top2=0;
	for(int i=1;i<=n;i++){
		while(top1&&a[i]>=r[top1]) top1--;
		r[++top1]=a[i];
	}
	for(int i=n;i>=1;i--){
		while(top2&&a[i]>=l[top2]) top2--;
		l[++top2]=a[i];
	}
	reverse(l+1,l+top2+1);reverse(r+1,r+top1+1);
	for(int i=0;i<=n+1;i++)
		for(int j=0;j<=n+1;j++) f[i][j]=g[i][j]=0;
	f[0][0]=1,g[n+1][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<=top2;j++){
			if(a[i]==l[j]&&j){
				f[i][j]+=f[i-1][j-1]+f[i-1][j]*2;
				f[i][j]%=p;
				continue ;
			}
			if(j&&a[i]<=l[j]) f[i][j]+=f[i-1][j]*2; 
			else f[i][j]+=f[i-1][j];
			f[i][j]%=p;
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=0;j<=top1;j++){
			if(a[i]==r[j]&&j){
				g[i][j]+=g[i+1][j-1]+g[i+1][j]*2;
				g[i][j]%=p;
				continue;
			}
			if(j&&a[i]<=r[j]) g[i][j]+=g[i+1][j]*2; 
			else g[i][j]+=g[i+1][j];
			g[i][j]%=p;
		}
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]==l[top2]){
			ans+=(f[i-1][top2]+f[i-1][top2-1])*g[i+1][top1-1]%p;
			ans%=p;
		}
	}
	cout<<ans<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
}
E2
发现答案里第二维只有两个值，并且转移里面第一维都是和前一个转移，涉及到的第二维量也最多只有 top 和 top-1。
由于 LL 是单调的并且 aia_{i} 的贡献是一个区间即 ai≤lja_{i}\le l_{j}，想到线段树优化。
发现你需要一个单点加，区间乘和单点查询。每次找贡献区间的时候 lower_bound 即可。
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p1=998244353,N=300010;
int l[N],r[N],a[N],f[N],g[N];
struct node{
	int l,r,data,lazy;
}p[4*N];
void build(int pos,int l,int r){
	p[pos].l=l,p[pos].r=r,p[pos].lazy=1,p[pos].data=0;
	if(l==r) return ;
	int mid=(l+r)/2;
	build(pos*2,l,mid);build(pos*2+1,mid+1,r);
}
void pushup(int pos){
	p[pos].data=p[pos*2].data+p[pos*2+1].data;
	p[pos].data%=p1;
}
void pushdown(int pos){
	if(p[pos].lazy==1) return ;
	int v=p[pos].lazy;
	p[pos].lazy=1;
	p[pos*2].data*=v;p[pos*2+1].data*=v;p[pos*2].lazy*=v,p[pos*2+1].lazy*=v;
	p[pos*2].data%=p1;p[pos*2+1].data%=p1;p[pos*2].lazy%=p1,p[pos*2+1].lazy%=p1;
}
void update(int pos,int l,int r){
	if(p[pos].l==l&&p[pos].r==r){
		p[pos].data*=2;
		p[pos].lazy*=2;
		p[pos].data%=p1,p[pos].lazy%=p1;
		return ;
	} 
	pushdown(pos);
	int mid=(p[pos].l+p[pos].r)/2;
	if(l<=mid) update(pos*2,l,min(r,mid));
	if(r>mid) update(pos*2+1,max(mid+1,l),r);
	pushup(pos);
}
void add(int pos,int x,int v){
	if(p[pos].l==p[pos].r){
		p[pos].data+=v;
		p[pos].data%=p1;
		return ;
	}
	pushdown(pos);
	int mid=(p[pos].l+p[pos].r)/2;
	if(x<=mid) add(pos*2,x,v);
	else add(pos*2+1,x,v);
	pushup(pos);
}
int get(int pos,int x){
	if(p[pos].l==p[pos].r) return p[pos].data;
	pushdown(pos);
	int mid=(p[pos].l+p[pos].r)/2;
	if(x<=mid) return get(pos*2,x);
	else return get(pos*2+1,x);
	pushup(pos);
}
void solve(){
	int n;cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	int top1=0,top2=0;
	for(int i=1;i<=n;i++){
		while(top1&&a[i]>=r[top1]) top1--;
		r[++top1]=a[i];
	}
	for(int i=n;i>=1;i--){
		while(top2&&a[i]>=l[top2]) top2--;
		l[++top2]=a[i];
	}
	reverse(l+1,l+top2+1);reverse(r+1,r+top1+1);
	for(int i=0;i<=n+1;i++) f[i]=g[i]=0;
	build(1,0,top2);
	add(1,0,1);
	if(top2==1) f[0]=1;
	for(int i=1;i<=n;i++){
		int x=lower_bound(l+1,l+top2+1,a[i])-l,now;
		if(a[i]==l[x]) now=get(1,x-1);
		update(1,x,top2);
		if(a[i]==l[x]) add(1,x,now);
		f[i]=(get(1,top2)+get(1,top2-1))%p1;
	}
	build(1,0,top1);
	add(1,0,1);
	if(top1==1) g[n+1]=1;
	for(int i=n;i>=1;i--){
		int x=lower_bound(r+1,r+top1+1,a[i])-r,now;
		if(a[i]==r[x]) now=get(1,x-1);
		update(1,x,top1);
		if(a[i]==r[x]) add(1,x,now);
		g[i]=get(1,top1-1);
	}
	int ans=0;
	for(int i=1;i<=n;i++){
		if(a[i]==l[top2]){
			ans+=f[i-1]*g[i+1]%p1;
			ans%=p1;
		}
	}
	cout<<ans<<'\n';
}
signed main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int T;cin>>T;
	while(T--) solve();
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...