E - LEQ and NEQ Editorial
by
sounansya
公式解説と同様に包除原理を適用することを考えます。
\(d[i]\) を \(i\) 項目までを考えた場合の答え \((0\le i\le N)\) とします。求める値は \(d[N]\) です。このように定義すると、\(\displaystyle d[i]=\sum_{j < i} (-1)^{i-j+1}d[j] \min_{j < k\le i} A_k\) が成り立ちます。
\(\displaystyle d'[i]=(-1)^i d[i]\) とすることで、遷移は \(\displaystyle d'[i]=-\sum_{j < i} d'[j] \min_{j < k\le i} A_k\) となります。各 \(j\) に対する \(\displaystyle \min_{j < k\le i} A_k\) は広義単調増加になることから、この遷移は Lazy Segment Tree を用いることで高速に計算することができます(モノイドとしては \(A,d',A\times d'\) の総和と区間長を持てば良く、\(\displaystyle \min A\) の更新もセグメント木上の二分探索や単調スタックを用いれば良いです)。計算量は \(O(N \log N)\) です。
