{"id":189,"date":"2024-04-26T17:03:34","date_gmt":"2024-04-26T09:03:34","guid":{"rendered":"https:\/\/seanxd.com\/?p=189"},"modified":"2024-04-26T17:03:36","modified_gmt":"2024-04-26T09:03:36","slug":"zerojudge-e457","status":"publish","type":"post","link":"https:\/\/seanxd.com\/en\/zerojudge-e457\/","title":{"rendered":"ZeroJudge E457: Segment Tree Practice"},"content":{"rendered":"\n\n\n

\u540c\u984c\uff1aUVa 12532 – Interval Product<\/h4>\n\n\n\n

\u6700\u591a N = 105<\/sup> \u500b\u6578\u5b57 X1<\/sub> … XN<\/sub>\uff0cK \u500b\u8a62\u554f {\u53ea\u6709\u5169\u7a2e\u683c\u5f0f} CIV \u6216 PIJ<\/p>\n\n\n\n

CIV \u662f\u5c07 Xi <\/sub>\u7684\u503c\u6539\u70ba V\uff0c PIJ \u662f\u554f Xi\u00a0<\/sub>~ Xj <\/sub>\u9023\u7e8c\u4e58\u7a4d\u7684\u7b26\u865f {\u6b63\u3001\u8ca0\u3001\u6216 0} \u8f38\u51fa +-0<\/p>\n\n\n\n

\u6709\u591a\u7d44\u6e2c\u8cc7\uff0c\u6bcf\u7d44\u8f38\u51fa\u4e00\u5217\uff0c\u8acb\u53c3\u8003\u7bc4\u4f8b<\/p>\n\n\n\n

\u7bc4\u4f8b\u6e2c\u8cc7<\/h2>\n\n\n\n
\u7bc4\u4f8b\u8f38\u5165<\/th>\u7bc4\u4f8b\u8f38\u51fa<\/th><\/tr><\/thead>
EOF<\/strong> \u8f38\u5165\uff0c\u6bcf\u7b46\u8cc7\u6599\u7b2c\u4e00\u884c\u6709\u5169\u500b\u6b63\u6574\u6578 N \u548c M<\/strong>\uff0c\u7b2c\u4e8c\u884c\u6703\u6709 N \u500b\u6578\u5b57\u4ee3\u8868\u6578\u5217\u4e2d\u7684\u6578\u3002\u63a5\u4e0b\u4f86\u6703\u6709 M \u884c\uff0c\u6bcf\u884c\u6703\u6709\u4e00\u500b\u5b57\u5143\u548c\u5169\u500b\u6574\u6578 A \u548c B\u3002<\/td>\u7576\u5b57\u5143\u70ba C \u6642\uff0c\u5c07\u6578\u5217\u4e2d\u7b2c A \u500b\u4f4d\u7f6e\u7684\u8cc7\u6599\u6539\u70ba B\u3002\u7576\u5b57\u5143\u70ba P \u6642\uff0c\u5982\u679c\u4f4d\u7f6e A \u5230 B \u7684\u4e58\u7a4d\u70ba\u6b63\u7684\u8a71\u8f38\u51fa\u300c+\u300d\uff0c\u8ca0\u7684\u8a71\u8f38\u51fa\u300c-\u300d\uff0c0\u7684\u8a71\u5247\u8f38\u51fa\u300c0\u300d\u3002<\/td><\/tr>
4 6<\/strong>
-2 6 0 -1
C 1 10
P 1 4
C 3 7
P 2 2
C 4 -5
P 1 4
5 9<\/strong>
1 5 -2 4 3
P 1 2
P 1 5
C 4 -5
P 1 5
P 4 5
C 3 0
P 1 5
C 4 -5
C 4 -5<\/td>		0+-
+-+-0<\/td><\/tr><\/tbody><\/table>
ZeroJudge E457 \u7bc4\u4f8b\u6e2c\u8cc7<\/figcaption><\/figure>\n\n\n\n

\u89e3\u984c\u601d\u8def<\/h2>\n\n\n\n

\u5efa\u7acb\u7dda\u6bb5\u6a39\u7684\u8cc7\u6599\u7d50\u69cb\u4f86\u66f4\u6539\u8cc7\u6599\u53ca\u78ba\u8a8d\u5340\u6bb5\u7684\u4e58\u7a4d\u3002(\u7bc4\u4f8b\u7a0b\u5f0f\u78bc\u5167\u6709\u8a3b\u89e3\u4f86\u89e3\u91cb\u641c\u5c0b\u539f\u7406)<\/p>\n\n\n\n

\u7bc4\u4f8b\u7a0b\u5f0f\u78bc\uff0dZeroJudge E457: \u4e5f\u662f Segment Tree \u7df4\u7fd2<\/a><\/h3>\n\n\n\n
#include <iostream>\n#include <vector>\nusing namespace std;\n\nvector<int>num;\nvector<int>tree;\n\nvoid build(int l, int r, int id)\n{\n    if (l == r)\n    {\n        if(num[l] > 0) tree[id] = 1;\n        else if(num[l] < 0) tree[id] = -1;\n        else tree[id] = 0;\n        return;\n    }\n    int middle = (l+r)\/2;\n    int L = id*2+1;\n    int R = id*2+2;\n    build(l, middle, L);\n    build(middle+1, r, R);\n    if((tree[L] < 0 and tree[R] < 0) or (tree[L] > 0 and tree[R] > 0)) tree[id] = 1;\n    else if((tree[L] < 0 and tree[R] > 0) or (tree[L] > 0 and tree[R] < 0)) tree[id] = -1;\n    else tree[id] = 0;\n}\n\nvoid change(int pos, long long int val, int l, int r, int id)\n{\n    if (l == r)\n    {\n        tree[id] = val;\n        if(val > 0) { tree[id] = 1; num[l] = 1; }\n        else if(val < 0) {tree[id] = -1;  num[l] = -1;}\n        else {tree[id] = 0; num[l] = 0;}\n        return;\n    }\n    int m = (l+r)\/2;\n    if (pos <= m) change(pos, val, l, m, (id*2)+1);\n    else change(pos, val, m+1, r, (id*2)+2);\n    tree[id] = tree[id*2+1] * tree[id*2+2];\n}\n\nint search(int l, int r , int L , int R , int id)\n{\n    if (l == r) return num[l];\n    if (l == L && r == R) {\n        return tree[id];\n    }\n    int m = (L+R)\/2; \/\/\u4e2d\u9593\u9ede --> \u5de6\u534a\u908a\uff1aL~m\uff1b\u53f3\u534a\u908a\uff1am+1~R\n    if (r <= m) \/\/l\u8ddfr\u90fd\u5c0f\u65bcm (\u56e0\u70bar\u6709\u5c0f\u65bcm\u7684\u8a71l\u5c31\u4e00\u5b9a\u6703\u5c0f\u65bcm) --> \u8981\u627e\u7684\u8cc7\u6599\u90fd\u5728\u5de6\u534a\u908a\n    {\n        return search(l, r, L, m , id*2+1);\n    }\n    else if (l > m) \/\/l\u8ddfr\u90fd\u5927\u65bcm (\u56e0\u70bal\u6709\u5927\u65bcm\u7684\u8a71r\u5c31\u4e00\u5b9a\u6703\u5927\u65bcm) --> \u8981\u627e\u7684\u8cc7\u6599\u90fd\u5728\u53f3\u534a\u908a\n    {\n        return search(l, r, m+1, R , id*2+2);\n    }\n    else \/\/\u5169\u908a\u90fd\u6709\u9700\u8981\u627e\u7684\u6771\u897f\n    {\n        return search(l, m, L, m , id*2+1) * search(m+1, r, m+1, R , id*2+2);\n    }\n}\n\n\nint main() {\n    int N, M;\n    while (cin >> N >> M)\n    {\n        num.clear();\n        tree.clear();\n        for(int i = 0; i<(2*N)-1; i++)\n        {\n            tree.push_back(0);\n        }\n        for (int i = 0; i<N; i++)\n        {\n            int tmp;\n            cin >> tmp;\n            num.push_back(tmp);\n        }\n        build(0, N-1, 0);\n        for (int i = 0; i<M; i++)\n        {\n            char ch;\n            cin >> ch;\n            if (ch == 'C')\n            {\n                int pos, val;\n                cin >> pos >> val;\n                change(pos-1, val, 0, N-1, 0);\n            }\n            else\n            {\n                int l, r;\n                cin >> l >> r;\n                int tmp = search(l-1, r-1, 0, N-1 , 0);\n                if (tmp > 0) cout << '+';\n                else if (tmp < 0) cout << '-';\n                else cout << '0';\n            }\n        }\n        cout << "\\n";\n    }\n}\n\n\/\/ZeroJudge E457\n\/\/Dr. SeanXD<\/code><\/pre><\/div>\n","protected":false},"excerpt":{"rendered":"
\u540c\u984c\uff1aUVa 12532 – Interval Product \u6700\u591a N = 105 \u500b\u6578\u5b57 X1 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"nf_dc_page":"","footnotes":""},"categories":[18],"tags":[20,8,11,13,31,9],"class_list":["post-189","post","type-post","status-publish","format-standard","hentry","category-uva","tag-20","tag-8","tag-11","tag-13","tag-31","tag-9"],"blocksy_meta":[],"_links":{"self":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/189","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/comments?post=189"}],"version-history":[{"count":2,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/189\/revisions"}],"predecessor-version":[{"id":191,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/posts\/189\/revisions\/191"}],"wp:attachment":[{"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/media?parent=189"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/categories?post=189"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/seanxd.com\/en\/wp-json\/wp\/v2\/tags?post=189"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}