可以转变成上一题（hdu1542）的形式，把每条线段变成宽为1的矩形，求矩形面积并
要注意的就是转化为右下角的点需要x+1,y-1，画一条线就能看出来了
#include<bits/stdc++.h> #define pi acos(-1.0) #define ll long long #define mod 1000000007 #define ls l,m,rt<<1 #define rs m+1,r,rt<<1|1 #pragma comment(linker, "/STACK:1024000000,1024000000") using namespace std; const double g=10.0,eps=1e-7; const int N=200000+10,maxn=500+100,inf=0x3f3f3f; int mark[N<<2];//某区间下底边个数 ll sum[N<<2];//某区间下底边总长度 ll Hash[N];//离散化数组 //把横坐标作为线段进行扫描 //扫描是为了更新下底边个数和下底边总长度，记录答案 struct tree{ ll l,r,h;//l,r左右端点,h从x轴到该边的高 int d;//-1上底边/1下底边 tree(){} tree(ll x,ll y,ll z,int a):l(x),r(y),h(z),d(a){} bool operator <(const tree &a)const { return h<a.h; } }s[N]; void pushup(int l,int r,int rt) { if(mark[rt])sum[rt]=Hash[r+1]-Hash[l]; else if(l==r)sum[rt]=0; else sum[rt]=sum[rt<<1]+sum[rt<<1|1]; } void update(int L,int R,int d,int l,int r,int rt) { if(L<=l&&r<=R) { mark[rt]+=d;//如果是上底边mark-1，下底边mark+1 pushup(l,r,rt); return ; } int m=(l+r)>>1; if(L<=m)update(L,R,d,ls); if(R>m)update(L,R,d,rs); pushup(l,r,rt); } int Search(ll key,int n) { int l=0,r=n-1; while(l<=r) { int m=(l+r)/2; if(Hash[m]==key)return m; if(Hash[m]>key)r=m-1; else l=m+1; } return -1; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout<<setiosflags(ios::fixed)<<setprecision(2); int n; cin>>n; int k=0; for(int i=0; i<n; i++) { ll x1,x2,y1,y2; cin>>x1>>y1>>x2>>y2; if(x1==x2) { if(y1<y2)swap(y1,y2); x2++; y2--; } else { if(x1>x2)swap(x1,x2); x2++; y2--; } Hash[k]=x1; s[k++]= {x1,x2,y1,1}; //上底边 Hash[k]=x2; s[k++]= {x1,x2,y2,-1}; //下底边 } sort(Hash,Hash+k); sort(s,s+k); int m=1; for(int i=1; i<k; i++) //离散化 if(Hash[i]!=Hash[i-1]) Hash[m++]=Hash[i]; ll ans=0; memset(sum,0,sizeof sum); memset(mark,0,sizeof mark); for(int i=0; i<k; i++) //如果两个下底边重合，但是上底边可能不一样，必须更新mark，而sum不会改变 { int l=Search(s[i].l,m);//利用hash表查找 int r=Search(s[i].r,m)-1;//这里的l，r实际上是Hash表的标号 update(l,r,s[i].d,0,m-1,1);//维护mark和sum的值 ans+=sum[1]*(s[i+1].h-s[i].h);//sum[1]当前的下底边长度总和 } cout<<ans<<endl; return 0; } /********************* *********************/