{"id":146,"date":"2022-06-21T12:10:34","date_gmt":"2022-06-21T04:10:34","guid":{"rendered":"https:\/\/vite66.cn\/?p=146"},"modified":"2025-01-11T16:57:50","modified_gmt":"2025-01-11T08:57:50","slug":"%e5%8a%a8%e6%80%81%e5%bc%80%e7%82%b9%e7%ba%bf%e6%ae%b5%e6%a0%91","status":"publish","type":"post","link":"https:\/\/vite66.cn\/?p=146","title":{"rendered":"\u52a8\u6001\u5f00\u70b9\u7ebf\u6bb5\u6811"},"content":{"rendered":"

\u52a8\u6001\u5f00\u70b9\u7ebf\u6bb5\u6811\u539f\u7406<\/a><\/p>\n

\u4f8b\u9898 1<\/h3>\n

\u7edf\u8ba1\u533a\u95f4\u4e2d\u7684\u6574\u6570\u6570\u76ee<\/a><\/p>\n

#define ls(x) tr[x].L\n#define rs(x) tr[x].R\nclass CountIntervals {\n    static const int N = 8e5 + 5;\n    struct node{\n        int l, r, cnt = 0;\n        int L = -1, R = -1;\n    }tr[N];\n    int idx = 1;\n    void push_up(int u) {\n        tr[u].cnt = 0;\n        if (ls(u) != -1) {\n            tr[u].cnt += tr[ls(u)].cnt;\n        }\n        if (rs(u) != -1) {\n            tr[u].cnt += tr[rs(u)].cnt;\n        }\n    }\n    void add2(int u, int l, int r) {\n        if (tr[u].l == tr[u].r) {\n            tr[u].cnt = 1;\n            return;\n        }\n        if (l <= tr[u].l && r >= tr[u].r) {\n            tr[u].cnt = tr[u].r - tr[u].l + 1;\n            return;\n        }\n        if (tr[u].cnt == tr[u].r - tr[u].l + 1) return;\n        int mid = (tr[u].l + tr[u].r) >> 1;\n\n        if (l <= mid) {\n            int& L = ls(u);\n            if (L == -1) {\n                L = idx ++;\n                tr[L] = {tr[u].l, mid};\n            }\n            add2(L, l, r);\n        }\n        if (r > mid) {\n            int& R = rs(u);\n            if (R == -1) {\n                R = idx ++;\n                tr[R] = {mid + 1, tr[u].r};\n            }\n            add2(R, l, r);\n        }\n        push_up(u);\n    }\n\npublic:\n    CountIntervals() {\n        tr[idx ++] = {1, 1000000005, 0};\n    }\n\n    void add(int left, int right) {\n        add2(1, left, right);\n        \/\/ cout << idx << endl;\n    }\n\n    int count() {\n        \/\/ cout << idx << endl;\n        return tr[1].cnt;\n    }\n};\n\n\/**\n * Your CountIntervals object will be instantiated and called as such:\n * CountIntervals* obj = new CountIntervals();\n * obj->add(left,right);\n * int param_2 = obj->count();\n *\/<\/code><\/pre>\n
\u4f8b\u9898 2<\/h3>\n
Range \u6a21\u5757<\/a><\/p>\n
#define ls(u) tr[u].L\n#define rs(u) tr[u].R\nclass RangeModule {\n    static const int N = 1E6;\n    struct node{\n        int l, r;\n        int L, R;\n        int sum = 0;\n        int f = 0;\n    }tr[4 * N];\n    int idx = 1;\n    void push_up(int u) {\n        tr[u].sum = tr[ls(u)].sum + tr[rs(u)].sum;\n    }\n    void push_dowm(int u) {\n        int& L = ls(u), &R = rs(u);\n        if (!L) {\n            L = ++ idx;\n            tr[L] = {tr[u].l, tr[u].l + tr[u].r >> 1};\n        }\n        if (!R) {\n            R = ++ idx;\n            tr[R] = {(tr[u].l + tr[u].r >> 1) + 1, tr[u].r};\n        }\n\n        if (tr[u].f == 0) return;\n        else if (tr[u].f == -1) {\n            tr[L].sum = 0;\n            tr[R].sum = 0;\n        }else {\n            int len = tr[u].r - tr[u].l + 1;\n            tr[L].sum = len - len \/ 2;\n            tr[R].sum = len \/ 2;\n        }\n        tr[L].f = tr[u].f;\n        tr[R].f = tr[u].f;\n        tr[u].f = 0;\n    }\n    void update(int u, int l, int r, int f) {\n        if (l <= tr[u].l && tr[u].r <= r) {\n            tr[u].f = f;\n            if (f == 1)\n                tr[u].sum = tr[u].r - tr[u].l + 1;\n            else tr[u].sum = 0;\n            return;\n        }\n        int mid = tr[u].r + tr[u].l >> 1;\n        push_dowm(u);\n        if (l <= mid) update(ls(u), l, r, f);\n        if (r > mid) update(rs(u), l, r, f);\n        push_up(u);\n    }\n    int query(int u, int l, int r) {\n        if (l <= tr[u].l && tr[u].r <= r) {\n            return tr[u].sum;\n        }\n        int mid = tr[u].l + tr[u].r >> 1;\n        push_dowm(u);\n        int ret = 0;\n        if (l <= mid) ret += query(ls(u), l, r);\n        if (r > mid) ret += query(rs(u), l, r);\n        return ret;\n    }\npublic:\n    RangeModule() {\n        tr[1] = {1, 1000000005};\n    }\n\n    void addRange(int left, int right) {\n        update(1, left, right - 1, 1);\n    }\n\n    bool queryRange(int left, int right) {\n        \/\/ if (left == 13 && right == 15) cout << query(1, 13, 14) << endl;\n        return query(1, left, right - 1) == (right - left);\n    }\n\n    void removeRange(int left, int right) {\n        update(1, left, right - 1, -1);\n    }\n};\n\n\/**\n * Your RangeModule object will be instantiated and called as such:\n * RangeModule* obj = new RangeModule();\n * obj->addRange(left,right);\n * bool param_2 = obj->queryRange(left,right);\n * obj->removeRange(left,right);\n *\/<\/code><\/pre>\n","protected":false},"excerpt":{"rendered":"
\u52a8\u6001\u5f00\u70b9\u7ebf\u6bb5\u6811\u539f\u7406 \u4f8b\u9898 1 \u7edf\u8ba1\u533a\u95f4\u4e2d\u7684\u6574\u6570\u6570\u76ee #define ls(x) tr[x].L #define […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[7],"tags":[26,19,25,20],"class_list":["post-146","post","type-post","status-publish","format-standard","hentry","category-science-and-engineering","tag-26","tag-data-structure","tag-algorithm-templates","tag-segment-tree"],"_links":{"self":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/146","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=146"}],"version-history":[{"count":2,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/146\/revisions"}],"predecessor-version":[{"id":148,"href":"https:\/\/vite66.cn\/index.php?rest_route=\/wp\/v2\/posts\/146\/revisions\/148"}],"wp:attachment":[{"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=146"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=146"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/vite66.cn\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=146"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}