输入一个长度为n的整数序列。
接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c。
请你输出进行完所有操作后的序列。
输入格式
第一行包含两个整数n和m。
第二行包含n个整数,表示整数序列。
接下来m行,每行包含三个整数l,r,c,表示一个操作。
输出格式
共一行,包含n个整数,表示最终序列。
数据范围
1≤n,m≤100000,
1≤l≤r≤n,
−1000≤c≤1000,
−1000≤整数序列中元素的值≤1000
输入样例:
6 3
1 2 2 1 2 1
1 3 1
3 5 1
1 6 1
输出样例:
3 4 5 3 4 2
Go 代码 TLE
package main
import (
"fmt"
)
const N int = 100010
var a = [N]int{} // 原数组
var b = [N]int{} // 差分数组
// 插入函数
func insert(l, r, c int) {
b[l] += c
b[r+1] -= c
}
func main() {
var n, m int
fmt.Scanf("%d%d", &n, &m)
for i := 1; i <= n; i++ {
fmt.Scanf("%d", &a[i])
}
for i := 1; i <= n; i++ {
insert(i, i, a[i]) // 构造原数组,插入原数组的n个数
}
// 接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c
for i := 0; i < m; i++ {
var l, r, c int
fmt.Scanln(&l, &r, &c)
insert(l, r, c)
}
// 输出进行完所有操作后的序列
for i := 1; i <= n; i++ {
b[i] += b[i-1] // 即对差分数组求一遍前缀和
}
for i := 1; i <= n; i++ {
fmt.Printf("%d ", b[i])
}
}
Go 代码优化 io
package main
import (
"bufio"
"errors"
"fmt"
"os"
"strconv"
"strings"
)
var reader *bufio.Reader
func readline() ([]int, error) {
str, err := reader.ReadString('\n')
str = str[:len(str)-1]
if len(str) == 0 || err != nil {
return nil, errors.New("stdin read error.\n")
}
l := strings.Split(str, " ")
res := make([]int, 0)
for _, s := range l {
x, _ := strconv.Atoi(s)
res = append(res, x)
}
return res, nil
}
func insert(b []int, l, r, c int) {
b[l] += c
b[r+1] -= c
}
func main() {
reader = bufio.NewReader(os.Stdin)
var n, m int
_, _ = fmt.Scanln(&n, &m)
a, _ := readline() // 读取原数组
b := make([]int, n+2) // 差分数组
for i := 0; i < n; i++ { // 构造原数组
insert(b, i+1, i+1, a[i])
}
for i := 0; i < m; i++ { // 操作
x, _ := readline()
insert(b, x[0], x[1], x[2])
}
for i := 1; i <= n; i++ {
b[i] += b[i-1] // 差分数组的前缀和组成原数组
fmt.Printf("%d ", b[i])
}
}
Go 实现 bufio.NewScanner
package main
import (
"bufio"
"fmt"
"os"
"strconv"
"strings"
)
// 插入函数
func insert(b []int, l, r, c int) {
b[l] += c
b[r+1] -= c
}
var scanner *bufio.Scanner
func main() {
var n, m int
// file, _ := os.Open("./1.txt")
// defer file.Close()
scanner = bufio.NewScanner(os.Stdin)
bs := make([]byte, 20000*1024)
scanner.Buffer(bs, len(bs))
nm := readLine()
n, m = nm[0], nm[1]
a := readLine()
b := make([]int, n+2) // 差分数组
for i := 0; i < n; i++ {
if len(a) == n {
insert(b, i+1, i+1, a[i]) // 构造原数组,插入原数组的n个数
}
}
// 接下来输入m个操作,每个操作包含三个整数l, r, c,表示将序列中[l, r]之间的每个数加上c
for i := 0; i < m; i++ {
l := readLine()
if len(l) == 3 {
insert(b, l[0], l[1], l[2])
}
}
// 输出进行完所有操作后的序列
for i := 1; i <= n; i++ {
b[i] += b[i-1] // 即对差分数组求一遍前缀和
fmt.Printf("%d ", b[i])
}
}
func readLine() []int {
scanner.Scan()
line := strings.Split(strings.TrimSpace(scanner.Text()), " ")
res := make([]int, len(line))
for i, num := range line {
x, _ := strconv.Atoi(num)
res[i] = x
}
return res
}
谢谢谢谢!
请教个问题,差分数组n+2什么意思,没看明白
为什么你的题解我发现执行的时候都会超时
数据增加了吧😂
我说为啥总 TLE 呢,原来是 IO 不行…感谢楼主