JOI2020本選5 火事 解説

問題リンク

解説

時系列順に数列の様子を並べると，同じ数でできた三角形や平行四辺形の集合になるので，これを頑張ってセグ木で再現する．

平行四辺形に差し引きすると直角二等辺三角形と長方形にできるので，これらの加算ができればよい．

長方形の加算は普通のセグ木でできて，直角二等辺三角形は，斜めの加算と長方形の加算を組み合わせるとできる． 斜めの加算用のセグ木と長方形の加算用のセグ木を分けて，図のように加算すればいい．

制限時間が厳しめだが，まあ通る