uva-1608-Non-boring sequences

出處 ： https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=4483

參考網頁：http://morris821028.github.io/2014/05/01/oj/uva/uva-1608/

解題策略，此方法會逾時，TLE

利用map找出每個元素最近的相同元素的左邊索引值到L[]，找出每個元素最近的相同元素的右邊索引值到R[]，用於在O(1)時間內判斷是否是在指定範圍內出現一次的元素，從中間往兩邊找，中間就找到演算法為O(n*log(n))，兩邊才找到為O(n*n)會逾時，因為T(n)=T(n-1)+O(n)

解題策略

利用map找出每個元素最近的相同元素的左邊索引值到L[]，找出每個元素最近的相同元素的右邊索引值到R[]，用於在O(1)時間內判斷是否在指定範圍內出現一次的元素，從左邊與右邊往中間找，第一個就找到演算法為O(n)，中間才找到為O(n*log(n))