{"id":80,"date":"2011-03-16T07:54:46","date_gmt":"2011-03-15T23:54:46","guid":{"rendered":"http:\/\/www.shuizilong.com\/house\/?p=80"},"modified":"2012-03-03T07:55:02","modified_gmt":"2012-03-02T23:55:02","slug":"poi-2006-tet-tetris-3d","status":"publish","type":"post","link":"https:\/\/www.shuizilong.com\/house\/archives\/poi-2006-tet-tetris-3d\/","title":{"rendered":"[POI 2006] Tet-Tetris 3D"},"content":{"rendered":"

Brief description :<\/h3>\n

\u4e8c\u7ef4 RMQ\u3002
\n<\/p>\n

Analyse :<\/h3>\n

..?<\/p>\n

Area_Tree..<\/p>\n

\r\n#include \r\nusing namespace std;  \r\nconst int nn = 1024, ll = 1398101; \/\/4 * nn * nn;\r\n\r\nint Xl[ll], Xr[ll], Yl[ll], Yr[ll];\r\nint Key[ll]; bool Close[ll];\r\nint LeftDown[ll], LeftUp[ll], RightDown[ll], RightUp[ll];\r\nint root, total; \/\/ Area-Tree\r\nint xl, xr, yl, yr, v;\r\nint n, m, q;\r\n\r\nvoid _R(int &x){\r\n\tif (!((x & -x) == x)){\r\n\t\tdo {\r\n\t\t\tx ^= x & -x;\r\n\t\t} while ((x & -x) != x);\r\n\t\tx <<= 1;\r\n\t}\r\n}\r\n\r\nvoid Open(int now){\r\n\tClose[LeftDown[now]] = Close[LeftUp[now]] = Close[RightDown[now]] = Close[RightUp[now]] = true;\r\n             \/\/.. key...#\r\n\tClose[now] = false;\r\n}\r\n\r\nvoid Build(int &now, int xl, int xr, int yl, int yr){\r\n\tnow = total++, Xl[now] = xl, Xr[now] = xr, Yl[now] = yl, Yr[now] = yr;\r\n\tKey[now] = 0, Close[now] = true;\r\n\t\r\n\t\/\/cout << xl << \" \" << xr << \" \" << yl << \" \" << yr << endl;\r\n\t\r\n\tif (!(xl == xr && yl == yr)){\r\n\t\tint xm = (xl + xr) \/ 2, ym = (yl + yr) \/ 2;\r\n\t\tBuild(LeftDown[now], xl, xm, yl, ym);\r\n\t\tBuild(LeftUp[now], xl, xm, ym+1, yr);\r\n\t\tBuild(RightDown[now], xm+1, xr, yl, ym);\r\n\t\tBuild(RightUp[now], xm+1, xr, ym+1, yr);\r\n\t}\r\n}\r\n\r\nint Query(int now){\r\n\tif (Close[now] || (xl <= Xl[now] && Xr[now] <= xr && yl <= Yl[now] && Yr[now] <= yr))\r\n\t\treturn Key[now];\r\n\t\r\n\tint xm = (Xl[now] + Xr[now]) \/ 2, ym = (Yl[now] + Yr[now]) \/ 2, res = -1;\r\n\t\r\n\tif (xl <= xm && yl <= ym) res = max(res, Query(LeftDown[now]));\r\n\tif (xl <= xm && ym < yr && Key[LeftUp[now]] > res) res = max(res, Query(LeftUp[now]));\r\n\tif (xm < xr && yl <= ym && Key[RightDown[now]] > res) res = max(res, Query(RightDown[now]));\r\n\tif (xm < xr && ym < yr && Key[RightUp[now]] > res) res = max(res, Query(RightUp[now]));\r\n\t\r\n\treturn res;\r\n}\r\n\r\nvoid Insert(int now){\r\n\t\r\n\tKey[now] = max(Key[now], v);\r\n\t\r\n\tif (xl <= Xl[now] && Xr[now] <= xr && yl <= Yl[now] && Yr[now] <= yr){\r\n\t\tClose[now] = true;\r\n\t\treturn;\r\n\t}\r\n\t\r\n\tif (Close[now]) Open(now);\r\n\t\r\n\tint xm = (Xl[now] + Xr[now]) \/ 2, ym = (Yl[now] + Yr[now]) \/ 2;\r\n\t\r\n\tif (xl <= xm && yl <= ym) Insert(LeftDown[now]);\r\n\tif (xl <= xm && ym < yr) Insert(LeftUp[now]);\r\n\tif (xm < xr && yl <= ym) Insert(RightDown[now]);\r\n\tif (xm < xr && ym < yr) Insert(RightUp[now]);\r\n}\r\n\r\nint main(){\r\n\t\/\/freopen(\"in.txt\", \"r\", stdin);\r\n\tscanf(\"%d%d%d\", &n, &m, &q), _R(n), _R(m);\r\n\tBuild(root, 1, n, 1, m);\r\n\tint d, s, w, x, y;\r\n\tfor (int i = 0; i < q; i ++){\r\n\t\tscanf(\"%d%d%d%d%d\", &d, &s, &w, &x, &y);\r\n\t\txl = x + 1, xr = x + d, yl = y + 1, yr = y + s, v = Query(root) + w;\r\n\t\tInsert(root);\r\n\t}\r\n\t\r\n\txl = 1, xr = n, yl = 1, yr = m;\r\n\tprintf(\"%d\\n\", Query(root));\r\n}\r\n<\/pre>\n
.....
\n2_Dimension_Segment_Tree
\n...<\/p>\n
\r\n#include \r\nusing namespace std;  \r\nconst int nn = 1024, ll = 2047; \/\/2 * nn - 1\r\n\r\nstruct Segment_Tree{\r\n\tint f[ll], s[ll];\r\n\tvoid Insert(int, int, int);\r\n\tvoid Query(int, int, int);\r\n};\r\n\r\nstruct Two_Dimension_Segment_Tree{\r\n\tSegment_Tree f[ll], s[ll];\r\n\tvoid Insert(int, int, int);\r\n\tvoid Query(int, int, int);\r\n} T;\r\nint root;\r\nint xl, xr, yl, yr, h;\r\nint n, _m, q;\r\n\r\n\r\nvoid Segment_Tree::Insert(int now, int l, int r){\t\r\n\t\r\n\tf[now] = max(f[now], h);\r\n\t\r\n\tif (yl <= l && r <= yr){\r\n\t\ts[now] = max(s[now] , h); \/\/f[now]);\r\n\t\t\/\/s[now] = h; \/\/#\r\n\t}\r\n\telse {\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (yl <= m) Insert(now, l, m);\r\n\t\tif (m < yr) Insert(now+1, m+1, r);\r\n\t}\r\n}\r\n\r\nvoid Segment_Tree::Query(int now, int l, int r){\r\n\tif (yl <= l && r <= yr){\r\n\t\th = max(h, f[now]);\r\n\t}\r\n\telse {\r\n\t\th = max(h, s[now]);\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (yl <= m) Query(now, l, m);\r\n\t\tif (m < yr) Query(now+1, m+1, r);\r\n\t}\r\n} \r\n\r\n\r\nvoid Two_Dimension_Segment_Tree::Insert(int now, int l, int r){\r\n\t\r\n\tf[now].Insert(root, 1, _m);\r\n\t\r\n\tif (xl <= l && r <= xr){\r\n\t\ts[now].Insert(root, 1, _m);\r\n\t}\r\n\telse {\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (xl <= m) Insert(now, l, m);\r\n\t\tif (m < xr) Insert(now+1, m+1, r);\r\n\t}\r\n}\r\n\r\nvoid Two_Dimension_Segment_Tree::Query(int now, int l, int r){\r\n\tif (xl <= l && r <= xr){\r\n\t\tf[now].Query(root, 1, _m);\r\n\t}\r\n\telse {\r\n\t\ts[now].Query(root, 1, _m);\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (xl <= m) Query(now, l, m);\r\n\t\tif (m < xr) Query(now+1, m+1, r);\r\n\t}\r\n}\r\n\r\n\r\n\r\n\r\nint main(){\r\n\t\/\/freopen(\"in.txt\", \"r\", stdin);\r\n\tscanf(\"%d%d%d\", &n, &_m, &q); root = 1;\r\n\tint d, s, w, x, y;\r\n\tfor (int i = 0; i < q; i ++){\r\n\t\tscanf(\"%d%d%d%d%d\", &d, &s, &w, &x, &y);\r\n\t\txl = x + 1, xr = x + d, yl = y + 1, yr = y + s, h = 0, T.Query(root, 1, n), h += w;\r\n\t\tT.Insert(root, 1, n);\r\n\t}\r\n\t\r\n\txl = 1, xr = n, yl = 1, yr = _m, T.Query(root, 1, n);\r\n\tprintf(\"%d\\n\", h);\r\n}\r\n<\/pre>\n
\r\n#include \r\nusing namespace std;  \r\nconst int nn = 1024, ll = 2047; \/\/2 * nn - 1\r\n\r\nstruct Segment_Tree{\r\n\tint f[ll], s[ll];\r\n\tvoid Insert(int, int, int);\r\n\tvoid Query(int, int, int);\r\n};\r\n\r\nstruct Two_Dimension_Segment_Tree{\r\n\tSegment_Tree f[ll], s[ll];\r\n\tvoid Insert(int, int, int);\r\n\tvoid Query(int, int, int);\r\n} T;\r\nint root;\r\nint xl, xr, yl, yr, h;\r\nint n, m, q;\r\n\r\n\r\nvoid Segment_Tree::Insert(int now, int l, int r){\t\r\n\t\r\n\tf[now] = max(f[now], h);\r\n\t\r\n\tif (yl <= l && r <= yr){\r\n\t\ts[now] = max(s[now] , h); \/\/s[now] = h; \/\/#\r\n\t}\r\n\telse {\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (yl <= m) Insert(now, l, m);\r\n\t\tif (m < yr) Insert(now+1, m+1, r);\r\n\t}\r\n}\r\n\r\nvoid Segment_Tree::Query(int now, int l, int r){\r\n\tif (yl <= l && r <= yr){\r\n\t\th = max(h, f[now]);\r\n\t}\r\n\telse {\r\n\t\th = max(h, s[now]);\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (yl <= m) Query(now, l, m);\r\n\t\tif (m < yr) Query(now+1, m+1, r);\r\n\t}\r\n} \r\n\r\n\r\nvoid Two_Dimension_Segment_Tree::Insert(int now, int l, int r){\r\n\t\r\n\tf[now].Insert(root, 1, m);\r\n\t\r\n\tif (xl <= l && r <= xr){\r\n\t\ts[now].Insert(root, 1, m);\r\n\t}\r\n\telse {\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (xl <= m) Insert(now, l, m);\r\n\t\tif (m < xr) Insert(now+1, m+1, r);\r\n\t}\r\n}\r\n\r\nvoid Two_Dimension_Segment_Tree::Query(int now, int l, int r){\r\n\tif (xl <= l && r <= xr)\r\n\t\tf[now].Query(root, 1, m);\r\n\telse {\r\n\t\ts[now].Query(root, 1, m);\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (xl <= m) Query(now, l, m);\r\n\t\tif (m < xr) Query(now+1, m+1, r);\r\n\t}\r\n}\r\n\r\n\r\n\r\n\r\nint main(){\r\n\t\/\/freopen(\"in.txt\", \"r\", stdin);\r\n\tscanf(\"%d%d%d\", &n, &m, &q); root = 1;\r\n\tint d, s, w, x, y;\r\n\tfor (int i = 0; i < q; i ++){\r\n\t\tscanf(\"%d%d%d%d%d\", &d, &s, &w, &x, &y);\r\n\t\txl = x + 1, xr = x + d, yl = y + 1, yr = y + s, h = 0, T.Query(root, 1, n), h += w;\r\n\t\tT.Insert(root, 1, n);\r\n\t}\r\n\txl = 1, xr = n, yl = 1, yr = m, T.Query(root, 1, n);\r\n\tprintf(\"%d\\n\", h);\r\n}\r\n\r\n\r\n\/*\r\n f >= s\r\n f >= f[l], f[r];...\r\n s <= s[l], s[r];...\r\n s != 0 ...(.. == s.)\r\n *\/\r\n<\/pre>\n
\r\n#include \r\nusing namespace std;  \r\nconst int nn = 1024, ll = 2048; \/\/2 * nn\r\n\r\nstruct Segment_Tree{\r\n\tint key[ll]; bool close[ll];\r\n\tvoid Open(int);\r\n\tvoid Insert(int, int, int);\r\n\tvoid Query(int, int, int);\r\n};\r\n\r\nstruct Two_Dimension_Segment_Tree{\r\n\tSegment_Tree f[ll], s[ll];\r\n\tvoid Insert(int, int, int);\r\n\tvoid Query(int, int, int);\r\n} T;\r\nint root;\r\nint xl, xr, yl, yr, h;\r\nint n, m, q;\r\n\r\n\r\n\r\nvoid Segment_Tree::Open(int now){\r\n\tint left = now << 1, right = left + 1;\r\n\tkey[left] = key[right] = key[now];\r\n\tclose[left] = close[right] = true;\r\n\tclose[now] = false;\r\n}\r\n\r\nvoid Segment_Tree::Insert(int now, int l, int r){\t\r\n\tif (yl <= l && r <= yr){\r\n\t\tkey[now] = max(key[now], h);\r\n\t\tclose[now] = true;\r\n\t}\r\n\telse {\r\n\t\tif (close[now]) Open(now);\r\n\t\tkey[now] = max(key[now], h);\r\n\t\t\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (yl <= m) Insert(now, l, m);\r\n\t\tif (m < yr) Insert(now+1, m+1, r);\r\n\t}\r\n}\r\n\r\nvoid Segment_Tree::Query(int now, int l, int r){\r\n\tif (close[now] || yl <= l && r <= yr){\r\n\t\th = max(h, key[now]);\r\n\t}\r\n\telse {\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (yl <= m) Query(now, l, m);\r\n\t\tif (m < yr) Query(now+1, m+1, r);\r\n\t}\r\n} \r\n\r\n\r\nvoid Two_Dimension_Segment_Tree::Insert(int now, int l, int r){\r\n\t\r\n\tf[now].Insert(root, 1, m);\r\n\t\r\n\tif (xl <= l && r <= xr){\r\n\t\ts[now].Insert(root, 1, m);\r\n\t}\r\n\telse {\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (xl <= m) Insert(now, l, m);\r\n\t\tif (m < xr) Insert(now+1, m+1, r);\r\n\t}\r\n}\r\n\r\nvoid Two_Dimension_Segment_Tree::Query(int now, int l, int r){\r\n\tif (xl <= l && r <= xr)\r\n\t\tf[now].Query(root, 1, m);\r\n\telse {\r\n\t\ts[now].Query(root, 1, m);\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (xl <= m) Query(now, l, m);\r\n\t\tif (m < xr) Query(now+1, m+1, r);\r\n\t}\r\n}\r\n\r\n\r\n\r\n\r\nint main(){\r\n\tfreopen(\"in.txt\", \"r\", stdin);\r\n\tscanf(\"%d%d%d\", &n, &m, &q); root = 1;\r\n\tint d, s, w, x, y;\r\n\tfor (int i = 0; i < q; i ++){\r\n\t\tscanf(\"%d%d%d%d%d\", &d, &s, &w, &x, &y);\r\n\t\txl = x + 1, xr = x + d, yl = y + 1, yr = y + s, h = 0, T.Query(root, 1, n), h += w;\r\n\t\tT.Insert(root, 1, n);\r\n\t}\r\n\txl = 1, xr = n, yl = 1, yr = m, h = 0, T.Query(root, 1, n);\r\n\tprintf(\"%d\\n\", h);\r\n}\r\n\r\n\r\n\/*\r\n f >= s\r\n f >= f[l], f[r];...\r\n s <= s[l], s[r];...\r\n s != 0 ...(.. == s.)\r\n *\/\r\n\r\n\/\/\u3002\u3002!!!..\r\n\r\n<\/pre>\n
\r\n#include \r\nusing namespace std;  \r\nconst int nn = 1024, ll = 2048; \/\/2 * nn - 1\r\n\r\n\r\nstruct Event{\r\n\tint now, l, r, h;\r\n\tEvent() {} \r\n\tEvent(int a, int b, int c, int d) :now(a), l(b), r(c), h(d){}\r\n};\r\n\r\nstruct Segment_Tree{\r\n\tint key[ll]; bool close[ll];\r\n\tvoid Open(int);\r\n\tvoid Insert(int, int, int);\r\n\tvoid Query(int, int, int);\r\n};\r\n\r\nstruct Two_Dimension_Segment_Tree{\r\n\tSegment_Tree key[ll]; bool close[ll]; Event delay[ll];\r\n\tvoid Open(int);\r\n\tvoid Insert(int, int, int);\r\n\tvoid Query(int, int, int);\r\n} T;\r\nint root;\r\nint xl, xr, yl, yr, h;\r\nint n, m, q;\r\n\r\n\r\n\r\nvoid Segment_Tree::Open(int now){\r\n\tint left = now << 1, right = left + 1;\r\n\tkey[left] = key[right] = key[now];\r\n\tclose[left] = close[right] = true;\r\n\tclose[now] = false;\r\n}\r\n\r\nvoid Segment_Tree::Insert(int now, int l, int r){\t\t\r\n\tif (yl <= l && r <= yr){\r\n\t\tkey[now] = max(key[now], h);\r\n\t\tclose[now] = true;\r\n\t}\r\n\telse {\r\n\t\tif (close[now]) Open(now);\r\n\t\tkey[now] = max(key[now], h);\r\n\t\t\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (yl <= m) Insert(now, l, m);\r\n\t\tif (m < yr) Insert(now+1, m+1, r);\r\n\t}\r\n}\r\n\r\nvoid Segment_Tree::Query(int now, int l, int r){\r\n\tif (close[now] || yl <= l && r <= yr){\r\n\t\th = max(h, key[now]);\r\n\t}\r\n\telse {\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (yl <= m) Query(now, l, m);\r\n\t\tif (m < yr) Query(now+1, m+1, r);\r\n\t}\r\n} \r\n\r\nvoid Two_Dimension_Segment_Tree::Open(int now){\r\n\tint left = now << 1, right = left + 1;\r\n\t\r\n\tint t1 = yl, t2 = yr, t3 = h;\r\n\tyl = delay[now].l, yr = delay[now].r, h = delay[now].h;\r\n\tkey[left].Insert(root, 1, m), key[right].Insert(root, 1, m);\r\n\tyl = t1, yr = t2, h = t3;\t\r\n\t\r\n\tdelay[left] = delay[right] = delay[now];\r\n\tclose[left] = close[right] = true;\r\n\tclose[now] = false;\r\n}\r\n\r\n\r\nvoid Two_Dimension_Segment_Tree::Insert(int now, int l, int r){\r\n\tif (xl <= l && r <= xr){\r\n\t\tkey[now].Insert(root, 1, m);\r\n\t\tdelay[now] = Event(now, yl, yr, h);\r\n\t\tclose[now] = true;\r\n\t}\r\n\telse {\r\n\t\tif (close[now]) Open(now);\r\n\t\tkey[now].Insert(root, 1, m);\r\n\t\t\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (xl <= m) Insert(now, l, m);\r\n\t\tif (m < xr) Insert(now+1, m+1, r);\r\n\t}\r\n}\r\n\r\nvoid Two_Dimension_Segment_Tree::Query(int now, int l, int r){\r\n\tif (close[now] || xl <= l && r <= xr){\r\n\t\tkey[now].Query(root, 1, m);\r\n\t}\r\n\telse {\r\n\t\tint m = (l + r) \/ 2; now <<= 1;\r\n\t\tif (xl <= m) Query(now, l, m);\r\n\t\tif (m < xr) Query(now+1, m+1, r);\r\n\t}\r\n}\r\n\r\n\r\n\r\n\r\nint main(){\r\n\t\/\/freopen(\"in.txt\", \"r\", stdin);\r\n\tscanf(\"%d%d%d\", &n, &m, &q); root = 1;\r\n\tint d, s, w, x, y;\r\n\tfor (int i = 0; i < q; i ++){\r\n\t\tscanf(\"%d%d%d%d%d\", &d, &s, &w, &x, &y);\r\n\t\txl = x + 1, xr = x + d, yl = y + 1, yr = y + s, h = 0, T.Query(root, 1, n), h += w;\r\n\t\tT.Insert(root, 1, n);\r\n\t}\r\n\txl = 1, xr = n, yl = 1, yr = m, h = 0, T.Query(root, 1, n);\r\n\tprintf(\"%d\\n\", h);\r\n}\r\n\r\n\r\n\/*\r\n f >= s\r\n f >= f[l], f[r];...\r\n s <= s[l], s[r];...\r\n s != 0 ...(.. == s.)\r\n *\/\r\n<\/pre>\n

\n<\/p>\n
External link :<\/h3>\n
http:\/\/61.187.179.132:8080\/JudgeOnline\/showproblem?problem_id=1513<\/a>
\nhttp:\/\/www.main.edu.pl\/user.phtml?op=zadania&c=1300<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"
Brief description : \u4e8c\u7ef4 RMQ\u3002<\/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":[1],"tags":[],"class_list":["post-80","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-1i","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/80","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=80"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/80\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=80"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=80"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=80"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}