gpt4 book ai didi

algorithm - 更新范围并跟踪每个索引出现的最大值

转载 作者:塔克拉玛干 更新时间:2023-11-03 03:43:39 24 4
gpt4 key购买 nike

<分区>

You are given an array, say A[], of N elements, initially all of them are equal to negative infinity.

现在要求您执行两种类型的查询(总共 M 个查询):

Type 1. Given two integers a and d you need to update the array A[] from index l to index r. What you need to do exactly is - for each index l+i (where 0<=i<=r-l) which contains some value say 'val' you need to update the value of that index with maximum of a+i*d and val, i.e, A[l+i] = max(A[l+i], a+i*d).

类型 2. 给定一个整数 'i',你需要报告 A[i] 的值。

Example : let N = 5 and M = 4

initially A[] = {-inf, -inf, -inf, -inf, -inf}
query 1: l = 2, r = 4, a = 2, d = 3
new A[] = {-inf, 2, 5, 8, -inf}
query 2: i = 3
output = 5
query 3: l = 3, r = 5, a = 10, d = -6
new A[] = {-inf, 2, 10, 8, -2}
query 4: i = 5
output = -2

Note : value of N and M can be as large as 100000 so I am looking for better algorithms than O(N*M).

谢谢。

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com