zhangxyhp

摘要： 考慮如果沒有修改，用 ST 表就非常舒服。 考慮暴力修改，需要修改所有覆蓋了這個位置的區間，時間復雜度是 \(O(n)\) 的。 而如果只修改 \(\frac{\log n}{2}\) 層，時間復雜度就是 \(O(\sqrt{n})\) 的。查詢時從上往下查，最多查到第 \(\frac{\log n 閱讀全文

摘要： A. Tree Master 考慮根號分治，暴力處理。對于一層，設點數為 \(cnt\)。 若 \(cnt>\sqrt{n}\)，這樣的層最多有 \(\sqrt{n}\) 層，每一層最多計算 \(q\) 次，時間復雜度為 \(O(q\sqrt{n})\)。 否則 \(cnt\le\sqrt{n}\) 閱讀全文