1樓：RhmBWT
震驚：99%的人不知道莫隊的真正複雜度！
O( nsqrt( m ) )
分塊的複雜度則是O( nsqrt( n ) ) + O( nsqrt( m ) )
//我們假設你要預處理塊間的鬼玩意
其實n=1e5,m=1e6的題莫隊是可以隨便跑的參見Problem 4940. -- [Ynoi2016]這是我自己的發明
只不過要調分塊大小為n / sqrt( m )級別
2樓：library.hide(FR)
設轉移時間為 ，對 進行分塊。
塊大小為 。一塊內和兩塊間的 方向移動次數都是 ，共有 塊，所以 方向移動次數共為 。兩次查詢之間 方向移動次數為 ，共有 次查詢，所以 方向移動次數為 。總複雜度為 。
塊大小為 。一塊內和兩塊間的 方向移動次數都是 ，共有 塊，所以 方向移動次數共為 。兩次查詢之間 方向移動次數為 ，共有 次查詢，所以 方向移動次數為 。總複雜度為 。
修改於09-28，09-15可能是廢話寫太多了。
3樓：艾慶興
顯然最多有sqrt（m）個塊、對於塊內每個詢問來說、右端點每次變換最多sqrt（m）次，所有詢問一共n個，所以最多n*sqrt（m）次、左端點的話、因為最多sqrt（m）個塊，所以構造每個塊第乙個詢問的左端點最多每次走m步、共msqrt（m）次，由於n往往和m相等，所以莫隊複雜度是更號級別的，排序的log相比更號太小了所以忽略
STL庫里的演算法時間複雜度和空間複雜度都是最佳的嗎？
Alinshans 肯定不都是最佳的。但肯定比99 的人寫的都要好。競賽中不一定要求時間複雜度最小，但是基本上 嚴格一點的 要求達到乙個級別。比如複雜度能O nlogn 的你不要搞O n STL中的演算法肯定能確保你能達到，如果你的寫法沒有問題，但死活超時了 卡常數 我覺得題目出得有問題。另，你知道...
關於演算法時間複雜度，O n 到底有多大？
Joker 現在很多機器 膝上型電腦 大約每秒鐘能夠執行大約v 10 9條指令 這個數量級 O n 2 的演算法可以認為它有不超過c n 2條需要執行的指令。c是某個常數，可以很大，c通常的程式在1 10之間。秒數大約c n 2 v。你如果時間複雜度沒算錯，那麼大概是c很大，或者v很小。要麼是演算法...
資料結構中的時間複雜度和空間複雜度有沒有直接的關係？
1.在絕大多數情況下，演算法的時間複雜度不會低於空間複雜度 2.為什麼在一段時間內學習到的實現同樣目標演算法中，二者似乎矛盾對立？因為如果A演算法在時空上都優秀於B演算法，我覺得你不會去記B演算法就醬 不用很長各種各樣的論述，你記住幾點 其實只要記住最後一點就可以了 1，完成乙個既定目標的任意演算法...