430. 区间和
时间限制：2000 MS 内存限制：64 MB
题目描述
# 区间和 ## 题目描述 假定有一条无限长的数轴，数轴上每个整数坐标处的数最初都是 $0$。 首先进行 $n$ 次修改，每次修改将坐标 $x$ 处的数加上 $c$。同一坐标可以被修改多次，各次修改的增量累加。 全部修改完成后，进行 $m$ 次询问。每次询问给出两个整数 $l$ 和 $r$，请你求出闭区间 $[l,r]$ 内所有整数坐标处的数之和。 ## 输入格式 从文件 `intervals.in` 读入数据。 第一行包含两个整数 $n$ 和 $m$，分别表示修改次数和询问次数。 接下来 $n$ 行，每行包含两个整数 $x$ 和 $c$，表示将坐标 $x$ 处的数加上 $c$。 再接下来 $m$ 行，每行包含两个整数 $l$ 和 $r$，表示询问闭区间 $[l,r]$ 内所有数的和。 ## 输出格式 输出到文件 `intervals.out`。 输出共 $m$ 行，按照询问的顺序，每行输出一个整数，表示对应闭区间内所有数的和。 ## 数据范围 - $1 \le n,m \le 10^5$。 - $-10^9 \le x \le 10^9$。 - $-10^9 \le l \le r \le 10^9$。 - $-10^4 \le c \le 10^4$。 - 保证任一区间和的绝对值不超过 $10^9$。 ## 样例输入 ``` 3 3 1 2 3 6 7 5 1 3 4 6 7 8 ``` ## 样例输出 ``` 8 0 5 ``` ## 运行限制 - 时间限制：$2000$ 毫秒。 - 内存限制：$64$ MB。