CF2144E题解
Forgive_Me
·
·
题解
CF2144E1\&E2
E1
首先可以单调栈预处理出来 L,R。\
发现这两部分实际上最多交一个最大值。\
然后就可以分别做。以 L 为例。\
$$
f_{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,R$ 的 `size`：\
$ans=\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`。\
由于 $L$ 是单调的并且 $a_{i}$ 的贡献是一个区间即 $a_{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();
}
```