<\/p>\n
\r\n\r\n\/\/}\/* .................................................................................................................................. *\/\r\n\r\nconst int MAXN = 100009;\r\n\r\nVI Y; template<class T> inline T low_bit(T x) {return x & -x;}\r\n\r\nnamespace BIT{\r\n const int N = MAXN * 2;\r\n int C[N], n;\r\n void Add(int x, int d){\r\n for (;x<=n;x+=low_bit(x)) C[x] += d;\r\n }\r\n int Sum(int x){\r\n int res = 0; for (;x;x^=low_bit(x)) res += C[x];\r\n return res;\r\n }\r\n int Sum(int l, int r){\r\n return Sum(r) - Sum(l-1);\r\n }\r\n} \/\/using namespace BIT;\r\n\r\nnamespace ST{\r\n const int NN = 4*2*MAXN;\r\n bool T[NN]; int a, b;\r\n\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, 0, Y.size()-1\r\n\r\n void cov(int x){\r\n T[x] = 1;\r\n }\r\n\r\n void rls(int x){\r\n if (T[x]){\r\n T[lx] = T[rx] = 1;\r\n T[x] = 0;\r\n }\r\n }\r\n\r\n bool Query(int x, int l, int r, int p){\r\n if (l == r){\r\n bool z = T[x]; T[x] = 0;\r\n return z;\r\n }\r\n else{\r\n rls(x);\r\n return p < mr ? Query(lc, p) : Query(rc, p);\r\n }\r\n }\r\n\r\n bool Query(int p){\r\n return Query(rt, p);\r\n }\r\n\r\n void Insert(int x, int l, int r){\r\n if (b < l || r < a) return;\r\n if (a <= l && r <= b){\r\n cov(x);\r\n }\r\n else{\r\n rls(x);\r\n Insert(lc); Insert(rc);\r\n }\r\n }\r\n void Insert(int _a, int _b){\r\n a = _a, b = _b;\r\n Insert(rt);\r\n }\r\n}\r\n\r\nnamespace DSU{ \/\/Disjoint Set Union\r\n VI P;\r\n inline int Find(int x){\r\n return P[x] == x ? x : P[x] = Find(P[x]);\r\n }\r\n inline bool Union(int x, int y){\r\n x = Find(x), y = Find(y); if (x == y) return 0;\r\n P[x] = y; return 1;\r\n }\r\n void fix(int p){\r\n if (ST::Query(p)){\r\n int n = P.size(); P.PB(n);\r\n P[p] = n;\r\n }\r\n}\r\n} \/\/using namespace DSU;\r\n\r\nLL res; int W, H, n; set<int> S;\r\n\r\nstruct Event{\r\n int x, t, y1, y2;\r\n\r\n Event(int x, int t, int y1, int y2):x(x),t(t),y1(y1),y2(y2){\r\n }\r\n bool operator<(const Event& rhs)const{\r\n return x < rhs.x || x == rhs.x && t < rhs.t;\r\n }\r\n void gao(){\r\n\t\tif(!t){\r\n\t\t\ty1 = *--S.lower_bound(y2); DSU::fix(y1); DSU::fix(y2); DSU::Union(y1, y2);\r\n\t\t\tBIT::Add(y2, 1); S.insert(y2);\r\n\t\t}else if(t == 1){\r\n\t\t int ll = *S.lower_bound(y1), rr = *--S.upper_bound(y2); if (rr < ll) return;\r\n\t\t\tres += BIT::Sum(ll, rr-1); ST::Insert(ll, rr-1);\r\n\t\t}else if(t == 2){\r\n\t\t\ty1 = *--S.lower_bound(y2); DSU::fix(y1); DSU::fix(y2); if(DSU::Union(y1, y2)) --res;\r\n\t\t\tBIT::Add(y2, -1); S.erase(y2);\r\n\t\t}\r\n }\r\n}; vector<Event> A;\r\n\r\nstruct Line{\r\n int x1, y1, x2, y2;\r\n Line(int x1=0, int y1=0, int x2=0, int y2=0):x1(x1),y1(y1),x2(x2),y2(y2){\r\n }\r\n void in(){\r\n RD(x1, y1, x2, y2);\r\n if (x1 > x2) swap(x1, x2);\r\n if (y1 > y2) swap(y1, y2);\r\n }\r\n void gao(){\r\n y1 = LBD(Y, y1); y2 = LBD(Y, y2); if(y1 == y2){\r\n A.PB(Event(x1, 0, y1, y2));\r\n A.PB(Event(x2, 2, y1, y2));\r\n }else{\r\n A.PB(Event(x1, 1, y1, y2));\r\n }\r\n }\r\n}; vector<Line> L;\r\n\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\tRD(W, H, n); L.resize(n); REP(i, n) L[i].in();\r\n\r\n\tL.PB(Line(0,0,W,0)); L.PB(Line(0,0,0,H));\r\n\tL.PB(Line(W,0,W,H)); L.PB(Line(0,H,W,H));\r\n\r\n\tY.PB(-1); ECH(it, L) Y.PB(it->y1), Y.PB(it->y2); UNQ(Y);\r\n\tBIT::n = Y.size(); S.insert(0); DSU::P.resize(Y.size(), 0);\r\n\r\n\tECH(it, L) it->gao(); SRT(A); res = 0; ECH(it, A) it->gao();\r\n\tprintf("%lld\\n", res);\r\n}\r\n\r\n<\/pre>\n","protected":false},"excerpt":{"rendered":"","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":[141],"tags":[],"class_list":["post-1081","post","type-post","status-publish","format-standard","hentry","category-aizu"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_shortlink":"https:\/\/wp.me\/p2tdP7-hr","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1081","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=1081"}],"version-history":[{"count":0,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/posts\/1081\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/media?parent=1081"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/categories?post=1081"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shuizilong.com\/house\/wp-json\/wp\/v2\/tags?post=1081"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}