大地震 的题解
记住只在没有思路时使用题解,不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。
在解题之前提交题解的代码会导致封禁。
作者:
這題是很經典的區間問題,區間指的是序列中一段連續的部分,題目要我們維護一段很長的區間,並且執行很多次區間加值以及最後查詢的操作,子題 \(1\) 只要依據題目要求,使用暴力法,建立一為陣列代表目前每一段的高度,再利用 for 迴圈等方式按照每次區間加值(\(i\) 到 \(j\) 都加 \(k\))維護陣列裡每一個數,即可獲得子題 \(1\) 的 \(40\) 分。
但觀察子題 \(2\),我們發現數據的範圍實在太大了,用暴力的話時間複雜度會爆炸,所以我們需要使用其他更有效率的方式處理區間問題,可以參考使用線段樹、二叉索引樹(BIT)或前綴和與拆分等方式來實作。
评论