题意：
给出一个棋盘，其中一些矩形位置不能放棋子。
现在往棋盘里面放入车，使得其不能互相攻击。
求能放的最大数量。
分析：
如果题目是给出：某些矩形能放棋子，那这题就非常的模板了。
可以把矩形当做点，然后每行每列分别视为一个点，行点向覆盖其的矩形连边，矩形再向覆盖的列点连边。原点向每个行点连一条容量为1的边，列点向汇点连一条容量为1的边。
然而这样显然会T，所以要用线段树优化建图。
嗯。。非常丑陋形象的图
然后，现在问题是，它给出的是不能放的矩形。
那么显然需要一种新的矩形划分方式，来得到能放的矩形：
每个矩形的上边和下边，分别向两侧延长，直到遇到被挡住或者边界为止。
这样理论上得到的矩形不会超过给出矩形的4倍。证明很容易，这里不再赘述。
为了得到这个矩形，有2种方法：
1、暴力扫描线（通常1500~2000ms左右，写得丑可能会更慢）
2、线段树扫描线（200ms以内）
但是线段树要多上接近70行左右。。。5.3KB的代码就这么诞生了
#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<cmath>
#define SF scanf
#define PF printf
#define MAXN 10010
#define INF 0x3FFFFFFF
using namespace std;
struct node{
int l,r,h;bool flag;node () {
}node (int l1,int r1,int h1,bool flag1):l(l1),r(r1),h(h1),flag(flag1) {
}bool operator <(const node &a) const {
if(h!=a.h)return h<a.h;return flag<a.flag;}
}lin[MAXN*2];
struct Tree{
int h,tag,sum;
}tree[MAXN*10];
int n,tot,s,t;
void pushdown(int id,int l,int r){
if(tree[id].tag!=0){
tree[id<<1].tag+=tree[id].tag;tree[id<<1|1].tag+=tree[id].tag;int mid=(l+r)>>1;tree[id<<1].sum+=(mid-l+1)*tree[id].tag;tree[id<<1|1].sum+=(r-mid)*tree[id].tag;tree[id].tag=0;}
}
void pushup(int id){
tree[id].sum=tree[id<<1].sum+tree[id<<1|1].sum;
}
vector<int> a[MAXN*8],w[MAXN*8],rev[MAXN*8];
void add_edge(int u,int v,int len){
// PF("[%d %d %d]\n",u,v,len);a[u].push_back(v);a[v].push_back(u);w[u].push_back(len);w[v].push_back(0);rev[u].push_back(a[v].size()-1);rev[v].push_back(a[u].size()-1);
}
int find_lft(int x,int id=1,int l=1,int r=n){
if(tree[id].sum==0)return l-1;if(l==r)return l;pushdown(id,l,r);int mid=(l+r)>>1;if(x<=mid)return find_lft(x,id<<1,l,mid);else{
if(tree[id<<1|1].sum==0)return find_lft(x,id<<1,l,mid);int res=find_lft(x,id<<1|1,mid+1,r);if(res==mid)return find_lft(x,id<<1,l,mid);return res;}
}
int find_rit(int x,int id=1,int l=1,int r=n){
if(tree[id].sum==0)return r+1;if(l==r)return r;pushdown(id,l,r);int mid=(l+r)>>1;if(x<=mid){
if(tree[id<<1].sum==0)return find_rit(x,id<<1|1,mid+1,r);int res=find_rit(x,id<<1,l,mid);if(res==mid+1)return find_rit(x,id<<1|1,mid+1,r);return res;} elsereturn find_rit(x,id<<1|1,mid+1,r);
}
int pl[MAXN*10],pr[MAXN*10];
void build(int l,int r,int id,bool flag){
if(l==r){
if(flag==0)add_edge(s,id,1);elseadd_edge(id,t,1);return ;}int mid=(l+r)>>1;pl[id]=++tot;pr[id]=++tot;build(l,mid,pl[id],flag);build(mid+1,r,pr[id],flag);if(flag==0){
add_edge(pl[id],id,INF);add_edge(pr[id],id,INF);}else{
add_edge(id,pl[id],INF);add_edge(id,pr[id],INF);}
}
void add_edge_lc(int l1,int r1,int tar,int id,bool flag,int l=1,int r=n){
if(l>=l1&&r<=r1){
if(flag==0)add_edge(id,tar,INF);elseadd_edge(tar,id,INF);return ;} int mid=(l+r)>>1;if(l1<=mid)add_edge_lc(l1,r1,tar,pl[id],flag,l,mid);if(r1>mid)add_edge_lc(l1,r1,tar,pr[id],flag,mid+1,r);
}
int rtc,rtr;
void add_blo(int l,int r,int lw,int up){
if(lw==up)return ;
// PF("--[%d %d %d %d]--\n",l,r,lw,up);tot++;add_edge_lc(up+1,lw,tot,rtc,0);add_edge_lc(l,r,tot,rtr,1);
}
void putline(int l1,int r1,int h,int id=1,int l=1,int r=n){
if(l>=l1&&r<=r1){
tree[id].h=max(tree[id].h,h);return ;}int mid=(l+r)>>1;if(l1<=mid)putline(l1,r1,h,id<<1,l,mid);if(r1>mid)putline(l1,r1,h,id<<1|1,mid+1,r);
}
int get_h(int pos,int id=1,int l=1,int r=n){
if(l==r)return tree[id].h;int mid=(l+r)>>1;if(pos<=mid)return max(tree[id].h,get_h(pos,id<<1,l,mid));elsereturn max(tree[id].h,get_h(pos,id<<1|1,mid+1,r));
}
void cov(int l1,int r1,int id=1,int l=1,int r=n){
if(l!=r)pushdown(id,l,r);if(l>=l1&&r<=r1){
tree[id].sum+=(r-l+1);tree[id].tag++;return ;}int mid=(l+r)>>1;if(l1<=mid)cov(l1,r1,id<<1,l,mid);if(r1>mid)cov(l1,r1,id<<1|1,mid+1,r);pushup(id);
}
void recov(int l1,int r1,int id=1,int l=1,int r=n){
if(l!=r)pushdown(id,l,r);if(l>=l1&&r<=r1){
tree[id].sum-=(r-l+1);tree[id].tag--;return ;}int mid=(l+r)>>1;if(l1<=mid)recov(l1,r1,id<<1,l,mid);if(r1>mid)recov(l1,r1,id<<1|1,mid+1,r);pushup(id);
}
int d[MAXN*8],g[MAXN*8];
int dfs(int x,int flw){
// PF("<%d %d %d>\n",x,flw,d[x]);if(x==t)return flw;int flw1=flw;for(int i=0;i<int(a[x].size());i++){
int u=a[x][i];if(w[x][i]!=0&&d[u]==d[x]-1){
int f=dfs(u,min(flw,w[x][i]));w[x][i]-=f;w[u][rev[x][i]]+=f;flw-=f;if(flw==0)break;
// if(d[s]==tot+1)
// return flw1-flw;}}if(flw==flw1){
if(g[d[x]]==1){
d[s]=tot+1;return flw1-flw;}g[d[x]]--;int minh=tot;for(int i=0;i<int(a[x].size());i++)if(w[x][i]!=0)minh=min(minh,d[a[x][i]]);d[x]=minh+1;g[d[x]]++;}return flw1-flw;
}
int maxflow(){
g[0]=tot;int ans=0;while(d[s]<tot)ans+=dfs(s,INF);return ans;
}
int q,xl,yl,xr,yr;
int main(){
SF("%d%d",&n,&q);for(int i=1;i<=q;i++){
SF("%d%d%d%d",&yl,&xl,&yr,&xr);lin[i]=node(xl,xr,yl-1,1);lin[i+q]=node(xl,xr,yr,0);}q*=2;lin[++q]=node(1,n,n,1);s=1;t=2;tot=2;rtc=++tot;build(1,n,rtc,0);rtr=++tot;build(1,n,rtr,1);sort(lin+1,lin+1+q);for(int i=1;i<=q;i++){
// PF("<%d %d %d %d>\n",lin[i].l,lin[i].r,lin[i].h,lin[i].flag);if(lin[i].flag==0){
int l=find_lft(lin[i].l-1)+1;int r=find_rit(lin[i].r+1)-1;if(l<lin[i].l)add_blo(l,lin[i].l-1,lin[i].h,get_h(l));if(r>lin[i].r)add_blo(lin[i].r+1,r,lin[i].h,get_h(r));recov(lin[i].l,lin[i].r);putline(min(l,lin[i].l),max(r,lin[i].r),lin[i].h);}else{
int l=find_lft(lin[i].l)+1;int r=find_rit(lin[i].l)-1;if(l<=r)add_blo(l,r,lin[i].h,get_h(l));cov(lin[i].l,lin[i].r);putline(min(l,lin[i].l),max(r,lin[i].r),lin[i].h);}}PF("%d",maxflow());
}