struct tnode { int l, r; int mins; }; struct Segment { tnode t[4 * N]; int fa[4 * N]; void built(int root, int l, int r) { """ 构建线段树 :param root: 当前节点 :param l: 左端点 :param r: 右端点 """ t[root].l = l; t[root].r = r; if (l == r) { t[root].mins = 0; fa[l] = root; return; } int ch = root << 1; int mid = (l + r) >> 1; built(ch, l, mid); built(ch + 1, mid + 1, r); t[root].mins = min(t[ch].mins, t[ch + 1].mins); } void modify(int num, int pos) { """ 修改线段树 :param num: 要修改的位置 :param pos: 要修改的值 """ int root = fa[num]; t[root].mins = pos; root >>= 1; while (root) { int ch = root << 1; t[root].mins = min(t[ch].mins, t[ch + 1].mins); root >>= 1; } } int query(int l) { """ 查询线段树 :param l: 查询的左端点 :return: 最小的未被覆盖的位置 """ int root = 1; while (t[root].l != t[root].r) { int ch = root << 1; if (t[ch].mins >= l) { root = ch + 1; } else { root = ch; } } return t[root].l - 1; } } ST; // int main() { // // 初始化线段树,假设值范围是1到n // int n; // cin >> n; // ST.built(1, 1, n); // // 示例:处理m次操作 // int m; // cin >> m; // while (m--) { // int op, x, y; // cin >> op; // if (op == 1) { // cin >> x >> y; // ST.modify(x, y); // } else if (op == 2) { // cin >> x; // cout << ST.query(x) << '\n'; // } // } // }