Face The Right Way
Solution sketch
對於所有的 $K$ 進行 枚舉 和 模擬反轉操作 的話,會是 $O(n^3)$ 所以會 TLE。
其實,一個點反轉兩次等於沒反轉。因此一個點有無被反轉,只需要看他前 $k - 1$ 的區間內反轉次數是奇數還數偶數就好。
因此,我們只要維護區間反轉次數,就可以壓到 $O(n^2)$ 了!
AC code
|
|
Never give up!
對於所有的 $K$ 進行 枚舉 和 模擬反轉操作 的話,會是 $O(n^3)$ 所以會 TLE。
其實,一個點反轉兩次等於沒反轉。因此一個點有無被反轉,只需要看他前 $k - 1$ 的區間內反轉次數是奇數還數偶數就好。
因此,我們只要維護區間反轉次數,就可以壓到 $O(n^2)$ 了!
|
|