问题标签 [segment-tree]

http://www.spoj.com/problems/CTRICK/ It is a problem on spoj It states that

The magician shuffles a small pack of cards, holds it face down and performs the following procedure:

1. The top card is moved to the bottom of the pack. The new top card is dealt face up onto the table. It is the Ace of Spades.

2. Two cards are moved one at a time from the top to the bottom. The next card is dealt face up onto the table. It is the Two of Spades.

3. Three cards are moved one at a time…</p>

4. This goes on until the nth and last card turns out to be the n of Spades.

This impressive trick works if the magician knows how to arrange the cards beforehand (and knows how to give a false shuffle). Your program has to determine the initial order of the cards for a given number of cards, 1 ≤ n ≤ 20000.

Input

On the first line of the input is a single positive integer, telling the number of test cases to follow. Each case consists of one line containing the integer n. Output

For each test case, output a line with the correct permutation of the values 1 to n, space separated. The first number showing the top card of the pack, etc… Example

Input: 2

4

5

Output:

2 1 4 3

3 1 4 5 2

Now the only solution i can think of is to use a queue and simulate the process. But that would be O(n^2).I read the comments and they suggested using segment tree of BIT. I know both segment tree and BIT but am unable to understand how to implement them in this question.Please suggest some way to do this. Thanx

我正在尝试了解线段树。这是一个很棒的教程，展示了如何找到范围内的最小值。但是，据说“除了最后一层之外，所构造的段树的所有层都将被完全填充。此外，树将是一个完整的二叉树，因为我们总是在每一层将段分成两半。”。我不明白添加是如何执行的？例如，如果我们再添加两个元素 6 和 10 - 他们应该去哪里？进入右子树？如果是，将有 5 个不太平衡，并且一半不相等。我应该以某种方式重新排序树并再次进行计算吗？

在本教程中，为什么query()函数会修改M最后 4 行代码中的内容，而不是只返回节点索引？

我认为他的方法存在问题：修改后的 M 数组将无法处理未来的 RMQ [范围最小查询]，因为m[node]存储了最近查询的索引。

这是我正在谈论的代码：

给定一个大小为 N 的数组，以及一个大小为 N 的区间数组，每个数组都是第一个数组的连续段，我需要处理 Q 查询，这些查询更新数组的元素并询问第二个数组（第 i 个区间到第 j 个区间的元素之和）。

现在，可以轻松处理第一个查询。我可以从数组中构建一个段树。我可以用它来计算第一个数组（第二个数组中的一个元素）中间隔的总和。但是我如何处理 O(log n) 中的第二个查询？在最坏的情况下，我更新的元素将在第二个数组的所有间隔中。

我需要 O(Q log N) 或 O(Q (logN)^2) 解决方案。

段树 O(logn) 最坏情况下的范围和如何？不应该是O(n)吗？如果在范围求和操作期间，我们按照算法遍历左右节点怎么办？

给定一个包含 N 个元素和 N 个范围的数组 A，每个范围的形式为 [L, R]。将范围的值称为 A 中从索引 L 到索引 R 的所有元素的总和，包括索引 L 和索引 R。

示例：让数组 A = [2 5 7 9 8] 并且给定的范围是 [2,4] 那么这个范围的值是 5+7+9=21

现在我们得到了 Q 查询，每个查询都是以下两种类型之一：

示例：让数组 A = [2 3 7 8 6 5] 并让我们有 3 个范围：

现在让我们有 3 个查询：

如果我们有 10^5 个查询并且 N 也高达 10^5，该怎么做。如何以有效的方式向 Queries2 报告？

我的方法：第一个查询可以轻松处理。我可以从数组中构建一个段树。我可以用它来计算第一个数组（第二个数组中的一个元素）中间隔的总和。但是我如何处理 O(log n) 中的第二个查询？在最坏的情况下，我更新的元素将在第二个数组的所有间隔中。

我需要 O(Qlog N) 或 O(Q(logN)^2) 解决方案。

显然我们不能为每个查询都有一个 O(N)。所以请帮助获得有效的方法

我当前的代码：

虽然代码是正确的，但对于较大的测试用例，它需要大量时间。请帮助

我们如何证明分段树 ( http://letuskode.blogspot.in/2013/01/segtrees.htmlupdate ) 上的andquery操作（不要与区间树混淆）是？O(log n)

我想到了一种方法——在每个节点上，我们最多对左右子树进行两次递归调用。如果我们能够证明其中一个调用相当快地终止，那么时间复杂度将是对数有界的。但我们如何证明这一点？

我需要一个数据结构来存储一组间隔并允许计算它们的联合长度。

1假设在和之间有一组整数端的区间n。最初它是空的，可以添加或删除间隔。在每次操作之后，应该计算集合中所有区间的并集长度。

如何通过具有O(log n)时间复杂度的线段树来实现它，用于推送、删除和查找长度？应该在节点中存储什么？

我需要段树来解决我的任务。我应该开发自己的段树，还是这种树有什么好的实现？

我需要以下操作：

1. 细分更新：tree.add(from, to, value)
2. 段总和：tree.sum(from, to)

【挑战结束】

问题：

一组正元素。Deepu 想减少数组的元素。他调用了一个函数 Hit(X)，它将数组中大于 X 的所有元素减少 1。

他会多次调用这个数组。在多次调用 Hit(X) 后打印数组。

输入：

n----- 数组 10^5 中没有元素。

n 个元素 ----- 1<=元素<=10^9。

x----- 对 Hit(X) x 个元素的调用次数----- 1<=element<=10^9。

输出：

打印调用 Hit(X) x 次后的数组。

时间限制--5 秒。

我的解决方案给出了 Time Limit Exceeded。

我的做法：

1. 保留原始数组
2. 创建数组元素对的向量及其在数组中的索引 对向量元素进行排序 [ 升序 ]。
3. 执行 C++ STL 的 LowerBound() 以获取元素在向量中的位置，其中元素等于给定元素 x。
4. 从这个元素开始，将大于 x 的元素减少 1，直到从对中的索引开始在原始数组中结束。
5. 对每个 x 重复步骤 3 和 4。
6. 打印原始数组。

我认为我的解决方案复杂度为 n^2。

谁能给我一个优化的解决方案

谢谢

我的代码