結果
| 問題 | No.3812 Max Min Sigma Problem |
| コンテスト | |
| ユーザー |
|
| 提出日時 | 2026-11-20 23:06:32 |
| 言語 | C++17 (gcc 15.3.0 + boost 1.92.0 + ACL) |
| 結果 |
AC
不安定
|
| 実行時間 | 1,276 ms / 2,000 ms |
| + 644µs | |
| コード長 | 9,799 bytes |
| 記録 | |
| コンパイル時間 | 1,807 ms |
| コンパイル使用メモリ | 235,672 KB |
| 実行使用メモリ | 35,392 KB |
| 最終ジャッジ日時 | 2026-11-20 23:06:47 |
| 合計ジャッジ時間 | 10,176 ms |
|
ジャッジサーバーID (参考情報) |
judge1_0 / judge5_0 |
(要ログイン)
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 28 |
ソースコード
#include <bits/stdc++.h>
#include <cassert>
using namespace std;
//入力が必ず-mod<=a<modの時.
template<const int mod> //mod<2^30.
struct modint{ //mod変更が不可能.
public:
long long v;
static void setmod(int m){} //飾り.
static constexpr long long getmod(){return mod;}
modint():v(0){}
template<typename T>
modint(T a):v(a){if(v < 0) v += mod;}
long long val()const{return v;}
modint &operator=(const modint &b) = default;
modint &operator+()const{return (*this);}
modint operator-()const{return modint(0)-(*this);}
modint operator+(const modint b)const{return modint(v)+=b;}
modint operator-(const modint b)const{return modint(v)-=b;}
modint operator*(const modint b)const{return modint(v)*=b;}
modint operator/(const modint b)const{return modint(v)/=b;}
modint &operator+=(const modint b){
v += b.v; if(v >= mod) v -= mod;
return *this;
}
modint &operator-=(const modint b){
v -= b.v; if(v < 0) v += mod;
return *this;
}
modint &operator*=(const modint b){v = v*b.v%mod; return *this;}
modint &operator/=(modint b){ //b!=0 mod素数が必須.
assert(b.v != 0);
(*this) *= b.pow(mod-2);
return *this;
}
modint pow(long long n)const{
modint ret = 1,p = v;
if(n < 0) p = p.inv(),n = -n;
while(n){
if(n&1) ret *= p;
p *= p; n >>= 1;
}
return ret;
}
modint inv()const{return pow(mod-2);} //素数mod必須.
modint &operator++(){*this += 1; return *this;}
modint &operator--(){*this -= 1; return *this;}
modint operator++(int){modint ret = *this; *this += 1; return ret;}
modint operator--(int){modint ret = *this; *this -= 1; return ret;}
friend bool operator==(const modint a,const modint b){return a.v==b.v;}
friend bool operator!=(const modint a,const modint b){return a.v!=b.v;}
friend bool operator<(const modint a,const modint b){return a.v<b.v;}
friend bool operator<=(const modint a,const modint b){return a.v<=b.v;}
friend bool operator>=(const modint a,const modint b){return a.v>=b.v;}
friend bool operator>(const modint a,const modint b){return a.v>b.v;}
friend ostream &operator<<(ostream &os,const modint a){return os<<a.v;}
friend istream &operator>>(istream &is,modint &a){ //入力はmodをとってくれる.
long long x; is >> x; x %= mod;
a = modint(x); return is;
}
};
using mint = modint<998244353>; const long long mod = 998244353;
struct SS{
mint len,x2,x1;
};
using FF = mint;
class LazySegmentTree{
//ACL超参考にしてる というかパクリ.
//verify十分だけど注意.
private:
vector<SS> dat;
vector<FF> lazy;
public:
int siz = -1,n = -1,log = 0;
SS op(SS a,SS b){return {a.len+b.len,a.x2+b.x2,a.x1+b.x1};}
SS mapping(FF f, SS x){
if(f == 0) return x;
return {x.len,x.x2 + x.x1*f*2 + x.len*f*f,x.x1 + x.len*f};
}
FF composition(FF f, FF g){return f+g;}
SS e(){return {0,0,0};}
FF id(){return 0;}
//op区間演算 mapping lazy→data composition lazy→lazy
//e 単位元 id map(id,a)=a
LazySegmentTree(int N){init(N);}
LazySegmentTree(const vector<SS> &A){//配列サイズに合わせる.
siz = 1; n = A.size(); log = 0;
while(siz < n) siz <<= 1,log++;
dat.resize(siz*2,e());
lazy.resize(siz,id());
for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
for(int i=siz-1; i>0; i--) merge(i);
}
void init(int N){ //単位元になる.
siz = 1; n = N; log = 0;
while(siz < n) siz *= 2,log++;
dat.assign(siz*2,e());
lazy.assign(siz,id());
}
void init(const vector<SS> &A){ //配列サイズに合わせる.
siz = 1; n = A.size(); log = 0;
while(siz < n) siz <<= 1,log++;
dat.resize(siz*2,e());
lazy.assign(siz,id());
for(int i=0; i<n; i++) dat.at(i+siz) = A.at(i);
for(int i=siz-1; i>0; i--) merge(i);
}
private:
void eval(int u,FF f){
//u番目にfを適用したあと保留.
if(u == 0) return;
dat.at(u) = mapping(f,dat.at(u));
if(u < siz) lazy.at(u) = composition(f,lazy.at(u));
}
void spread(int u){ //uにあるFF保留を伝播.
if(u == 0 || id() == lazy.at(u)) return;
eval(2*u,lazy.at(u));
eval(2*u+1,lazy.at(u));
lazy.at(u) = id();
}
void merge(int u){dat.at(u) = op(dat.at(u*2),dat.at(u*2+1));} //子2つからマージ.
public:
void set(int pos,SS x){ //1点変更.
assert(0 <= pos && pos < n);
pos += siz;
for(int i=log; i>0; i--) spread(pos>>i);
dat.at(pos) = x;
while(pos > 1) pos >>= 1,merge(pos);
}
void update(int pos,FF f){ //1点更新 変数抜かして区間更新になってないか注意!.
assert(0 <= pos && pos < n);
pos += siz;
for(int i=log; i>0; i--) spread(pos>>i);
dat.at(pos) = mapping(f,dat.at(pos));
while(pos > 1) pos >>= 1,merge(pos);
}
void update(int l,int r,FF f){ //区間更新.
assert(0 <= l && l <= r && r <= n);
if(l == r) return;
l += siz; r += siz;
for(int i=log; i>0; i--){
if(((l>>i)<<i) != l) spread(l>>i);
if(((r>>i)<<i) != r) spread((r-1)>>i);
}
int memoL = l,memoR = r;
while(l < r){
if(l&1) eval(l++,f);
if(r&1) eval(--r,f);
l >>= 1; r >>= 1;
}
l = memoL,r = memoR;
while((l&1) == 0) l >>= 1;
while((r&1) == 0) r >>= 1;
r--; //-1注意.
while(l > 1) l >>= 1,merge(l);
while(r > 1) r >>= 1,merge(r);
}
SS get(int pos){ //1点取得.
assert(0 <= pos && pos < n);
pos += siz;
for(int i=log; i>0; i--) spread(pos>>i);
return dat.at(pos);
}
SS rangeans(int l,int r){ //区間取得.
assert(0 <= l && l <= r && r <= n);
if(l == r) return e();
l += siz; r += siz;
for(int i=log; i>0; i--){
if(((l>>i)<<i) != l) spread(l>>i);
if(((r>>i)<<i) != r) spread((r-1)>>i);
}
SS retl = e(),retr = e();
while(l < r){
if(l&1) retl = op(retl,dat.at(l++));
if(r&1) retr = op(dat.at(--r),retr);
l >>= 1; r >>= 1;
}
return op(retl,retr);
}
SS allrange(){return dat.at(1);} //全体取得.
int maxright(const function<bool(SS)> f,int l = 0){
assert(0 <= l && l <= n && f(e()));
if(l == n) return n;
l += siz;
for(int i=log; i>0; i--) spread(l>>i);
SS now = e();
do{
while(l%2 == 0) l >>= 1;
SS next = op(now,dat.at(l));
if(f(next) == false){
while(l < siz){
spread(l); l <<= 1;
next = op(now,dat.at(l));
if(f(next)) now = next,l++;
}
return l-siz;
}
now = next; l++;
}while((l&-l) != l);
return n;
}
int minleft(const function<bool(SS)> f,int r = -1){
if(r == -1) r = n;
assert(0 <= r && r <= n && f(e()));
if(r == 0) return 0;
r += siz;
for(int i=log; i>0; i--) spread((r-1)>>i);
SS now = e();
do{
r--;
while(r&1) r >>= 1;
if(r == 0) r = 1;
SS next = op(dat.at(r),now);
if(f(next) == false){
while(r < siz){
spread(r);
r <<= 1; r++;
next = op(dat.at(r),now);
if(f(next)) now = next,r--;
}
return r+1-siz;
}
now = next;
}while((r&-r) != r);
return 0;
}
};
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int N; cin >> N;
vector<int> A(N);
for(auto &a : A) cin >> a;
mint answer = 0;
vector<int> X(N),Y(N);
auto f = [&](auto f,int l,int r) -> void {
if(l+1 == r) return;
int m = (l+r)/2;
f(f,l,m),f(f,m,r);
vector<SS> give(r-m);
{
int big = 0,small = 1001001001;
for(int i=m; i<r; i++){
big = max(big,A.at(i)),small = min(small,A.at(i));
X.at(i) = big,Y.at(i) = small;
mint v = (big-small)%mod;
give.at(i-m) = {1,v*v,v};
}
}
LazySegmentTree Z(give);
stack<tuple<int,int,int>> B,S;
for(int i=r-1; i>=m; i--) B.push({i,i+1,X.at(i)}),S.push({i,i+1,Y.at(i)});
for(int i=m-1,big=0,small=1001001001; i>=l; i--){
big = max(big,A.at(i)),small = min(small,A.at(i));
{
int L = m,R = m;
while(B.size()){
auto [L2,R2,v] = B.top();
if(big >= v){
if(big-v) Z.update(L2-m,R2-m,big-v);
B.pop(),R = R2;
}
else break;
}
if(L != R) B.push({L,R,big});
}
{
int L = m,R = m;
while(S.size()){
auto [L2,R2,v] = S.top();
if(small <= v){
if(v-small) Z.update(L2-m,R2-m,v-small);
S.pop(),R = R2;
}
else break;
}
if(L != R) S.push({L,R,small});
}
answer += Z.allrange().x2;
}
};
f(f,0,N);
cout << answer << endl;
}