{"id":60,"date":"2011-08-29T05:21:19","date_gmt":"2011-08-28T21:21:19","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=60"},"modified":"2012-03-03T05:23:08","modified_gmt":"2012-03-02T21:23:08","slug":"spoj-2916-can-you-answer-these-queries-v","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/spoj-2916-can-you-answer-these-queries-v\/","title":{"rendered":"SPOJ 2916. Can you answer these queries V"},"content":{"rendered":"

https:\/\/www.spoj.pl\/problems\/GSS5\/<\/a><\/p>\n

\u3002\u6700\u8fd1\u91cd\u5199\u4e86\u4e00\u4e0b GSS3 .. \u6ca1\u52a0\u4efb\u4f55\u4f18\u5316\u4ea4 GSS1 \u5c31\u8fc7\u6389\u4e86 \u3002\u3002\u4ee5\u524d\u662f\u8981\u8d85\u65f6\u7684\u3002\u3002
\n\u6211\u7684\u8fd9\u79cd\u5199\u6cd5\u4e0d\u5bb9\u6613\u51fa\u9519\u3002\u3002\u800c\u4e14\u5f88\u5bb9\u6613\u63a8\u5230 GSS5 \u3002\u3002\u3002> < \u3002\u3002\u8ba8\u8bba\u53ea\u8981\u5206\u4e09\u79cd\u5c31\u53ef\u4ee5\u4e86\u554a\u3002\u3002\u8d8a\u5c11\u8d8a\u597d\u561b\u3002\n\n<\/p>\n

\r\n\/** ` Micro Mezzo Macro Flation -- Overheated Economy ., **\/\r\n#include <iostream>\r\n#include <cstdio>\r\nusing namespace std;\r\n#define REP_1_C(i, n) for (int n____=int(n),i=1;i<=n____;++i)\r\n#define DO(n) while(n--)\r\n#define DO_C(n) int n____ = n; while(n____--)\r\n#define Rush int T____; RD(T____); DO(T____)\r\ntemplate<class T> inline void RD(T &);\r\ntemplate<class T> inline void OT(const T &);\r\ntemplate<class T> inline T& _RD(T &x){ RD(x); return x;}\r\ninline int RD(){ int x; RD(x); return x;}\r\ntemplate<class T0, class T1, class T2, class T3> inline void RD(T0 &x0, T1 &x1, T2 &x2, T3 &x3){RD(x0), RD(x1), RD(x2), RD(x3);}\r\ntemplate<class T> inline T max(T a, T b, T c){return max(max(a, b), c);}\r\ntemplate<class T> inline void RD(T &x){scanf("%d", &x);}\r\ntemplate<class T> inline void OT(const T &x){printf("%d\\n", x);}\r\n\r\n\/* .................................................................................................................................. *\/\r\n\r\nconst int N = 10001;\r\n\r\nstruct Seg{\r\n    int ss, ls, rs, ms;\r\n} T[4*N];\r\nint A[N], n, a, b;\r\n\r\n#define root 1, 1, n\r\n#define lx (x << 1)\r\n#define rx (lx + 1)\r\n#define lc lx, l, m\r\n#define rc rx, m+1, r\r\n\r\nvoid Update(Seg &x, Seg l, Seg r){\r\n    x.ss = l.ss + r.ss;\r\n    x.ls = max(l.ls, l.ss + r.ls);\r\n    x.rs = max(r.rs, r.ss + l.rs);\r\n    x.ms = max(l.ms, r.ms, l.rs + r.ls);\r\n}\r\n\r\nvoid Build(int x, int l, int r){\r\n\r\n    if (l == r){\r\n        T[x].ss = T[x].ls = T[x].rs = T[x].ms = A[l];\r\n    }\r\n    else{\r\n        int m = (l + r) >> 1;\r\n        Build(lc), Build(rc);\r\n        Update(T[x], T[lx], T[rx]);\r\n    }\r\n}\r\n\r\nSeg _Query(int x, int l, int r){\r\n    if (a <= l && r <= b)\r\n        return T[x];\r\n    else {\r\n        int m = (l + r) >> 1;\r\n        if (b <= m) return _Query(lc); if (m < a) return _Query(rc);\r\n        Seg res; Update(res, _Query(lc), _Query(rc)); return res;\r\n    }\r\n}\r\n\r\nSeg Query(int _a, int _b){\r\n    if (_a > _b) return T[0];\r\n    a = _a, b = _b;\r\n    return _Query(root);\r\n}\r\n\r\nint main(){\r\n\r\n    \/\/freopen("in.txt", "r", stdin);\r\n    \/\/freopen("out.txt", "w", stdout);\r\n    \/\/ios::sync_with_stdio(false);\r\n\r\n    Rush{\r\n        REP_1_C(i, _RD(n)) RD(A[i]);\r\n        Build(root);\r\n\r\n        int x1, y1, x2, y2; DO_C(RD()){\r\n            RD(x1, y1, x2, y2);\r\n            if (y1 < x2) OT( Query(x1, y1).rs + Query(y1 + 1, x2 - 1).ss + Query(x2, y2).ls );\r\n            else OT( max( Query(x2, y1).ms, Query(x1, x2-1).rs + Query(x2, y2).ls, Query(x1, y1).rs + Query(y1+1, y2).ls) );\r\n        }\r\n    }\r\n\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
https:\/\/www.spoj.pl\/problems\/GSS5\/ \u3002\u6700\u8fd1\u91cd\u5199\u4e86\u4e00\u4e0b GSS3 .. \u6ca1\u52a0\u4efb\u4f55\u4f18\u5316\u4ea4 GSS1 \u5c31\u8fc7\u6389\u4e86 \u3002\u3002\u4ee5\u524d\u662f\u8981\u8d85\u65f6\u7684\u3002\u3002 \u6211\u7684\u8fd9\u79cd\u5199\u6cd5\u4e0d\u5bb9\u6613\u51fa\u9519\u3002\u3002\u800c\u4e14\u5f88\u5bb9\u6613\u63a8\u5230 GSS5 \u3002\u3002\u3002> < \u3002\u3002\u8ba8\u8bba\u53ea\u8981\u5206\u4e09\u79cd\u5c31\u53ef\u4ee5\u4e86\u554a\u3002\u3002\u8d8a\u5c11\u8d8a\u597d\u561b\u3002\n<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":false,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[21],"tags":[43,30],"class_list":["post-60","post","type-post","status-publish","format-standard","hentry","category-spoj","tag-43","tag-30"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-Y","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/60","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/comments?post=60"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/60\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=60"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=60"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=60"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}