zoj Split the Rectangle

題目大意:
Bob可以在一個原始空矩形或由一條垂線分割出的空矩形中畫一條水平線,反之畫一條垂線.
線畫完之後,Bob會在原始矩形內選兩個目標點,且目標點不會在畫的線上,Alice可以刪掉畫的線使得兩點在同一空矩形中,刪掉的線必須保證兩邊都是空矩形,且不能使圖不連通,求出刪完線後最多能剩幾個空矩形.

題目思路:
可以看出構造圖的過程是一個二叉樹建立的過程,要使兩個點合在一起只要知道兩點所在矩形的LCA即可,把LCA裡畫的線全刪掉就是了.而且是1000空間復雜度,暴力LCA即可.

代碼:
[cpp] 
#include <stdlib.h> 
#include <string.h> 
#include <stdio.h> 
#include <ctype.h> 
#include <math.h> 
#include <time.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <vector> 
#include <string> 
#include <iostream> 
#include <algorithm> 
using namespace std; 
 
#define ll long long 
#define ls rt<<1 
#define rs ls|1 
#define lson l,mid,ls 
#define rson mid+1,r,rs 
#define middle l+r>>1 
#define inf 0x3F3F3F3F 
#define eps (1e-9) 
#define MOD 1000000007 
typedef pair<int,int> pii; 
typedef multiset<int> mset; 
typedef multiset<int>::iterator mst_it; 
//const double pi=acos(-1.0); 
#define M 2000 +5 
template <class T> T _max(T x,T y){return x>y? x:y;} 
template <class T> T _min(T x,T y){return x<y? x:y;} 
template <class T> void _swap(T &x,T &y){T z=x;x=y;y=z;} 
int ts,cas=0; 
 
int n,m; 
int xl,yl,xr,yr; 
 
struct pot{ 
    int x,y; 
    pot(){} 
    pot(int _x,int _y): x(_x),y(_y){} 
    void read(){scanf("%d%d",&x,&y);} 
}; 
 
struct mtx{ 
    pot a,b; 
    int l,r; 
    void insert(pot _a,pot _b){a=_a,b=_b;} 
    void read(){a.read(),b.read();} 
    bool inner(mtx t){ 
        return (a.x<=t.a.x && t.b.x<=b.x && a.y<=t.a.y && t.b.y<=b.y); 
    } 
}; 
 
mtx val[M],c; 
int cnt[M],l[M],r[M],tot; 
 
void update(int rt){ 
    cnt[rt]++; 
    if(l[rt]==-1){ 
        val[l[rt]=++tot].insert(val[rt].a,c.b); 
        val[r[rt]=++tot].insert(c.a,val[rt].b); 
        return; 
    } 
    if(val[l[rt]].inner(c)) update(l[rt]); 
    else if(val[r[rt]].inner(c)) update(r[rt]); 
} 
 
int query(int rt){ 
    if(l[rt]==-1) return cnt[rt]; 
    if(val[l[rt]].inner(c)) return query(l[rt]); 
    if(val[r[rt]].inner(c)) return query(r[rt]); 
    return cnt[rt]; 
} 
 
void run(){ 
    int i,j; 
    scanf("%d%d",&n,&m); 
    memset(cnt,0,sizeof(cnt)); 
    memset(l,-1,sizeof(l)); 
    memset(r,-1,sizeof(r)); 
    val[tot=1].insert(pot(xl,yl),pot(xr,yr)); 
    for(i=1;i<=n;i++){ 
        c.read(); 
        if(c.a.x>c.b.x) _swap(c.a.x,c.b.x); 
        if(c.a.y>c.b.y) _swap(c.a.y,c.b.y); 
        update(1); 
    } 
    while(m--){ 
        c.read(); 
        if(c.a.x>c.b.x) _swap(c.a.x,c.b.x); 
        if(c.a.y>c.b.y) _swap(c.a.y,c.b.y); 
        printf("%d\n",n-query(1)+1); 
    } 
} 
 
void preSof(){ 
} 
 
int main(){ 
    //freopen("1.in","r",stdin); 
    //freopen("1.out","w",stdout); 
    preSof(); 
    //run(); 
    while(~scanf("%d%d%d%d",&xl,&yl,&xr,&yr)) run(); 
    //for(scanf("%d",&ts),cas=1;cas<=ts;cas++) run(); 
    return 0; 
}