本文主要是介绍AtCoder Regular Contest 115 E. LEQ and NEQ（容斥 单调栈优化dp），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目
n(n<=5e5)个数，第i个数ai(1<=ai<=1e9)
构造一个序列b，要求bi∈[1,ai]，且b[i]不等于b[i+1]
求方案数，答案对998244353取模
思路来源
洛谷题解Xu_brezza
一模一样的cf题：
Codeforces Round 759 (Div. 2, based on Technocup 2022 Elimination Round 3) F. Non-equal Neighbours
题解
首先肯定是容斥，假设出现了一对冲突的就叫有一个坏点，
那么，答案=没有冲突的-至少一个冲突的+至少两个冲突的...
出现了一个坏点，就认为是合并减少了一个数，
所以最后如果减少了k个数，就认为序列被拆成了n-k段，且每段内的数字相同
dp[i][j]表示前i个数被划分成了j段的方案数，
其中每段内的数字是相同的，也就是从[1,这一段的最小值]中取
1. 朴素转移即枚举最后一段在哪，补上这最后一段的贡献，对应了这一个区间的最小值
复杂度
2. 注意到，第二维对容斥系数的贡献，只有第二维的奇偶性，所以可以改写为
前缀和分别维护第二维为奇数/为偶数的和，
复杂度
3. 单调栈优化，注意到，如果找到了前面第一个小于ai的数是p，
那么，ai对前面的位置的数，也就是k<p的位置不再有贡献，
考虑k<p的位置的和，
所以有，
那么，一边维护单调栈一边维护前缀和即可，
特别地，如果不存在这样的p，说明ai是前缀最小，
观察原式后代入ai，有
前0个数分成偶数段方案数为1，分成奇数段方案数为0，对应dp[0][0]=1
最后，答案=至少出现偶数次冲突-
至少出现奇数次冲突方案
如果n为偶数，说明分成偶数段=出现偶数次冲突，答案是
否则，如果n为奇数，说明分成奇数段=出现偶数次冲突，答案是
复杂度
代码1
#include<iostream>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=5e5+10,mod=998244353;
int n,a[N],dp[N][2],sum[N][2],stk[N],c,ans;
// dp[i][j&1]+=dp[p][j&1]+sum dp[k][j&1^1]*a[i],p为小于ai的最大位置
void add(int &x,int y){x=(x+y)%mod;
}
int cal(int l,int r,int v){if(l==0)return sum[r][v];return (sum[r][v]-sum[l-1][v]+mod)%mod;
}
int main(){sci(n);dp[0][0]=sum[0][0]=1;rep(i,1,n){sci(a[i]);while(c && a[stk[c]]>=a[i]){c--;}rep(j,0,1){if(c)dp[i][j]=(dp[stk[c]][j]+1ll*cal(stk[c],i-1,j^1)*a[i]%mod)%mod;else dp[i][j]=1ll*cal(0,i-1,j^1)*a[i]%mod;sum[i][j]=(sum[i-1][j]+dp[i][j])%mod;}stk[++c]=i;//printf("i:%d dp:(%d,%d)\n",i,dp[i][0],dp[i][1]);}if(n&1)ans=(dp[n][1]-dp[n][0]+mod)%mod;else ans=(dp[n][0]-dp[n][1]+mod)%mod;printf("%d\n",ans);return 0;
}代码2
自己的乱搞，基于以下这个式子，构造单调栈优化
其中，dp[i]表示以i结尾的方案数，枚举最后一段合并了几个数，
假设最后一段x个数，说明冲突了x-1次，容斥系数是(-1)的x-1次方，加上对应的贡献即可
#include<iostream>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define pb push_back
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define scll(a) scanf("%lld",&(a))
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
const int N=5e5+10,mod=998244353;
//dp[i]+=dp[j]*min(a[j+1],...,a[i])*(-1)^(i-j-1),j<i
//dp[1]+=dp[0]*a[1]
//dp[2]+=dp[1]*a[2]
//dp[2]-=dp[0]*min(a[1],a[2])
int n,a[N],dp[N],sum[2],sum2[N],stk[N],mn[N],cp[N][2],c;
void add(int &x,int y){x=(x+y)%mod;
}
int main(){sci(n);rep(i,1,n){sci(a[i]);if(i==1)mn[i]=a[i];else mn[i]=min(mn[i-1],a[i]);}rep(i,0,n){while(c && a[stk[c]]>=a[i]){int p=stk[c],x=(p-1)&1;add(sum[x],mod-1ll*cp[p-1][0]*a[p]%mod);//jadd(sum2[x],cp[p-1][0]);//jadd(sum[x^1],mod-1ll*cp[p-1][1]*a[p]%mod);//jadd(sum2[x^1],cp[p-1][1]);//jc--;}//1 2 4 6 5 7//printf("i:%d sum:(%d,%d) sum2:(%d,%d)\n",i,sum[0],sum[1],sum2[0],sum2[1]);int v1=(sum[i&1^1]-sum[i&1]+mod)%mod;int v2=1ll*(sum2[i&1^1]-sum2[i&1]+mod)*a[i]%mod;dp[i]=(v1+v2)%mod;if(i&1)add(dp[i],mn[i]);//dp[0]的贡献else add(dp[i],mod-mn[i]);//printf("i:%d dp:%d\n",i,dp[i]);int x=(i-1)&1;stk[++c]=i;cp[i-1][0]=sum2[x];cp[i-1][1]=sum2[x^1];add(sum[x],1ll*cp[i-1][0]*a[i]%mod);add(sum[x^1],1ll*cp[i-1][1]*a[i]%mod);sum2[0]=sum2[1]=0;while(c && a[stk[c]]>=a[i+1]){int p=stk[c],x=(p-1)&1;add(sum[x],mod-1ll*cp[p-1][0]*a[p]%mod);//jadd(sum2[x],cp[p-1][0]);//jadd(sum[x^1],mod-1ll*cp[p-1][1]*a[p]%mod);//jadd(sum2[x^1],cp[p-1][1]);//jc--;}stk[++c]=i+1;x=i&1;cp[i][0]=(sum2[x]+dp[i])%mod;cp[i][1]=sum2[x^1];sum2[0]=sum2[1]=0;add(sum[x],1ll*cp[i][0]*a[i+1]%mod);add(sum[x^1],1ll*cp[i][1]*a[i+1]%mod);}printf("%d\n",dp[n]);return 0;
}这篇关于AtCoder Regular Contest 115 E. LEQ and NEQ（容斥 单调栈优化dp）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
