COCI 2010/2011 Contest 3

香港時間2200-0100..!
十分合適我的生理時鐘

Q1-Q4: 頹
Q5: 望下去很有趣, 直覺會想到
最後還是做到了, 方法大概是

計算的次序:
1: [1,1]
2: [1,2],[2,2]
3: [1,3],[2,3],[3,3]
4: [1,4],[2,4],[3,4],[4,4]
..

首先想到的是每一個range都儲著max和min
做到第i步時, 把a[i]和每一個range的max和min比較和update, 再把每一個range的(max-min)加落answer

但續個range計和update是O(N²), 所以運用了一個很trivial的fact:
(max[1]-min[1])+(max[2]-min[2])+...+(max[n]-min[n]) = (max[1]+max[2]+...+max[n])-(min[1]+min[2]+...+min[n])

即是, 每一步儲著兩條list: max list 和 min list
而這條list要support以下operation
1. Push(x) - change all elements smaller than x to x
2. Sum() - sum of all elements

然後就想到條list其實就是一條類似stack的東西, 而每一個entry儲著frequency和value, 其中value是increasing/decreasing的
每一次Push(x)就一直pop走大於x/小於x的entry, 並累計frequency, 最後push返落條list度, 途中maintain Sum
由於每一個entry只會入/出條stack一次, 所以整個算法為O(N)

Q6: 未想到, 暉好像想到, 其實這樣挺好的, 因為如果我們一隊的話便可以把所有題目solve了(想像)