记录3个变量。
sum[i]:当前区间被覆盖2次及两次以上的面积。
num[i]:当前区间被覆盖1次及一次以上的面积。
cover[i]:覆盖的lazy标记。
对于每一个区间.
更新操作如下：
void push_up(int_now)
{if(cover[rt]==0){num[rt]=num[rt<<1]+num[rt<<1|1];sum[rt]=sum[rt<<1]+sum[rt<<1|1];}if(cover[rt]==1){num[rt]=du[r+1]-du[l];sum[rt]=num[rt<<1]+num[rt<<1|1];}if(cover[rt]>=2){num[rt]=sum[rt]=du[r+1]-du[l];}
}那么剩下的问题就是简单的区间更新问题了。
还有，要注意每一个点所代表的含义。
我的每个点代表的含义为当前点到下一个点的长度。
#include<stdio.h>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include<vector>
#include<math.h>
#include<map>
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define maxn 11000
#define mem(a,b) (memset(a),b,sizeof(a))
#define lmin 1
#define rmax len
#define lson l,(l+r)/2,rt<<1
#define rson (l+r)/2+1,r,rt<<1|1
#define root lmin,rmax,1
#define now l,r,rt
#define int_now int l,int r,int rt
#define INF 99999999
#define LL long long
#define mod 10007
#define eps 1e-6
#define zero(x) (fabs(x)<eps?0:x)
map<double,int>mp;
double du[4010];
int len;
struct list
{double x1,y1;double x2,y2;
}node[maxn];
struct linen
{double y1,y2;int leap;double x;friend bool operator <(const linen &a,const linen &b){if(zero(a.x-b.x)!=0) return a.x<b.x;else return a.leap>b.leap;}
}line[maxn*2];
double sum[maxn*4*4*2];
double num[maxn*4*4*2];
int cover[maxn*4*4*2];
void push_up(int_now)
{if(cover[rt]==0){num[rt]=num[rt<<1]+num[rt<<1|1];sum[rt]=sum[rt<<1]+sum[rt<<1|1];}if(cover[rt]==1){num[rt]=du[r+1]-du[l];sum[rt]=num[rt<<1]+num[rt<<1|1];}if(cover[rt]>=2){num[rt]=sum[rt]=du[r+1]-du[l];}
}
void push_down(int_now)
{}
void creat(int_now)
{memset(sum,0,sizeof(sum));memset(cover,0,sizeof(cover));memset(num,0,sizeof(num));
}
void updata(int ll,int rr,int x,int_now)
{if(ll>r||rr<l)return;if(ll<=l&&rr>=r){cover[rt]+=x;push_up(now);return;}updata(ll,rr,x,lson);updata(ll,rr,x,rson);push_up(now);
}
int main()
{int t,n,s;scanf("%d",&t);while(t--){scanf("%d",&n);s=0;for(int i=1;i<=n;i++){scanf("%lf%lf%lf%lf",&node[i].x1,&node[i].y1,&node[i].x2,&node[i].y2);du[++s]=node[i].x1;du[++s]=node[i].y1;du[++s]=node[i].x2;du[++s]=node[i].y2;line[i*2-1].x=node[i].x1;line[i*2-1].y1=node[i].y1;line[i*2-1].y2=node[i].y2;line[i*2-1].leap=1;line[i*2].x=node[i].x2;line[i*2].y1=node[i].y1;line[i*2].y2=node[i].y2;line[i*2].leap=-1;}sort(line+1,line+n*2+1);sort(du+1,du+s+1);du[0]=-1;len =0;mp.clear();for(int i=1;i<=s;i++){if(du[i]!=du[i-1]){mp[du[i]]=++len;du[len]=du[i];}}creat(root);double st=0;double are=0.0;len--;for(int i=1;i<=n*2;i++){int l,r;l=mp[line[i].y1];r=mp[line[i].y2];if(zero(line[i].x-st)!=0){are+=(line[i].x-st)*sum[1];st=line[i].x;}updata(l,r-1,line[i].leap,root);}printf("%.2lf\n",are);}return 0;
}