# 某岛

… : "…アッカリ～ン . .. . " .. .
November 25, 2014

# Aizu 0602. 切り取り線(Cutting)

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

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;
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);
}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;
}
}
}; 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);
}

```