# ARC098 C - Attention

なるほど、300 点問題には、こういう感じに、一直線に走査しつつ数えた結果を溜めていくタイプがある気がするな。
[ABC125 C - GCD on Blackboard](https://atcoder.jp/contests/abc125/tasks/abc125_c) とか。

各 i について、その人をリーダにしたときに向きをかえなきゃいけなくなるひとは、その人より右にいて E の人と、
その人より左にいて W の人。前者は右から、後者は左から順にみていけば、それぞれ \(O(N)\) で数えらえれるので、全体としても \(O(N)\) 。

$$<table>{ lcccccccc
\hline
入力例３の S & W & W & W & W & W & E & E & E \\
\hline
より右にいる E &  3  & 3 & 3 & 3 & 3 & 2 & 1 & 0 \\
\hline
より左にいる W & 0 & 1 & 2 & 3 & 4 & 4 & 4 & 4 \\
\hline
\hline
計 & 3 & 4 & 5 & 6 & 7 & 6 & 5 & 4 \\
\hline
$$}

というのを、ただ単に書いただけ： [提出 5397029](https://atcoder.jp/contests/arc098/submissions/5397029)

解説みたら、こゆのを「累積和」っていうのね。