https:\/\/github.com\/lychees\/ACM-Training\/tree\/master\/Archive\/BZOJ\/3165.%20%5BHeoi2013%5DSegment<\/a><\/p>\n\u505a\u6cd5\u4e8c\uff1a\u7ebf\u6bb5\u6811\u5957\u5e73\u8861\u6811<\/p>\n
\u56e0\u4e3a\u674e\u8d85\u6811\u7684\u5927\u6d41\u884c\uff0c\u6811\u5957\u6811\u53cd\u800c\u6ca1\u4eba\u518d\u53bb\u5199\u4e86\u3002\u3002\u3002<\/p>\n
\r\nconst int N = int(1e5) + 9;\r\n\r\n#define ll double\r\nstruct Line {\r\n\tmutable ll k, b, p; int id;\r\n\tLine (ll k = 0, ll b = 0, int id = 0):k(k),b(b),id(id) {\r\n\t p = 0;\r\n\t}\r\n\tll y(ll x) const {return k*x + b;}\r\n\tbool operator<(const Line& o) const { return k < o.k; }\r\n\tbool operator<(ll x) const { return p < x; }\r\n};\r\n\r\nstruct LineContainer : multiset<Line,less<>> {\r\n\tconst ll inf = 1\/.0;\r\n\tll div(ll a, ll b) {\r\n\t\treturn a \/ b;\r\n }\r\n\tbool isect(iterator x, iterator y) {\r\n\t\tif (y == end()) return x->p = inf, 0;\r\n\t\tif (x->k == y->k) x->p = x->b > y->b ? inf : -inf;\r\n\t\telse x->p = div(y->b - x->b, x->k - y->k);\r\n\t\treturn x->p >= y->p;\r\n\t}\r\n\tvoid add(ll k, ll b, int i) {\r\n\t\tadd(Line(k,b,i));\r\n\t}\r\n\tvoid add(Line t) {\r\n\t\tauto z = insert(t), y = z++, x = y;\r\n\t\twhile (isect(y, z)) z = erase(z);\r\n\t\tif (x != begin() && isect(--x, y)) isect(x, y = erase(y));\r\n\t\twhile ((y = x) != begin() && (--x)->p >= y->p)\r\n\t\t\tisect(x, erase(y));\r\n\t}\r\n\r\n\tpair<ll, int> query(ll x) {\r\n\t\tassert(!empty());\r\n\t\tauto& l = *lower_bound(x);\r\n\t\treturn {l.y(x), l.id};\r\n\t}\r\n} H;\r\nmap<int, pair<ll,int> > M;\r\n\r\n\r\nnamespace Segtree {\r\n const int NN = 4 * N;\r\n LineContainer T[NN];\r\n#define lx (x<<1)\r\n#define rx (lx|1)\r\n#define ml ((l+r)>>1)\r\n#define mr (ml+1)\r\n#define lc lx, l, ml\r\n#define rc rx, mr, r\r\n#define rt 1,1,39989\r\n void Insert(int x, int l, int r, int a, int b, Line L) {\r\n if (b < l || r < a) return;\r\n if (a <= l && r <= b) {\r\n T[x].add(L);\r\n } else {\r\n Insert(lc, a, b, L);\r\n Insert(rc, a, b, L);\r\n }\r\n }\r\n void Query(int x, int l, int r, int p, vector<LineContainer*>& L) {\r\n if (p < l || r < p) return;\r\n if (l <= p && p <= r) {\r\n if (!T[x].empty()) L.PB(&T[x]);\r\n }\r\n if (l != r) {\r\n Query(lc, p, L);\r\n Query(rc, p, L);\r\n }\r\n }\r\n}\r\n\r\nvector<LineContainer*> L;\r\n\r\nint main(){\r\n\r\n#ifndef ONLINE_JUDGE\r\n freopen("in.txt", "r", stdin);\r\n \/\/ freopen("out.txt", "w", stdout);\r\n#endif\r\n\r\n int id = 0; Rush {\r\n LL x0, y0, x1, y1;\r\n if (RD()) {\r\n RD(x0, y0, x1, y1);\r\n x0 = (x0 + last_ans - 1) % 39989 + 1;\r\n x1 = (x1 + last_ans - 1) % 39989 + 1;\r\n y0 = (y0 + last_ans - 1) % int(1e9) + 1;\r\n y1 = (y1 + last_ans - 1) % int(1e9) + 1;\r\n if (x0 > x1) {\r\n swap(x0, x1);\r\n swap(y0, y1);\r\n }\r\n if (x0 == x1) {\r\n auto t = pair<ll, int>(max(y0, y1), ++id);\r\n if (CTN(M, x0)) {\r\n M[x0] = t;\r\n } else {\r\n checkMax(M[x0], t);\r\n }\r\n } else {\r\n DB k = (DB)(y1-y0)\/(x1-x0);\r\n DB b = y0 - k*x0;\r\n Segtree::Insert(rt, x0, x1, Line(k, b, ++id));\r\n }\r\n } else {\r\n RD(x0);\r\n x0 = (x0 + last_ans - 1) % 39989 + 1;\r\n pair<ll, int> z = {-OO, 0}; L.clear(); Segtree::Query(rt, x0, L);\r\n for (auto& l: L) checkMax(z, l->query(x0));\r\n if (CTN(M, x0)) checkMax(z, M[x0]);\r\n OT(z.se);\r\n }\r\n }\r\n}\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"\u8bb0\u4e00\u4e0b\u6a21\u677f\u7684\u5199\u6cd5\u3002\u3002\u3002 \u505a\u6cd5\u4e00\uff1a\u674e\u8d85\u6811 https:\/\/github.com\/lychees\/ACM-Training\/tree\/master\/Archive\/BZOJ\/3165.%20%5BHeoi2013%5DSegment \u505a\u6cd5\u4e8c\uff1a\u7ebf\u6bb5\u6811\u5957\u5e73\u8861\u6811 \u56e0\u4e3a\u674e\u8d85\u6811\u7684\u5927\u6d41\u884c\uff0c\u6811\u5957\u6811\u53cd\u800c\u6ca1\u4eba\u518d\u53bb\u5199\u4e86\u3002\u3002\u3002 const int N = int(1e5) + 9; #define ll double struct Line { mutable ll k, b, p; int id; Line (ll k = 0, ll b = 0, int id = 0):k(k),b(b),id(id) { p = 0; } ll y(ll x) const {return k*x + b;} bool operator<(const Line& o) […]<\/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":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","enabled":false}}},"categories":[1],"tags":[],"class_list":["post-1766","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-su","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1766","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=1766"}],"version-history":[{"count":1,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1766\/revisions"}],"predecessor-version":[{"id":2001,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1766\/revisions\/2001"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1766"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1766"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1766"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}