QOJ.ac

QOJ

Time Limit: 1 s Memory Limit: 512 MB Total points: 100

# 7442. qwq

统计

定义初始数列为每个数字都为 $0$ 的数列。

定义一次操作为将数列的一个区间中每一个数的值增加 $1$,规定该区间的长度不能超过 $m$。

给定一个长度为 $n$ 的数列 $a$,第 $i$ 个数为 $a_i$。

你需要回答 $q$ 次询问。每次询问给定 $l,r$,你需要回答将一个长度为 $r-l+1$ 的初始数列变为 $a$ 中的 $[l,r]$(即数列 $a_l$, $a_{l+1}$, $\cdots$, $a_r$)至少需要多少次操作。

输入格式

第一行三个整数 $n,m,q$。

第二行 $n$ 个整数,第 $i$ 个为 $a_i$。

接下来 $q$ 行,每行两个整数,表示 $l,r$。

输出格式

$q$ 行,每行一个整数,表示至少需要的操作次数。

样例数据

样例 1 输入

5 4 1
1 1 2 1 1
1 5

样例 1 输出

2

样例 1 解释

一个长度为 $5$ 的初始数列为 $0$ $0$ $0$ $0$ $0$。

第一次操作为,将区间 $[1,3]$ 中每一个数,即第 $1$、$2$、$3$ 个数的值分别增加 $1$。经过该操作后,数列变为 $1$ $1$ $1$ $0$ $0$。

第二次操作为,将区间 $[3,5]$ 中每一个数,即第 $3$、$4$、$5$ 个数的值分别增加 $1$。经过该操作后,数列变为 $1$ $1$ $2$ $1$ $1$。

样例 2 输入

10 3 3
4 8 1 2 9 7 4 1 3 5
1 10
3 8
5 5

样例 2 输出

22
10
9

子任务

  • Subtask 1(1 point):$m=1$。
  • Subtask 2(4 points):$m=n$。
  • Subtask 3(10 points):$n,q\le300$。
  • Subtask 4(10 points):$n,q\le5\times10^3$。
  • Subtask 5(15 points):$m\le5$。
  • Subtask 6(15 points):$m\le100$。
  • Subtask 7(20 points):$n,q\le5\times10^4$。
  • Subtask 8(25 points):无特殊限制。

对于 $100\%$ 的数据,保证 $1\le m\le n\le10^5$,$1\le q\le10^5$,$0\le a_i\le10^9$,$1\le l\le r\le n$。