Phys Ed Online

题意翻译

### 题目描述 一所不知名大学的学生没有体育课。这就是为什么他们中的$q$个人决定自己去附近的健身房。健身房共开放$n$天，并设有门票系统。在第$i$天，一张门票的费用等于$a_i$，您被允许每天可以购买一张以上的门票。 您可以在第$i$天或之后的任何一天激活已购买的门票。每张已激活的门票仅在$k$天内有效。换句话说，如果您在第$t$天激活了门票，它将仅在第$t$天、第$t+1$,...,第$t+k-1$天有效。 您现在知道第$j$个学生想要在从$l_i$到$r_i$的每一天都去健身房。而每个学生将在第$i$天$(l_i \le i \le r_i)$通过下列的步骤进入健身房: $1.$一个学生来到健身房门口的售票处，用$a_i$的价格购买几张门票。($a_i$可能为零) $2.$如果这个学生至少有一张已激活的有效门票，便可直接进入健身房。否则，这个学生必须激活一张今天或是更早时候购买的门票才能进入健身房。 注意，每个学生从第$l_j$天开始就会去健身房，所以每个学生必须在第$l_j$天购买至少一张门票。 请帮助学生们计算去健身房的最低花费。 ### 输入格式 第一行包含三个整数 $n$,$q$,$k$ ($1 \leqslant n,q \leqslant 300000;1\leqslant k \leqslant n$) 表示有$n$天，$q$个学生，以及每张门票的有效期为$k$天。 第二行包含$n$个整数 $a_1,a_2,...a_n(1 \leqslant a_i \leqslant 10^9)$ 表示相应天数的一张门票的费用。 接下来的$q$行中，每一行都包含两个整数，$l_i$和$r_i$ ($1 \leqslant l_i \leqslant r_i \leqslant n$) 表示相应的学生想去健身房的时间段。 ### 输出格式 输出每个学生去健身房的最低花费。 ### 说明/提示 让我们看看每个学生如何花钱： $\bullet$第一名学生应在第$1$天购买一张门票。 $\bullet$第二名学生应在第$3$天购买一张门票，在第$4$天购买两张门票。注意，学生们可以在接下来的几天中保留已购买的门票。 $\bullet$第三名学生应在第$5$天购买一张门票。 $\bullet$第四名学生应在第$7$天购买一张门票。 $\bullet$第五名学生应在第$3$天购买一张门票，第$4$天购买一张门票。

题目描述

Students of one unknown college don't have PE courses. That's why $ q $ of them decided to visit a gym nearby by themselves. The gym is open for $ n $ days and has a ticket system. At the $ i $ -th day, the cost of one ticket is equal to $ a_i $ . You are free to buy more than one ticket per day. You can activate a ticket purchased at day $ i $ either at day $ i $ or any day later. Each activated ticket is valid only for $ k $ days. In other words, if you activate ticket at day $ t $ , it will be valid only at days $ t, t + 1, \dots, t + k - 1 $ . You know that the $ j $ -th student wants to visit the gym at each day from $ l_j $ to $ r_j $ inclusive. Each student will use the following strategy of visiting the gym at any day $ i $ ( $ l_j \le i \le r_j $ ): 1. person comes to a desk selling tickets placed near the entrance and buy several tickets with cost $ a_i $ apiece (possibly, zero tickets); 2. if the person has at least one activated and still valid ticket, they just go in. Otherwise, they activate one of tickets purchased today or earlier and go in. Note that each student will visit gym only starting $ l_j $ , so each student has to buy at least one ticket at day $ l_j $ . Help students to calculate the minimum amount of money they have to spend in order to go to the gym.

输入输出格式

输入格式

The first line contains three integers $ n $ , $ q $ and $ k $ ( $ 1 \le n, q \le 300\,000 $ ; $ 1 \le k \le n $ ) — the number of days, the number of students and the number of days each ticket is still valid. The second line contains $ n $ integers $ a_1, a_2, \dots, a_n $ ( $ 1 \le a_i \le 10^9 $ ) — the cost of one ticket at the corresponding day. Each of the next $ q $ lines contains two integers $ l_i $ and $ r_i $ ( $ 1 \le l_i \le r_i \le n $ ) — the segment of days the corresponding student want to visit the gym.

输出格式

For each student, print the minimum possible amount of money they have to spend in order to go to the gym at desired days.

输入输出样例

输入样例 #1

7 5 2
2 15 6 3 7 5 6
1 2
3 7
5 5
7 7
3 5

输出样例 #1

2
12
7
6
9

说明

Let's see how each student have to spend their money: - The first student should buy one ticket at day $ 1 $ . - The second student should buy one ticket at day $ 3 $ and two tickets at day $ 4 $ . Note that student can keep purchased tickets for the next days. - The third student should buy one ticket at day $ 5 $ . - The fourth student should buy one ticket at day $ 7 $ . - The fifth student should buy one ticket at day $ 3 $ and one at day $ 4 $ .