题意：
给定一个n*n的矩阵，一个格子上可以放一个车。其中有q个子矩阵，且q个子矩阵互不相交或者是重叠（但边界可以衔接）。这q个子矩阵所覆盖的地方都是不能够放车的。车可以越过子矩阵覆盖的地方进行攻击（车可以横着或者是竖着直走，就像象棋中的那样）。现在问的是一共最多能够放多少个不能够互相攻击的车。
数据范围
1<=n<=10000,0<=q<=10000
输入格式
首先输入两个数字n,q,分别表示矩阵的大小和子矩阵的个数。
接下来有q行，每行四个正整数x1,y1,x2,y2,分别表示每一个子矩阵的左上角的坐标和右下角的坐标。
输出格式
直接输出最多能够放多少个车即可。
思路
如果不是放在网络流的题里面，我绝对会去想贪心
我觉得已经比较详细了
听完题解之后觉得非常的恶心。
首先，如果按照最普通的方式建图的话，就是一个套路性的东西：对于每一行、每一列分别建一个点，然后再让代表第i行的点指向代表第j行的点，表示(i,j)这个地方可以放一个车。当然，如果是被子矩阵覆盖了的话，肯定就不能够相边。最后跑一边最大流就得到了答案。
但是经过一番推敲后我们可以发现，一共有O(n)个点，然后最坏有O(n*n)条边，对于网络流而言是要T的。下面我们考虑优化。
首先让我们把题目中给出的子矩形称作黑色矩形
其实我们需要优化的就是建边的过程，也就是行向列进行连边的问题。我们可以考虑将剩下的空白的部分转化为一个个的小矩形（把这些矩形称作白色矩形），然后利用线段树进行统一的连边。
这样说是很抽象的，下面我们具体探讨一下如何利用线段树优化建图。
假设当前需要加入的白色矩形为(x1,y1,x2,y2)，那么在行坐标上就对应于(x1,x2)这个线段，列坐标上就对对应于(y1,y2)这个线段。然后我们在最开始建立两棵线段树，一棵表示行坐标，一棵表示列坐标，然后将(x1,x2)拆解成log(n)个子线段，将(y1,y2)拆解为log(n)个子线段，然后将这两坨子线段互相连边，那么就有log^2(n)条边。这样子就解决了建边的问题了（舒服）。
接下来，我们就只剩下了一个子问题了，那就是如何去找白色矩形（对空白部分进行划分）。首先需要满足两个前提：
1.能够成功划分完所有的空白的区域
2.划分的白色矩阵尽量少
这道题目前的优秀解法是这样的（橙色的是黑色矩阵）:
可以看出，对于每一个黑色矩形，它的上下两条边都向两边进行了发散，直到碰到了其它的边或者是边界才停下来，最终就会形成类似于上面所示的一个图。
然后红色的线就自然的将空白的区域划分为了若干个白色矩形。最后经实践证明，一共有O(n)级别的白色矩形。
如何来构造这样一个方案呢？
考虑这样一个算法:
扫描每一个黑色矩形，将每一个子矩阵分成两条线段，一条是位于第y1列的(x1,x2,0)，第y2列的(x1,x2,1)(后面的值表示类型)，然后根据列坐标进行排序。然后按照列坐标从小到大的顺序枚举这些线段，对于列左边相同的，先枚举类型0的，再枚举类型1的。
首先让我们考虑类型0的：
假设当前的线段是(x1,x2),在第j列。我们需要在全局维护一个a[]，其中a[i]表示从当前枚举到的第i行往前走，最远的能够到达的未被黑色矩形覆盖的空白格子的列坐标。
然后从x1到x2进行枚举，并记录一个当前的白色矩形的左边界last，以及上一次左边界发生变化的位置(行)，lastpos。假设枚举到了i，那么假如a[i]==last,那么就继续枚举；否则就将(lastpos,last,i-1,j-1)插入。
下面是给出的一个例子：
当扫描到i+2时，我们发现a[i]发生了变化，而此时的last=a[i]，lastpos=i，然后我们在这里发现了一个新的矩形，也就是(lastpos,last,i+1,j-1)，插入即可。
这样做是十分暴力的，复杂度高达O(n^2)，但是可以过
接下来考虑类型1的：
假设当前的线段为(x1,x2)，其实这条线段的作用就是用来更新a[]数组的。也就是将a[x1~x2]修改为当前的列坐标即可。记住列坐标相等的类型1线段与类型0线段，类型1一定是在类型0之后做
需要注意的是，在最开始输入完黑色矩阵后，我们还需要加入一个(1,n+1,n+1,n)的一条线段，来保证最后右边的空白区域有白色矩形来填充。
最后网络流的图大概是这样的：
左边为一棵线段树，右边为一棵线段树，叶子分别连向源、汇点，然后中间黄色的边是插入白色矩形的时候连的边。
具体细节就参考代码吧。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
#define MAXN 10000
#define MAXQ 10000
#define INF 0x3FFFFFFF
using namespace std;
struct Line
{
int p,l,r,typ;
Line(){};
Line(int _p,int _l,int _r,int _typ):p(_p),l(_l),r(_r),typ(_typ){};
};
bool operator < (const Line &a,const Line &b)
{
if(a.p!=b.p) return a.p<b.p;
return a.typ>b.typ;
}
struct edge
{
int to,cap;
edge *nxt,*bck;
}edges[MAXN*500];
edge *ncnt=&edges[0],*Adj[MAXN*10+5];
struct node
{
int ch[2];
}tree[MAXN*10];
int tcnt=0,rt[2];
vector<Line> Lineseq;
vector<int> seq[2];
int n,q,S,T;
int a[MAXN+5];
int d[MAXN*10],vd[MAXN*10];
void AddEdge(int u,int v,int cap)
{
edge *p=++ncnt;
p->to=v,p->cap=cap;
p->nxt=Adj[u],Adj[u]=p;
edge *q=++ncnt;
q->to=u,q->cap=0;
q->nxt=Adj[v],Adj[v]=q;
p->bck=q,q->bck=p;
}
void Build(int &p,int l,int r)
{
p=++tcnt;
if(l==r)
return;
int mid=(l+r)/2;
Build(tree[p].ch[0],l,mid);
Build(tree[p].ch[1],mid+1,r);
}
void Bianli(int p,int l,int r,int typ)
{
if(l==r)
{
if(typ==0) AddEdge(S,p,1);//参考之前网络流的图
else AddEdge(p,T,1);
return;
}
int mid=(l+r)/2;
//最后网络流的图的形状十分特殊
if(typ==0)
AddEdge(tree[p].ch[0],p,INF),AddEdge(tree[p].ch[1],p,INF);
if(typ==1)
AddEdge(p,tree[p].ch[0],INF),AddEdge(p,tree[p].ch[1],INF);
Bianli(tree[p].ch[0],l,mid,typ);
Bianli(tree[p].ch[1],mid+1,r,typ);
}
void Query(int p,int ql,int qr,int l,int r,int typ)
{
if(qr<l||ql>r)
return;
if(ql<=l&&r<=qr)
{
seq[typ].push_back(p);
return;
}
int mid=(l+r)/2;
Query(tree[p].ch[0],ql,qr,l,mid,typ);
Query(tree[p].ch[1],ql,qr,mid+1,r,typ);
}
void Insert_Rectangle(int x1,int y1,int x2,int y2)
{
seq[0].clear(),seq[1].clear();
Query(rt[0],x1,x2,1,n,0);Query(rt[1],y1,y2,1,n,1);
for(int i=0;i<(int)seq[0].size();i++)//先把对应的子线段找出来，然后两两连边
for(int j=0;j<(int)seq[1].size();j++)
AddEdge(seq[0][i],seq[1][j],INF);
}
void Scan()
{
Line cur;
fill(a,a+1+n,1);
for(int i=0;i<(int)Lineseq.size();i++)
{
cur=Lineseq[i];
int las=a[cur.l],lasp=cur.l;//last，lastpos的初值（可以画个图理解一下）
for(int p=cur.l;p<=cur.r;p++)
if(cur.typ==0)
{
if(las!=a[p])
{
if(cur.p!=las)//插入前记得判断这个矩阵是否存在（而不是一根线）
Insert_Rectangle(lasp,las,p-1,cur.p-1);//插入白色矩阵
las=a[p],lasp=p;
}
a[p]=cur.p+1;
}
else
a[p]=cur.p;
if(cur.typ==0&&cur.p!=las)//同样需要进行判断
Insert_Rectangle(lasp,las,cur.r,cur.p-1);
}
}
int aug(int u,int tot)
{
if(u==T)
return tot;
int v,delta,sum=0,mind=T+1;
if(d[u]<mind)
mind=d[u];
for(edge *p=Adj[u];p!=NULL;p=p->nxt)
{
v=p->to;
if(p->cap>0)
{
if(d[u]==d[v]+1)
{
delta=min(tot-sum,p->cap);
delta=aug(v,delta);
sum+=delta;
p->cap-=delta,p->bck->cap+=delta;
if(d[S]>=T+1)
return sum;
if(sum==tot)
break;
}
}
}
if(sum==0)
{
vd[d[u]]--;
if(vd[d[u]]==0)
d[S]=T+1;
d[u]=mind+1;
vd[d[u]]++;
}
return sum;
}
int Isap()
{
int flow=0;
memset(d,0,sizeof(d));
memset(vd,0,sizeof(vd));
vd[0]=T+1;
while(d[S]<T+1)
flow+=aug(S,INF);
return flow;
}
int main()
{
scanf("%d %d",&n,&q);
int x1,y1,x2,y2;
for(int i=1;i<=q;i++)
{
scanf("%d %d %d %d",&x1,&y1,&x2,&y2);
Lineseq.push_back(Line(y1,x1,x2,0));
Lineseq.push_back(Line(y2+1,x1,x2,1));
}
Lineseq.push_back(Line(n+1,1,n,0));//插入特殊矩阵
Lineseq.push_back(Line(n+2,1,n,1));
sort(Lineseq.begin(),Lineseq.end());
Build(rt[0],1,n);Build(rt[1],1,n);//线段树初始化
S=0,T=tcnt+1;
Bianli(rt[0],1,n,0);Bianli(rt[1],1,n,1);//"遍历"来进行线段树之间的连边
Scan();//扫描线
//预处理完毕
int ans=Isap();
printf("%d\n",ans);
return 0;
}