题目地址：http://poj.org/problem?id=1177
题目超级水。离散化后用个数组模拟一下就能过了
而且不能忍的是比线段树的方法空间更小，时间更短....OMG
940K 16MS
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
const int maxn=5000+5;
int y[maxn*2],cnt[maxn*2]; //cnt指该区间被覆盖几层了
struct Line{int x,y1,y2;bool bLeft;Line(int x=0,int y1=0,int y2=0,bool bl=false):x(x),y1(y1),y2(y2),bLeft(bl){}bool operator < (const Line& l) const {return x<l.x;}
}line[maxn*2];
int main()
{int T,x1,y1,x2,y2,ycnt=0,nline=0;cin>>T;while(T--){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);y[ycnt++]=y1; y[ycnt++]=y2;line[nline++]=Line(x1,y1,y2,true);line[nline++]=Line(x2,y1,y2,false);}sort(y,y+ycnt);ycnt=unique(y,y+ycnt)-y;sort(line,line+nline);int pm=0;for(int i=0;i<nline;i++){ int L=find(y,y+ycnt,line[i].y1)-y;int R=find(y,y+ycnt,line[i].y2)-y;for(int j=L;j<R;j++) {if(line[i].bLeft) { //Addcnt[j]++; if(cnt[j]==1) pm+=(y[j+1]-y[j]);} else { //Delete cnt[j]--;if(cnt[j]==0) pm+=(y[j+1]-y[j]);}}int num=0,ok=1;for(int j=0;j<ycnt-1;j++) //中间有几条线段 {if(cnt[j]&&ok) num++,ok=0;if(!cnt[j]) ok=1;}num*=2;if(i!=nline-1) pm+=num*(line[i+1].x-line[i].x);} cout<<pm;return 0;
}线段树法：1296K 32MS
题目思路：http://www.cnblogs.com/shuaiwhu/archive/2012/04/22/2464876.html
#include<iostream>
#include<algorithm>
#include<cmath>
#include<cstdio>
using namespace std;
const int maxn=5000+5;
int y[maxn*2],nNode;
struct Node{int L,R,mid;int Covered; //被 完全覆盖 的次数 int Len,cnt; //Len该区间的线段长度，cnt该区间有几条线段 bool lLen,rLen; //左端点处，右端点处是否有线段 Node *pLeft,*pRight;Node(int l=0,int r=0):L(l),R(r){ mid=(L+R)/2; lLen=rLen=false;Covered=Len=cnt=0;pLeft=pRight=NULL;}
}tree[maxn*2];
struct Line{int x,y1,y2;bool bLeft;Line(int x=0,int y1=0,int y2=0,bool bl=false):x(x),y1(y1),y2(y2),bLeft(bl){}bool operator < (const Line& l) const {return x<l.x;}
}line[maxn*2];
void BuildTree(Node *root,int s,int e)
{*root=Node(s,e);if(s==e) return;root->pLeft=++nNode+tree;root->pRight=++nNode+tree;BuildTree(root->pLeft,s,root->mid);BuildTree(root->pRight,root->mid+1,e);
}
void update(Node *root)
{if(root->Covered>0) {root->lLen=root->rLen=true;root->Len=y[root->R+1]-y[root->L];root->cnt=1;} else if(root->L==root->R) {root->lLen=root->rLen=false;root->Len=root->cnt=0;}else {root->Len=root->pLeft->Len+root->pRight->Len;root->lLen=root->pLeft->lLen;root->rLen=root->pRight->rLen;root->cnt=root->pLeft->cnt+root->pRight->cnt-(root->pLeft->rLen&&root->pRight->lLen);//这句很关键 }
}
void Add(Node *root,int s,int e)
{if(root->L==s&&root->R==e) {root->Covered++;update(root);return;}if(e<=root->mid) Add(root->pLeft,s,e);else if(s>=root->mid+1) Add(root->pRight,s,e);else {Add(root->pLeft,s,root->mid);Add(root->pRight,root->mid+1,e);}update(root);
}
void Delete(Node *root,int s,int e)
{if(root->L==s&&root->R==e){root->Covered--;update(root);return; }if(e<=root->mid) Delete(root->pLeft,s,e);else if(s>=root->mid+1) Delete(root->pRight,s,e);else {Delete(root->pLeft,s,root->mid);Delete(root->pRight,root->mid+1,e);}update(root);
}
int main()
{int T,x1,y1,x2,y2,ycnt=0,nline=0;cin>>T;while(T--){scanf("%d%d%d%d",&x1,&y1,&x2,&y2);y[ycnt++]=y1; y[ycnt++]=y2;line[nline++]=Line(x1,y1,y2,true);line[nline++]=Line(x2,y1,y2,false);}sort(y,y+ycnt);ycnt=unique(y,y+ycnt)-y;nNode=0; BuildTree(tree,0,ycnt-1);sort(line,line+nline);int pm=0,lastLen=0;for(int i=0;i<nline;i++){int L=find(y,y+ycnt,line[i].y1)-y;int R=find(y,y+ycnt,line[i].y2)-y;if(line[i].bLeft) Add(tree,L,R-1);else Delete(tree,L,R-1);pm+=abs(tree[0].Len-lastLen);lastLen=tree[0].Len;if(i!=nline-1) pm+=tree[0].cnt*2*(line[i+1].x-line[i].x);}cout<<pm;return 0;
}