//Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and 
// description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are:
// $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the 
// same ids are connected.
// prefix 的格式要求是 acm-[一级标题编号].[二级标题编号][该代码片段的英文简称]
// description 的格式要求是 "插入 [该代码片段的中文名]"

{
    "线段树- mex": {
        "prefix": "acm-2.6segment-tree-mex",
        "body": [
            "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';",
            "//         }",
            "//     }",
            "// }"
        ],
        "description": "插入 线段树- mex"
    }
}