学步园

线段树+离散化+扫描：

离散化的概念可以参考99年国家集训队陈宏的论文。

重点理解两个公式：[1]   ans+=
st[
1
].
segnum *
2
*(
yline[
i+1
].
x-
yline[
i].
x);

                           [2]   
ans+=
abs
(
st[
1
].
sum-
lsum);

首先，读入数据，存入yline[]数组中，并将y坐标存入INDEX[]数组中，其中，yline[]的结构应该为：

struct line<br /> {<br /> int st,ed;//记录竖段的上下坐标<br /> int x;//记录其x坐标<br /> bool inout;//记录左边还是右边<br /> }yline[max];<br />
 ；

接下来，对yline[]数组以x为关键字进行排序，INDEX[]数组同样得排序，并对INDEX[]数组进行去重操作，得到剩下的不同的y值为cnt个；

现在，到了建树阶段：这里建树，是以[0,cnt-1]为起始点建树的，也就是说st[1].l=0,st[1].r=cnt-1;因为这样建的树的话，每个节点的l,r值是和INDEX[]数组里面的y值相对应的，而且，用的是超元线段，这样，可以节省很多空间和操作的时间，当然，建完树，应该顺便初始化的，st[max]的结构是：

struct stnode<br /> {<br /> int l,r;//当前节点的左右区间范围<br /> int len;//当前节点的区间长度<br /> int segnum;//当前节点里不相交的段数<br /> int cover;//当前节点区间被覆盖的次数<br /> int sum;//当前节点被覆盖的总长度<br /> bool lcover,rcover;//当前节点的左右端点是否被覆盖<br /> };<br />
 

现在，从0开始，对yline[]数组进行扫描，扫描到左边，进行Insert操作，如果是右边，则进行Delete操作，并且，每次都对数进行更新，即getlen
(
index)和
getsegnum
(
index)两个操作
；

对于ans+=
abs
(
st[
1
].
sum-
lsum)，这个等式，应该不难理解，每次加上|线段树中所覆盖的总长度-上次还剩的长度|即更新的长度；

而 ans+=
st[
1
].
segnum *
2
*(
yline[
i+1
].
x-
yline[
i].
x)中，
难理解的是
st[
1
].
segnum 。对于这个的值，就是该区间中，有多少的不相交的段数。而求这个值的过程中，就用的了cover、st[i].lcover、st[i].rcover，而且，对轴进行了离散化。自己理解下，不是很好明白，但你必须弄懂！

现在贴上代码：

#include<cstdio><br /> #include<iostream><br /> #include<string><br /> #include<algorithm><br /> using namespace std;<br /> #define max 10005<br /> int n,cnt=0;<br /> int INDEX[max];<br /> struct stnode<br /> {<br /> int l,r;<br /> int len;<br /> int segnum;<br /> int cover;<br /> int sum;<br /> bool lcover,rcover;<br /> stnode()<br /> {<br /> l=r=0;<br /> len=segnum=cover=sum=0;<br /> lcover=rcover=false;<br /> }<br /> };<br /> stnode st[max*4];<br /> struct line<br /> {<br /> int st,ed;<br /> int x;<br /> bool inout;<br /> bool operator <(line o)const<br /> {<br /> return x<o.x;<br /> }<br /> };<br /> line yline[max];<br /> void build(int l,int r,int index)<br /> {<br /> st[index].l=l;<br /> st[index].r=r;<br /> st[index].len =INDEX[r]-INDEX[l];<br /> st[index].cover =0;<br /> st[index].segnum =0;<br /> st[index].sum =0;<br /> st[index].lcover =st[index].rcover =false;<br /> if(r-l>1)<br /> {<br /> int mid=(l+r)>>1;<br /> build(l,mid,index*2);<br /> build(mid,r,index*2+1);<br /> }<br /> }<br /> int getindex(int i)<br /> {<br /> return lower_bound(INDEX,INDEX+cnt,i)-INDEX;//lower_bound函数返回一个元素在容器中的迭代器，数组可以看成特殊的容器<br /> //，所以这里返回的迭代器就是指针<br /> }<br /> void getlen(int index)<br /> {<br /> if(st[index].cover >0)<br /> st[index].sum =st[index].len ;<br /> else if(st[index].r -st[index].l>1)<br /> st[index].sum=st[index*2].sum +st[index*2+1].sum ;<br /> else<br /> st[index].sum =0;<br /> }<br /> void getsegnum(int index)<br /> {<br /> if(st[index].cover>0)<br /> {<br /> st[index].lcover=st[index].rcover=true;<br /> st[index].segnum =1;<br /> }<br /> else if(st[index].r-st[index].l>1)<br /> {<br /> st[index].lcover=st[index*2].lcover;<br /> st[index].rcover=st[index*2+1].rcover;<br /> st[index].segnum=st[index*2].segnum+st[index*2+1].segnum-st[index*2].rcover*st[index*2+1].lcover;<br /> }<br /> else<br /> {<br /> st[index].lcover=st[index].rcover=false;<br /> st[index].segnum=0;<br /> }<br /> }<br /> void Insert(int l,int r,int index)<br /> {<br /> if(st[index].l==l&&st[index].r ==r)<br /> st[index].cover ++;<br /> else<br /> {<br /> int mid=(st[index].l +st[index].r )>>1;<br /> if(l>=mid)<br /> Insert(l,r,index*2+1);<br /> else if(r<=mid)<br /> Insert(l,r,index*2);<br /> else<br /> {<br /> Insert(l,mid,index*2);<br /> Insert(mid,r,index*2+1);<br /> }<br /> }<br /> getlen(index);<br /> getsegnum(index);<br /> }<br /> void Delete(int l,int r,int index)<br /> {<br /> if(st[index].l==l&&st[index].r==r)<br /> st[index].cover --;<br /> else<br /> {<br /> int mid=(st[index].l +st[index].r )>>1;<br /> if(r<=mid)<br /> Delete(l,r,index*2);<br /> else if(l>=mid)<br /> Delete(l,r,index*2+1);<br /> else<br /> {<br /> Delete(l,mid,index*2);<br /> Delete(mid,r,index*2+1);<br /> }<br /> }<br /> getlen(index);<br /> getsegnum(index);<br /> }<br /> int main()<br /> {<br /> while(scanf("%d",&n)!=EOF)<br /> {<br /> int x1,x2,y2,y1;<br /> int i,j,k;<br /> for(i=0;i<n;i++)<br /> {<br /> scanf("%d%d%d%d",&x1,&y1,&x2,&y2);<br /> yline[i*2].x=x1;yline[i*2].st =y1;yline[i*2].ed =y2;<br /> yline[i*2].inout =true;<br /> yline[i*2+1].x =x2;yline[i*2+1].st =y1;yline[i*2+1].ed =y2;<br /> yline[i*2+1].inout =false;<br /> INDEX[i*2]=y1;<br /> INDEX[i*2+1]=y2;<br /> }<br /> sort(INDEX,INDEX+n*2);<br /> sort(yline,yline+n*2);<br /> cnt=0;<br /> for(i=1;i<n*2;i++)<br /> {<br /> if(INDEX[i]!=INDEX[i-1])<br /> INDEX[cnt++]=INDEX[i-1];<br /> }<br /> INDEX[cnt++]=INDEX[2*n-1];<br /> build(0,cnt-1,1);<br /> int ans=0;<br /> int lsum=0;<br /> for(i=0;i<2*n-1;i++)<br /> {<br /> if(yline[i].inout)<br /> Insert(getindex(yline[i].st),getindex(yline[i].ed),1);<br /> else<br /> Delete(getindex(yline[i].st),getindex(yline[i].ed),1);<br /> ans+=st[1].segnum *2*(yline[i+1].x-yline[i].x);<br /> ans+=abs(st[1].sum-lsum);<br /> lsum=st[1].sum ;<br /> }<br /> Delete(getindex(yline[2*n-1].st ),getindex(yline[2*n-1].ed ),1);<br /> ans+=abs(st[1].sum -lsum);<br /> printf("%d/n",ans);<br /> }<br /> return 0;<br /> }<br />