在段树元素旋转 [英] Element rotation in segment tree

问题描述

由于数组的 A 的用的 N 的数字（所有正面和含有少于   或等于4位）， 2 的类型的查询都被支持。那里   是总共M个查询。

Given an array A with N numbers(all positive and contain less than or equal to 4 digits), 2 types of queries are to be supported. There are total M queries.

  
1. 更新通过指数给出了一系列的 L，R 的（包括两端）通过的 K 的
  
2. 返回由给定范围内的最大元素的 L，R 的（包括两端）。
  

1. Update a range given by indices L,R(both inclusive) by K.
2. Return the maximum element in a range given by L,R(both inclusive).

更新了许多的 K 的时间意味着旋转数的 K 的时间。

Updating a number K times implies rotating the number K times.

有关如1234旋转到2341

For e.g. 1234 rotates into 2341

905旋转到059和059旋转到590。

905 rotates into 059 and 059 rotates into 590.

注意的：059和59不同的号码。 59旋转到95。

Note : 059 and 59 are different numbers. 59 rotates into 95.

由于数组元素的没有前导零的。

约束：

0℃= 爱的＆LT; 10000

0 <= Ai < 10000

1 LT = N 的＆LT; = 800000

1 <= N <= 800000

1 LT = M 的＆LT; = 200000

1 <= M <= 200000

0℃= K 的＆LT; = 60

0 <= K <= 60

我认为一个线段树中的树节点存储它们所包含的范围的转数的。我实现了这个懒惰的传播史，但与懒惰的传播史过于我的查询实现需要O（n）的时间，在最坏的情况下，这是导致时间限制超出。

I thought of a segment tree in which the tree nodes store the number of rotations of the range they contain. I implemented this with lazy propogation but with the lazy propogation too my query implementation takes O(N) time in the worst case, which is leading to TIME LIMIT EXCEEDED.

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

Can anyone propose a faster approach?

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

Am I missing some property of the array or structure?

推荐答案

您存储旋转数的思路是正确的。照片 以下是如何使其工作fatser（ O（日志N）每次查询）。
1）节点结构定义：

Your idea of storing the number of rotation is correct.
Here is how to make it work fatser(O(log N)per query).
1)Node structure definition:

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）传播：

2)Propagation:

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）更新和获取操作可以像在常规的线段树来实现。

3)Update and get operation can be implemented like in a conventional segment tree.

为什么它的工作速度快？因为传播不是递归。这就是所谓的只对这些树的遍历期间回答查询时访问这些节点。而只有 O（日志N）每次查询这样的节点（由于段树的属性）。

Why does it work fast? Because propagate is not recursive. It is called only for those nodes which are visited during the tree traversal when answering a query. And there are only O(log N) such nodes per query(due to the properties of a segment tree).

为什么恒定的12使用？因为 LCM（1，2，3，4）= 12 。（ 1，2，3，4 是可能的的每个阵列元素的数字）的号码。

Why is constant 12 used? Because lcm(1, 2, 3, 4) = 12.(1, 2, 3, 4 are possible numbers of digits of each array element).

这篇关于在段树元素旋转的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！