ProjectEuler 663 - Solutions

這題大家都說要用線段樹(segment tree)，可是我不會用啊！我當然知道線段樹，只是不知道要如何將線段樹用在這題？

觀察到要更動的項數很少，大約是2*10^5項，忽然想到區間查詢可以將 陣列分割成Sqrt(N)個區間來做。對於S(N,m)-S(N,n)有著(m-n)*N^0.5的複雜度。依題目的要求，大約是6.3*10^8的計算量。最後程式跑了15秒！1分鐘以內，算是達標了！第23名。就憑著這23名，讓我又回到歐拉人的前20名。175分，歐拉人第15名！！！