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