C++14(g++5.4) 解法, 执行用时: 3ms, 内存消耗: 504K, 提交时间: 2020-07-31 16:23:14

#include<bits/stdc++.h>

using namespace std;

#define lson i<<1,l,m
#define rson i<<1|1,m+1,r

long long x[3000],cnt[3000<<2],sum[3000<<2];
struct node
{
    int l,r,h,d;
    node() {}
    node(int l,int r,int h,int d):l(l),r(r),h(h),d(d) {}
    bool operator < (const node &a)const
    {
        return h<a.h;
    }
} line[3000];
void pushup(int i,int l,int r)
{
   if(cnt[i])
       sum[i]=x[r+1]-x[l];
   else
       sum[i]=sum[i<<1]+sum[i<<1|1];
}
void update(int ql,int qr,int v,int i,int l,int r)
{
    if(ql<=l && qr>=r){
       cnt[i]+=v;
       pushup(i,l,r);
       return ;
    }
    int m=(l+r)>>1;
    if(ql<=m)update(ql,qr,v,lson);
    if(qr>m)update(ql,qr,v,rson);
    pushup(i,l,r);
}
int main()
{
    int n,x1,y1,x2,y2,k=1,ni=0,mi=0;
    long long ans=0;
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        scanf("%d %d %d %d",&x1,&y2,&x2,&y1);
        x[++ni]=x1;
        x[++ni]=x2;
        line[++mi]=node(x1,x2,y1,1);
        line[++mi]=node(x1,x2,y2,-1);
    }
    sort(x+1,x+1+ni);
    sort(line+1,line+1+mi);
    k=unique(x+1,x+ni+1)-x-1;
    for(int i=1; i<mi; i++){
        int l=lower_bound(x+1,x+k+1,line[i].l)-x;
        int r=lower_bound(x+1,x+k+1,line[i].r)-x;
        r--;
        if(l<=r)update(l,r,line[i].d,1,1,k-1);
        ans+=sum[1]*(line[i+1].h-line[i].h);
    }
    cout<<ans<<endl;
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 37ms, 内存消耗: 504K, 提交时间: 2020-07-31 14:22:25

#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#define maxn 1010
using namespace std;

long long n,x[maxn],y[maxn],x2[maxn],y2[maxn],side[2*maxn];
int arr[maxn];
long long ans;

bool cmp(int a,int b)
{
	return y[a]>y[b];
}

int main()
{
	cin >> n;
	for (int i=0;i<n;i++) 
	{
		cin >> x[i] >> y[i] >> x2[i] >> y2[i];
		side[2*i]=x[i];
		side[2*i+1]=x2[i];
	}
	sort(side,side+2*n);
	ans=0;
	for (int i=1;i<2*n;i++)
	{
		if (side[i-1]==side[i]) continue;
		int m=0;
		for (int j=0;j<n;j++)
		{
			if (x[j]<=side[i-1] && side[i]<=x2[j]) arr[m++]=j;
		}
		sort(arr,arr+m,cmp);
		long long h=y[arr[0]],d=y2[arr[0]],w=side[i]-side[i-1];
		for (int j=1;j<m;j++)
		{
			int temp=arr[j];
			if (y[temp]>d)
			{
				ans+=(h-y[temp])*w;
				h=y[temp];
			}
			else
			{
				ans+=(h-d)*w;
				h=y[temp];
			}
			if (y2[temp]<d) d=y2[temp];
		}
		ans+=(h-d)*w;
	}
	cout << ans << endl;
}