結果

問題 No.3812 Max Min Sigma Problem
コンテスト
ユーザー sepa38
提出日時 2026-11-18 15:42:27
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
WA  
実行時間 -
コード長 2,936 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 90 ms
コンパイル使用メモリ 64,508 KB
実行使用メモリ 176,132 KB
最終ジャッジ日時 2026-11-20 20:56:10
合計ジャッジ時間 15,231 ms
ジャッジサーバーID
(参考情報)
judge3_0 / judge2_0
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 2
other AC * 17 WA * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code

# 誤解法5: (X-Y)^2 = X^2 - 2XY + Y^2 と展開。
#   ΣX^2, ΣY^2 は「A_i が最大となる区間数」の寄与法、ΣXY は遅延セグ木で各 l の mx·mn の和を管理。
#   ただし寄与法の左右の境界を両側とも「真に大きい(小さい)値」で取っており、同値があると重複カウントする。
import sys
MOD = 998244353
def contrib(A, better):
    n = len(A); L = [0]*n; R = [0]*n; st = []
    for i in range(n):
        while st and not better(A[st[-1]], A[i]): st.pop()   # A[j] が真に勝つものだけ残す
        L[i] = st[-1] if st else -1; st.append(i)
    st = []
    for i in range(n-1, -1, -1):
        while st and not better(A[st[-1]], A[i]): st.pop()   # ←右側も同じ条件(バグ)
        R[i] = st[-1] if st else n; st.append(i)
    return sum(A[i]*A[i] % MOD * (i - L[i]) * (R[i] - i) for i in range(n)) % MOD
def main():
    d = sys.stdin.read().split()
    n = int(d[0]); A = list(map(int, d[1:1+n]))
    sx2 = contrib(A, lambda u, v: u > v)
    sy2 = contrib(A, lambda u, v: u < v)
    size = 1
    while size < n: size *= 2
    LOG = size.bit_length() - 1
    smx = [0]*(2*size); smn = [0]*(2*size); spr = [0]*(2*size); ln = [0]*(2*size)
    la = [0]*size; lb = [0]*size
    for i in range(size): ln[size+i] = 1
    for i in range(size-1, 0, -1): ln[i] = ln[2*i] + ln[2*i+1]
    def ap(k, a, b):
        spr[k] = (spr[k] + a*smn[k] + b*smx[k] + a*b % MOD * ln[k]) % MOD
        smx[k] = (smx[k] + a*ln[k]) % MOD
        smn[k] = (smn[k] + b*ln[k]) % MOD
        if k < size: la[k] = (la[k] + a) % MOD; lb[k] = (lb[k] + b) % MOD
    def push(k):
        if la[k] or lb[k]:
            ap(2*k, la[k], lb[k]); ap(2*k+1, la[k], lb[k]); la[k] = lb[k] = 0
    def pull(k):
        smx[k] = (smx[2*k] + smx[2*k+1]) % MOD
        smn[k] = (smn[2*k] + smn[2*k+1]) % MOD
        spr[k] = (spr[2*k] + spr[2*k+1]) % MOD
    def add(l, r, a, b):
        if l >= r: return
        l += size; r += size
        for i in range(LOG, 0, -1):
            if ((l >> i) << i) != l: push(l >> i)
            if ((r >> i) << i) != r: push((r-1) >> i)
        l2, r2 = l, r
        while l2 < r2:
            if l2 & 1: ap(l2, a, b); l2 += 1
            if r2 & 1: r2 -= 1; ap(r2, a, b)
            l2 >>= 1; r2 >>= 1
        for i in range(1, LOG+1):
            if ((l >> i) << i) != l: pull(l >> i)
            if ((r >> i) << i) != r: pull((r-1) >> i)
    smax = []; smin = []; sxy = 0
    for r in range(n):
        a = A[r]
        add(r, r+1, a, a)
        end = r-1; st = r
        while smax and smax[-1][0] <= a:
            v, s = smax.pop(); add(s, end+1, a - v, 0); end = s-1; st = s
        smax.append((a, st))
        end = r-1; st = r
        while smin and smin[-1][0] >= a:
            v, s = smin.pop(); add(s, end+1, 0, a - v); end = s-1; st = s
        smin.append((a, st))
        sxy = (sxy + spr[1]) % MOD
    print((sx2 + sy2 - 2*sxy) % MOD)
main()
0