0

给定一个包含N个数字的数组A（全为正数且包含小于或等于 4 位数字），将支持2种类型的查询。总共有 M 个查询。

  1. 用K更新由索引L,R（包括两者）给出的范围。
  2. 返回L,R（包括两者）给定范围内的最大元素。

将数字更新K次意味着将数字旋转K次。

例如 1234 旋转成 2341

905转成059，059转成590。

注意：059 和 59 是不同的数字。59 转为 95。

给定的数组元素没有前导零。

约束：

0 <= Ai < 10000

1 <= N <= 800000

1 <= M <= 200000

0 <= K <= 60

我想到了一个分段树，其中树节点存储它们包含的范围的旋转次数。我用惰性传播实现了这一点，但也使用惰性传播，我的查询实现在最坏的情况下需要 O(N) 时间，这会导致 TIME LIMIT EXCEEDED。

任何人都可以提出更快的方法吗？

我是否缺少数组或结构的某些属性？

4

1 回答 1

2

您存储旋转次数的想法是正确的。
以下是如何使它更胖（O(log N)每个查询）。
1）节点结构定义：

class Node:
    int shift = 0 //number of rotations
    int max[12] //maximum value for shift = 0..11
    Node left_child //the left child of this node
    Node right_child //the right child of this node

2）传播：

void propagate(Node node):
    node.left_child.shift += node.shift
    node.left_child.shift %= 12
    node.right_child.shift += node.shift
    node.right_child.shift %= 12
    node.shift = 0
    for i = 0..11:
        node.max[i] = max(get_max(node.left_child, i), 
                          get_max(node.right_child, i))

int get_max(Node node, int shift):
     return node.max[(shift + node.shift) % 12]

3）更新和获取操作可以像传统的线段树一样实现。

为什么它工作得很快？因为propagate不是递归的。它仅在回答查询时在树遍历期间访问的那些节点调用。并且每个查询只有O(log N)这样的节点（由于段树的属性）。

为什么使用常数 12？因为lcm(1, 2, 3, 4) = 12.(1, 2, 3, 4是每个数组元素的可能位数）。

于 2014-08-09T15:17:42.587 回答