//}/* .................................................................................................................................. */

const int MAXN = 100009;

VI Y; template<class T> inline T low_bit(T x) {return x & -x;}

namespace BIT{
    const int N = MAXN * 2;
    int C[N], n;
    void Add(int x, int d){
        for (;x<=n;x+=low_bit(x)) C[x] += d;
    }
    int Sum(int x){
        int res = 0; for (;x;x^=low_bit(x)) res += C[x];
        return res;
    }
    int Sum(int l, int r){
        return Sum(r) - Sum(l-1);
    }
} //using namespace BIT;

namespace ST{
    const int NN = 4*2*MAXN;
    bool T[NN]; int a, b;

#define lx (x << 1)
#define rx (lx | 1)
#define ml (l + r >> 1)
#define mr (ml + 1)
#define lc lx, l, ml
#define rc rx, mr, r
#define rt 1, 0, Y.size()-1

    void cov(int x){
        T[x] = 1;
    }

    void rls(int x){
        if (T[x]){
            T[lx] = T[rx] = 1;
            T[x] = 0;
        }
    }

    bool Query(int x, int l, int r, int p){
        if (l == r){
            bool z = T[x]; T[x] = 0;
            return z;
        }
        else{
            rls(x);
            return p < mr ? Query(lc, p) : Query(rc, p);
        }
    }

    bool Query(int p){
        return Query(rt, p);
    }

    void Insert(int x, int l, int r){
        if (b < l || r < a) return;
        if (a <= l && r <= b){
            cov(x);
        }
        else{
            rls(x);
            Insert(lc); Insert(rc);
        }
    }
    void Insert(int _a, int _b){
        a = _a, b = _b;
        Insert(rt);
    }
}

namespace DSU{ //Disjoint Set Union
    VI P;
    inline int Find(int x){
        return P[x] == x ? x : P[x] = Find(P[x]);
    }
    inline bool Union(int x, int y){
        x = Find(x), y = Find(y); if (x == y) return 0;
        P[x] = y; return 1;
    }
    void fix(int p){
        if (ST::Query(p)){
            int n = P.size(); P.PB(n);
            P[p] = n;
        }
}
} //using namespace DSU;

LL res; int W, H, n; set<int> S;

struct Event{
    int x, t, y1, y2;

    Event(int x, int t, int y1, int y2):x(x),t(t),y1(y1),y2(y2){
    }
    bool operator<(const Event& rhs)const{
        return x < rhs.x || x == rhs.x && t < rhs.t;
    }
    void gao(){
		if(!t){
			y1 = *--S.lower_bound(y2); DSU::fix(y1); DSU::fix(y2); DSU::Union(y1, y2);
			BIT::Add(y2, 1); S.insert(y2);
		}else if(t == 1){
		    int ll = *S.lower_bound(y1), rr = *--S.upper_bound(y2); if (rr < ll) return;
			res += BIT::Sum(ll, rr-1); ST::Insert(ll, rr-1);
		}else if(t == 2){
			y1 = *--S.lower_bound(y2); DSU::fix(y1); DSU::fix(y2); if(DSU::Union(y1, y2)) --res;
			BIT::Add(y2, -1); S.erase(y2);
		}
    }
}; vector<Event> A;

struct Line{
    int x1, y1, x2, y2;
    Line(int x1=0, int y1=0, int x2=0, int y2=0):x1(x1),y1(y1),x2(x2),y2(y2){
    }
    void in(){
        RD(x1, y1, x2, y2);
        if (x1 > x2) swap(x1, x2);
        if (y1 > y2) swap(y1, y2);
    }
    void gao(){
        y1 = LBD(Y, y1); y2 = LBD(Y, y2); if(y1 == y2){
            A.PB(Event(x1, 0, y1, y2));
            A.PB(Event(x2, 2, y1, y2));
        }else{
            A.PB(Event(x1, 1, y1, y2));
        }
    }
}; vector<Line> L;


int main(){

#ifndef ONLINE_JUDGE
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

	RD(W, H, n); L.resize(n); REP(i, n) L[i].in();

	L.PB(Line(0,0,W,0)); L.PB(Line(0,0,0,H));
	L.PB(Line(W,0,W,H)); L.PB(Line(0,H,W,H));

	Y.PB(-1); ECH(it, L) Y.PB(it->y1), Y.PB(it->y2); UNQ(Y);
	BIT::n = Y.size(); S.insert(0); DSU::P.resize(Y.size(), 0);

	ECH(it, L) it->gao(); SRT(A); res = 0; ECH(it, A) it->gao();
	printf("%lld\n", res);
}

Posted by xiaodao
Category: Aizu