倒车数组查询 [英] Reversing an array Query

问题描述

我有一个大小为N的数组，我已经给了2种查询

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

1 L R从反向[L，R] in所有元素 2升寻找在指数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

问：的查询
-Number Q＆LT; = 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 的根，分离其左子树微升，张开 v 根，分离其右子树 VR ，颠倒翻转位上的所有微升， v ， VR ，重新安装微升到外地从 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屋！