题目中的坐标范围是[0,1e9]。我的线段树维护的是区间内所有青蛙的最大捕食位置，每次加入蚊子后二分查找完当前蚊子会对哪只青蛙产生影响，然后再计算后续影响，最后修改当前青蛙的最大捕食位置。由于我默认不存在青蛙的位置的最大捕食位置为0，所以当有在0处的蚊子加入后，就一定会被在0处的青蛙捕食，不过这个青蛙是不一定存在的，后面的蚊子就可能会被这只虚空青蛙吃掉~线段树的具体实现如下：```cpp struct node { int maxVal, ch[2]; } tr[N * 100]; int cnt, rt;

void modify(int &x, int l, int r, int pos, int val) { if (!x) x = ++cnt; tr[x].maxVal = max(tr[x].maxVal, val); if (l == r) return; int m = l + r >> 1; if (pos <= m) modify(lc(x), l, m, pos, val); else modify(rc(x), m + 1, r, pos, val); }

int qPos(int x, int l, int r, int ql, int qr, int lim) { if (!x) // 这一段很重要~如果没有这个判断，可能会在0处生成一只青蛙~ return -1; // 这只青蛙自带破坏属性 不过可以通过将线段树的maxVal初始化为-1解决 if (ql <= l && qr >= r) { if (tr[x].maxVal < lim) return -1; } if (l == r) return l; int m = l + r >> 1; if (ql <= m) { int pos = qPos(lc(x), l, m, ql, qr, lim); if (pos != -1) return pos; } if (qr > m) { int pos = qPos(rc(x), m + 1, r, ql, qr, lim); if (pos != -1) return pos; } return -1; }