fzu 2171 線段樹 lazy标記

 http://acm.fzu.edu.cn/problem.php?pid=2171

     problem 2171 防守陣地 ii

部隊中總共有n個士兵，每個士兵有各自的能力指數xi，在一次演練中，指揮部确定了m個需要防守的地點，指揮部将選擇m個士兵依次進入指定地點進行防守任務，獲得的參考指數即為m個士兵的能力之和。随着時間的推移，指揮部将下達q個指令來替換m個進行防守的士兵們，每個參加完防守任務的士兵由于疲憊等原因能力指數将下降1。現在士兵們排成一排，請你計算出每次進行防守的士兵的參考指數。

輸入包含多組資料。

輸入第一行有兩個整數n,m,q(1<=n<=100000，1<=m<=1000,1<=q<=100000),第二行n個整數表示每個士兵對應的能力指數xi（1<=xi<=1000）。

接下來q行，每行一個整數x，表示在原始隊列中以x為起始的m個士兵替換之前的士兵進行防守。（1<=x<=n-m+1）

對于30%的資料1<=m,n,q<=1000。

輸出q行，每行一個整數，為每次指令執行之後進行防守的士兵參考指數。

5 3 3 2 1 3 1 4 1 2 3

6 3 5