假定有一个无限长的数轴，数轴上每个坐标上的数都是0。

现在，我们首先进行 n 次操作，每次操作将某一位置x上的数加c。

接下来，进行 m 次询问，每个询问包含两个整数l和r，你需要求出在区间[l, r]之间的所有数的和。

输入格式

第一行包含两个整数n和m。

接下来 n 行，每行包含两个整数x和c。

再接下里 m 行，每行包含两个整数l和r。

输出格式

共m行，每行输出一个询问中所求的区间内数字和。

数据范围

−109≤x≤109,
1≤n,m≤105,
−109≤l≤r≤109,
−10000≤c≤10000

输入样例：

3 3
1 2
3 6
7 5
1 3
4 6
7 8

输出样例：

8
0
5

Go 代码

package main

import (
    "bufio"
    "fmt"
    "os"
    "sort"
    "strconv"
    "strings"
)

type pair struct { // 定义操作
    first  int
    second int
}

func main() {
    scanner = bufio.NewScanner(os.Stdin)
    bs := make([]byte, 20000*1024)
    scanner.Buffer(bs, len(bs))

    var n, m int
    fmt.Scanf("%d%d", &n, &m)
    add := make([]pair, 0)   // 插入操作
    query := make([]pair, 0) // 询问操作
    alls := make([]int, 0)   // 把所有要用到的下标放到 alls 数组中

    for i := 0; i < n; i++ {
        x := readline()
        add = append(add, pair{x[0], x[1]}) // 插入操作-将某一位置x上的数加c。
        alls = append(alls, x[0])           // 加入到离散化后的数组中去
    }

    for i := 0; i < m; i++ {
        x := readline()
        alls = append(alls, x[0])               // 区间的左端点离散化
        alls = append(alls, x[1])               // 区间的右端点离散化
        query = append(query, pair{x[0], x[1]}) // 询问操作-读取询问的左右区间
    }

    sort.Ints(alls)     // alls 数组排序
    alls = unique(alls) // alls 数组去重

    // 处理插入
    a := make([]int, len(alls)+1)
    for _, item := range add {
        x := find(alls, item.first) // 位置 x
        a[x] += item.second         // 插入操作将某一位置x上的数加c
    }

    // 预处理前缀和
    s := make([]int, len(a))
    for i := 1; i <= len(alls); i++ {
        s[i] = s[i-1] + a[i]
    }

    // 处理询问
    for _, item := range query { // 左右断点离散化后的值
        l, r := find(alls, item.first), find(alls, item.second)
        fmt.Println(s[r] - s[l-1])
    }

}

func unique(a []int) (b []int) {
    // 已经排过序了
    j := 0
    for i := 0; i < len(a); i = j {
        for j < len(a) && a[j] == a[i] {
            j++
        }
        b = append(b, a[i])
    }
    return b
}

// 求 x 位置上的值离散化后的结果
func find(alls []int, x int) int {
    l, r := 0, len(alls)-1 // 二分查找
    for l < r {
        mid := l + (r-l)/2
        if alls[mid] >= x {
            r = mid
        } else {
            l = mid + 1
        }
    }
    return r + 1 // 把所有数值映射到从1开始的自然数，方便前缀和计算，避免考虑边界
}

var scanner *bufio.Scanner

func readline() []int {
    scanner.Scan()
    l := strings.Split(scanner.Text(), " ")

    res := make([]int, len(l))
    for i, s := range l {
        x, _ := strconv.Atoi(s)
        res[i] = x
    }
    return res
}