从序列中减去一个数字后，剩下的多少个数字是正数? [英] After subtracting a number from a sequence, how many of remaining numbers are positive?

问题描述

我有一个长度为 N 的数字序列. 我将必须对此编号序列执行 Q 操作.

I have a number sequence of length N. I will have to do Q operations on this number sequence.

在每个操作中，我将得到三个整数 P，Q，V ，其中 P≤Q≤N ，并将从每个整数中减去 V iᵗʰ整数，其中 P≤i≤Q .

In each operation I will be given three integers P, Q, V with P ≤ Q ≤ N and will subtract V from every iᵗʰ integer, where P ≤ i ≤ Q.

每次操作后，我将再得到两个整数 X，Y ，其中 X≤Y≤N .我将不得不回答Xᵗʰ和Yᵗʰ(含)整数之间有多少个整数为正数.

After each operation, I will be given another two integers X, Y with X ≤ Y ≤ N. I will have to answer how many integers between the Xᵗʰ and Yᵗʰ (inclusive) integers are positive.

Q 大约为 10 ⁵ .我将必须执行所有操作并在1/2秒内回答相应的查询.

Q will be around 10⁵. I will have to do all the operations and answer the corresponding queries in around 1/2 seconds.

我应该使用哪种算法/数据结构?程序将是什么?

What algorithm/data structure should I use? And what the procedure will be?

注意:我对段树或二进制索引树有相当的了解.如果您的解决方案涉及这些数据结构，那就太好了.

Note : I have a decent knowledge in Segment Trees or Binary Indexed Trees. If your solution involves these data structures, that will be great.

推荐答案

数据结构

将具有延迟传播的段树用于数据结构.

Data structure

Use a segment tree with lazy propagation for the data structure.

在每个节点存储中:

1. 所有子节点中的正值数量
2. 所有子节点的最小正值(即，对于值为-1、3、5，-10的子节点，最小正值为3.我们忽略-1和-10，因为它们不是正数.)
3. 从该节点减去要减去的值(已初始化为0)

更新

更新范围的过程将是:

Update

The procedure for updating a range will be:

1. 递归地进入细分树，直到找到一个完全被范围覆盖的节点
2. 修改节点的待定值

查询

回答范围查询的过程将是:

Query

The procedure for answering the query for a range will be:

1. 递归地进入细分树，直到找到一个完全被范围覆盖的节点
2. 如果节点的暂挂值大于最小正值，则递归更新节点的属性

复杂度

由于每个节点只能变为负数一次，因此我认为整个过程应为O(nlogn + qlogn)，其中n是序列的长度，q是操作数.

Complexity

As each node can only become negative once, I believe this whole procedure should be O(nlogn+qlogn) where n is the length of the sequence and q is the number of operations.

假设我们有数组[1,5，-3,4].

Suppose we have the array [1,5,-3,4].

我们将具有以下分段节点:

We will have segment nodes as follows:

[1,5,-3,4] min positive 1, pending change 0
[1,5] min positive 1, pending change 0
[-3,4] min positive 4, pending change 0

假设我们想用减2来更新整个范围，则将其更改为:

Suppose we wanted to update the whole range with a subtraction of 2, we would change this to:

[1,5,-3,4] min positive 1, pending change 2.

现在，由于挂起的更改> =最小正值，我们需要通过将更改向下递归推入左子对象和右子对象来修复节点.

Now, as the pending change is >= the min positive, we need to fix the node by recursively pushing the change down into the left child and the right child.

首先，左孩子将变为:

[1,5] min positive 1, pending change 2

然后我们将再次扩展此节点，并将更新应用为

We would then expand this node again and apply the updates to become

[-1,3] min positive 3, pending change 0

接下来，我们将找到合适的孩子，该孩子将更改为

Next we would come to the right child which would change to

[-3,4] min positive 4, pending change 2

，但由于未决更改<不需要进一步递归最小正数.

but no further recursion would be required as pending change < min positive.

最后，递归将再次到达顶级节点.我们使用左右孩子的属性来计算，现在最小正数为2(来自右边孩子的最小4和待定2，结果为4-2 = 2)，并且可以将待定更改重置为0因为它已应用于孩子们.

Finally the recursion would reach the top level node again. We use the properties of the left and right child to calculate that now the min positive is 2 (from the right child with min 4 and pending 2 giving a result of 4-2=2), and we can reset the pending change to 0 because it has been applied to the children.

这篇关于从序列中减去一个数字后，剩下的多少个数字是正数?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！