區間[1,n]內有n個數字。現在按順序進行n次操作，操作有以下兩種:
1.給你三個整數L,R,K。把[L,R]的數字都修改成k
2.給你兩個整數L,R。詢問[L,R]的數字之和
對於所有的L,R,K,有
1<=L<=R<=n
k為整數，且絕對值小於10的9次方
訪問或修改一個數字需要消耗1個單位的時間
現在要求設計一種效率儘可能高的演算法來正確回答所有的操作2。
效率高的演算法要求隨著n規模增長，所花時間T的增長儘可能慢。
如T與n^2成正比的演算法，效率就要低於T與n成正比的演算法。
那麼最優情況下，T與下列哪個選項成正比？
提示:可以使用額外的空間來記錄信息。
