反转数组查询 [英] Reversing an array Query

问题描述

我有一个大小为 N 的数组，我给出了两种类型的查询

I have an array of size N and I have given 2 types of query

1 L R 反转 [L,R] 中的所有元素
2 L 找到索引 L 处的值.

1 L R Reverse all element from [L,R]
2 L Find the value at index L.

Example: [1,2,3,4,5]
1 2 4   -> [1,4,3,2,5]
1 4 5   -> [1,4,3,5,2]
2 5    -> 2

Q-查询次数
Q<=10^5 和 N<=10^5
直截了当的解决方案将是O(Q*N)，这会很慢，如何使它更快可以使用分割树?

Q-Number of Query
Q<=10^5 and N<=10^5
Straight Forward Solution will be O(Q*N) which will be Quite slow, how to make it faster can segment tree can be used ?

推荐答案

我不确定线段树算法是什么样的.

I'm not sure what the segment tree algorithm looks like.

这可以使用装饰的展开树在 O((n + q) log n) 时间内完成.每个节点装饰由一个后代计数和一个位组成，当设置时，隐式翻转整个子树.要查询，请使用后代计数导航到正确的节点.从 u 到 v 反转，将 u 展开到根，分离其左子树 uL，展开 v 到根，分离其右子树 vR，反转所有 uL, v, 上的翻转位>vR，将 uL 重新附加到 vR 来自的字段，展开 u，重新附加 vR类似.

This can be done in time O((n + q) log n) using decorated splay trees. Each node decoration consists of a descendant count and a bit that, when set, implicitly flips the entire subtree. To query, use the descendant counts to navigate to the proper node. To reverse from u to v, splay u to the root, detach its left subtree u.L, splay v to the root, detach its right subtree v.R, invert the flip bits on all of u.L, v, v.R, reattach u.L to the field from which v.R came, splay u, reattach v.R similarly.

Key: ? denotes an anonymous node
     ^ denotes a subtree


   u
  / 
u.L  ?
 ^  / 
   v   ?
   ^   ^


u.L    v
 ^    / 
     u  v.R
        ^
       ?
       ^


v.R    v     # v's flip bit is inverted
 ^    / 
     u  u.L  # so is u.L's, for no effect on u.L
        ^
       ?
       ^


   u
  / 
v.R  v
 ^  / 
   ?  u.L
   ^   ^

这篇关于反转数组查询的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！