人类不应该使用 std::vector 实现线段树的 2 个原因：
- 当你的参数包含引用时，扩容操作，包括显式的
resize()和隐式的push_back()均会导致引用失效。 - 当你的左值为引用时，由于
=左右计算顺序是不确定的（C++14），由于 1 中所述原因，引用可能失效。 terminate called after throwing an instance of 'std::bad_alloc' what(): std::bad_alloc
笑点解析：首先通过「……的 2 个原因」暗示声明一个长度为 2 的
vector，接着在试图访问第 3 个元素时抛出错误。
什么？你说我的下标是从 1 开始的？恭喜你发现了 vector
的第 0 个笑点。
楼房重建
https://www.luogu.com.cn/problem/P4198
考虑用线段树解决问题。难点在于如何合并两个区间的信息——直觉地，大区间的信息一定与两个子区间有关。
考虑理想的情况：我们现在知道左右两边区间的答案序列。显然我们需要保留左边整段区间，对于左区间序列末的元素 \(rv_l\)，我们在右区间内找到第一个大于之的元素 \(x\)，从它开始的序列就是答案。
反证法易得 \(x\) 一定在右区间答案序列内：若 \(x\) 不在答案序列内，则右区间内存在一个 \(>x\) 且位于 \(x\) 之前的元素，那么 \(x\) 就不是第一个 \(>rv_l\) 的元素，矛盾。
那么现在对于左右序列未知的情况，我们取左区间的答案，再在右区间中单 \(\log\) 查找能够接上去的区间长度，加起来即可。
题目只要求总区间答案，故不需要查询。动态开点可能需要小心处理一下。
#include <bits/stdc++.h>
const int maxn = 1e5 + 5;
struct {
int l, r, u;
double lv, rv, mv;
} t[maxn << 2];
int tot;
#define lt t[p].l
#define rt t[p].r
int askt(int p, int l, int r, double v) {
if (l == r)
return t[p].u;
int mid = (l + r) >> 1;
if (lt && t[p].mv > v)
return t[p].u - t[lt].u + askt(lt, l, mid, v);
return askt(rt, mid + 1, r, v);
}
void pushup(int p, int l, int r) {
t[p].mv = t[lt].rv;
if (lt && rt) {
t[p].lv = t[lt].lv;
t[p].rv = std::max(t[lt].rv, t[rt].rv);
if (t[lt].rv < t[rt].lv)
t[p].u = t[lt].u + t[rt].u;
else if (t[lt].rv >= t[rt].rv)
t[p].u = t[lt].u;
else {
int mid = (l + r) >> 1;
t[p].u = t[lt].u + askt(rt, mid + 1, r, t[lt].rv);
}
}
else {
t[p].u = t[lt + rt].u;
t[p].lv = t[lt + rt].lv, t[p].rv = t[lt + rt].rv;
}
return;
}
void upd(int &p, int l, int r, int x, double v) {
if (!p)
p = ++tot;
if (l == r) {
t[p].lv = t[p].rv = v, t[p].u = 1;
return;
}
int mid = (l + r) >> 1;
if (x <= mid)
upd(lt, l, mid, x, v);
else
upd(rt, mid + 1, r, x, v);
pushup(p, l, r);
return;
}
#undef lt
#undef rt
int main() {
#ifdef ONLINE_JUDGE
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr), std::cout.tie(nullptr);
#else
std::freopen("P4198_2.in", "r", stdin);
std::freopen(".out", "w", stdout);
#endif
int n, m, rt = 0;
std::cin >> n >> m;
std::vector<double> a(n + 1);
for (int x; m--; ) {
double y;
std::cin >> x >> y;
a[x] = y / x;
upd(rt, 1, n, x, y / x);
std::cout << t[1].u << '\n';
}
return 0;
}