反转数组查询

Question

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

1 LR反转[L,R]
2 L中的所有元素在索引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),这将是相当慢的,如何使它更快可以使用分段树？

Answer 1

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

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

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
   ^   ^