なるほど、300 点問題には、こういう感じに、一直線に走査しつつ数えた結果を溜めていくタイプがある気がするな。 ABC125 C - GCD on Blackboard とか。
各 i について、その人をリーダにしたときに向きをかえなきゃいけなくなるひとは、その人より右にいて E の人と、 その人より左にいて W の人。前者は右から、後者は左から順にみていけば、それぞれ \(O(N)\) で数えらえれるので、全体としても \(O(N)\) 。
| 入力例３の S | W | W | W | W | W | E | E | E |
| より右にいる E | 3 | 3 | 3 | 3 | 3 | 2 | 1 | 0 |
| より左にいる W | 0 | 1 | 2 | 3 | 4 | 4 | 4 | 4 |
| 計 | 3 | 4 | 5 | 6 | 7 | 6 | 5 | 4 |
というのを、ただ単に書いただけ： 提出 5397029
解説みたら、こゆのを「累積和」っていうのね。