主题思路
听老师讲解部分:
大跨度,但数值稀疏
(保序)离散化
难点
1. 去重
2. 找离散化的值(二分)
老师没有特别提到的部分:
其实老师的做题思路就是一种“离线处理”
把几次的查询操作一并收集起来一并处理,这样更好发现数据中的“相对关系”
在这里提现为查询的l,r坐标都参与离散化数组的创建
与之相对的就是“在线处理”
就是来一次查询就立马处理一次
注意细节
不一样的数据读写方法也会大大影响程序的运行速度,选个合适的方法吧
基础代码:最快写法
package main
import (
"bufio"
"fmt"
"os"
"sort"
"strconv"
"strings"
)
type pair struct {
first int
second int
}
var (
n, m int
scanner = bufio.NewScanner(os.Stdin) // 整行读取器
bs = make([]byte, 20000 * 1024)
readLine = func() (res []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
}
out = bufio.NewWriter(os.Stdout)
find = func(alls []int, x int) int { // 在离散化数组上查找位置(下标),二分查找
l, r := 0, len(alls) - 1
for l < r {
mid := l + (r - l) >> 1
if alls[mid] >= x {
r = mid
} else {
l = mid + 1
}
}
return r + 1
}
unique = func(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
}
add = make([]pair, 0) // 数组:pair{x, c}, 把n次的“在位置x存值c的操作”一并处理(存起来)
query = make([]pair, 0) // 数组:pair{l, r}, 把m次的“查[l, r]的区间和的操作”一并处理(存起来)
alls = make([]int, 0) // 离散化数组,存的值是已经排序+去重的[x, l, r]
)
func main() {
scanner.Buffer(bs, len(bs))
cur := readLine()
n, m = cur[0], cur[1]
for i := 0; i < n; i++ {
cur := readLine()
add = append(add, pair{cur[0], cur[1]})
alls = append(alls, cur[0])
}
for i := 0; i < m; i++ {
cur := readLine()
alls = append(alls, cur[0])
alls = append(alls, cur[1])
query = append(query, pair{cur[0], cur[1]})
}
sort.Ints(alls)
alls = unique(alls)
a := make([]int, len(alls) + 1) // 建比离散数组长1的存c的数组
for _, item := range add { // 读取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] } // 生成数组a的前缀和数组
for _, item := range query { // 读取queue里的操作指令
l, r := find(alls, item.first), find(alls, item.second) // 在离散数组上寻址 l, r
fmt.Fprint(out, s[r] - s[l - 1], "\n") // 计算[l, r]的区间和
}
out.Flush()
}
有没有人拼团买算法基础课,有意者加q:2289930942