段树中的元素旋转

Question

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

1. 将索引 L，R(包括两者(给出的范围更新为 K。
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( 时间，这导致超出时间限制。

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

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

Answer 1

您存储旋转次数的想法是正确的。
以下是使其工作更胖的方法(每个查询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是每个数组元素的可能位数(。