线段树的应用：有编号是1~n的n头牛（n个数字），2 <= n <= 8,000，乱序排列，顺序未知。对每个位置的数字，知道排在它前面比它小的数字有多少个。求这个乱序数列的顺序。

这道题可以使用归并排序和线段树来解决，其中线段树的应用比较巧妙。

首先，我们需要定义一个结构体来存储每个数字的值以及它前面比它小的数字的个数：

struct node {
    int val;
    int smaller;
};

然后，我们可以使用归并排序来统计每个数字前面比它小的数字的个数。在归并排序的过程中，我们可以记录左边区间的数字比右边区间的数字先出列，因此左边区间的数字对右边区间的数字构成了逆序对。对于每个数字，它前面比它小的数字的个数就是它在归并排序中经过的逆序对的个数。我们可以使用一个数组 `smaller` 来记录每个数字的这个值。

接下来，我们需要将这个乱序数列的顺序求出来。我们可以使用一个线段树来实现这个过程。线段树的每个节点表示区间 `[l, r]` 内的数字，其中 `l` 和 `r` 分别表示区间的左右端点。我们可以在每个节点中记录区间内的数字的排列顺序。对于一个区间 `[l, r]`，如果它的左右端点相等，那么这个区间内只有一个数字，它的排列顺序就是它的编号。否则，我们可以将区间 `[l, mid]` 和 `[mid+1, r]` 分别递归地建立线段树，并记录它们的排列顺序。然后，我们可以将这两个区间内的数字按照 `smaller` 数组中的值进行归并排序，得到当前区间内数字的排列顺序。最后，我们将这个排列顺序存储在当前节点中，并返回它。递归地建立线段树后，根节点中存储的就是整个乱序数列的顺序。

代码实现如下：

相关问题

现在增加提示：1<=n<=100000 1<=L<=1000000000 0<=x<=y<=1000000000，请你用C++代码写出这道题

以下是用 C++ 语言编写的程序，可以通过本题：

#include <iostream>
#include <algorithm>

using namespace std;

struct Segment {
    int l, r;
    bool operator < (const Segment& other) const {
        return l < other.l;
    }
} seg[100005];

int main() {
    int n, L;
    cin >> n >> L;

    for (int i = 0; i < n; i++) {
        int x, y;
        cin >> x >> y;
        seg[i].l = max(1, x - y);
        seg[i].r = min(L, x + y);
    }

    sort(seg, seg + n);

    int ans = 0, cur = 0, i = 0;
    while (cur < L) {
        int mx = cur;
        while (i < n && seg[i].l <= cur + 1) {
            mx = max(mx, seg[i].r);
            i++;
        }
        if (mx == cur) {
            cout << -1 << endl;
            return 0;
        }
        cur = mx;
        ans++;
    }

    cout << ans << endl;

    return 0;
}

程序的思路如下：

首先，读入所有的线段，对于每个线段，计算出该线段在范围 [1, L] 内的有效部分。

然后，按照线段左端点从小到大排序。

接着，从左往右枚举每个点，维护一个变量 mx 表示当前点能够到达的最远位置，如果当前点无法到达任何新的位置，则输出 -1。

最后，输出能够到达的点数。

时间复杂度为 O(n log n)。

线段树数组为啥是4n数学严格证明

线段树数组通常用于高效地支持区间查询和修改操作，它的空间复杂度通常是O(n)，其中n是数据的数量。为什么说它占用的空间是4n呢，这里有一个简单的数学解释：

线段树通常分为两个部分：节点和指针。每个节点代表区间的值，需要存储两个关键信息：区间的起始和结束位置。在完全二叉树结构下，对于深度为k的树，最底层有2^k个节点，因为每一层的节点数都是上一层的一倍。对于每一个节点，我们需要额外的指针来链接左右孩子，这又增加了2个元素。

所以，对于每层，我们有2^(k+1) = 2 * 2^k = 2n个元素（n是层数）。当k=0（根节点），元素数量是2；随着层数增加，每次翻倍。因此，总的空间需求是：

- 根节点(第0层)：2n = 2
- 所有其他层级(从第1层到第k层)：(2n - 2) * k (因为除了根节点剩下的k-1层)

将这两部分相加，得到：

总空间 = 2 + (2n - 2) * k = 2 + 2n * k - 2k = 2nk - 2(k-1) = 2n * k

如果取最大深度k=log2n（以保证所有数据都能覆盖到），那么总空间就是2n * log2n，接近于4n（因为log2n ≈ 2）。这里的“接近”是因为实际计算中会舍去常数项，但直观上可以认为线段树数组占用的空间大约是4倍的数据量。