Submission #49207240

---

Source Code Expand

// LUOGU_RID: 142472765
//Author: gsczl71
//Copyright (c) 2023 gsczl71 All rights reserved.

#include<bits/stdc++.h>
#define ll long long
#define i128 __int128
#define ull unsigned long long
#define pii pair<int,int>
#define pll pair<long long, long long>
#define fir first
#define se second
#define endl '\n'
#define debug puts("AK IOI")
#define re register
#define pb push_back
using namespace std;
#define int long long
//const int mod = 1e9+7;
const int mod = 998244353;
const int inf = 0x3f3f3f3f,N = 3e5+5,M = 2e5+5;
const ll linf = 0x3f3f3f3f3f3f3f3f;
int n,a[N],f,g,dp[N],mx[N],mn[N];
stack<int> stmx,stmn;
void solve(){
	cin>>n;for(int i=1;i<=n;i++)cin>>a[i];
	dp[0]=mx[0]=mn[0]=1;//因为要做乘法
	for(int i=1;i<=n;i++){
		//对max部分处理
		mx[i]=dp[i-1];//长度为1的贡献肯定是ai
		while(!stmx.empty()&&a[stmx.top()]<a[i]){//找比ai小的数
			int x=stmx.top();stmx.pop();
			mx[i]=(mx[i]+mx[x])%mod;//修改累积的和。
			f-=mx[x]*a[x]%mod;f=(f%mod+mod)%mod;
		}stmx.push(i);
		f=((f+mx[i]*a[i])%mod+mod)%mod;//(1)式
		//对min部分处理	（跟max同理）
		mn[i]=dp[i-1];
		while(!stmn.empty()&&a[stmn.top()]>a[i]){//找比ai小的数
			int x=stmn.top();stmn.pop();
			mn[i]=(mn[i]+mn[x])%mod;
			g-=mn[x]*a[x]%mod;g=(g%mod+mod)%mod;
		}stmn.push(i);
		g=((g+mn[i]*a[i])%mod+mod)%mod;//(2)式
		//合算答案。
		dp[i]=((f-g)%mod+mod)%mod;//(3)式
	}cout<<dp[n];
}
signed main(){
	ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
	int T=1;
//	cin >> T;
	while(T--) solve();
	return 0;
}

Submission Info

Judge Result