Picture

C++(g++ 7.5.0) 解法, 执行用时: 7ms, 内存消耗: 1052K, 提交时间: 2022-08-09 11:02:24

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const double EPS=1e-8;
const int INF=2e9;
const LL LNF=2e18;
const int MAXN=1e4+10;
struct line
{
    int le, ri, h;
    int id;
    bool operator<(const line &a)const{
        return h<a.h;
    }
}Line[MAXN];
int X[MAXN<<1], times[MAXN<<2], block[MAXN<<2], len[MAXN];
bool usedl[MAXN<<2], usedr[MAXN<<2];
void push_up(int u, int l, int r)
{
    if(times[u]>0)
    {
        len[u]=X[r]-X[l];
        block[u]=1;
        usedl[u]=usedr[u]=true;
    }
    else
    {
        if(l+1==r)
        {
            len[u]=0;
            block[u]=0;
            usedl[u]=usedr[u]=false;
        }
        else
        {
            len[u] = len[u*2] + len[u*2+1];
            block[u] = block[u*2] + block[u*2+1];
            if(usedr[u*2] && usedl[u*2+1])
                block[u]--;
            usedl[u] = usedl[u*2];
            usedr[u] = usedr[u*2+1];
        }
    }
}
void add(int u, int l, int r, int x, int y, int v)
{
    if(x<=l && r<=y)
    {
        times[u]+=v;
        push_up(u,l,r);
        return;
    }

    int mid = (l+r)>>1;
    if(x<=mid-1) add(u*2,l,mid,x,y,v);
    if(y>=mid+1) add(u*2+1,mid,r,x,y,v);
    push_up(u, l, r);
}
int main()
{
    int n;
    while(scanf("%d", &n)!=EOF)
    {
        for(int i=1; i<=n; i++)
        {
            int x1, y1, x2, y2;
            scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
            Line[i].le=Line[i+n].le=x1;
            Line[i].ri=Line[i+n].ri=x2;
            Line[i].h=y1;Line[i+n].h=y2;
            Line[i].id=1;Line[i+n].id=-1;
            X[i]=x1;
            X[i+n]=x2;
        }
        sort(Line+1,Line+1+2*n);
        sort(X+1,X+1+2*n);
        int m=unique(X+1,X+1+2*n)-(X+1);
        memset(times,0,sizeof(times));
        memset(len,0,sizeof(len));
        memset(block,0,sizeof(block));
        memset(usedl,false,sizeof(usedl));
        memset(usedr,false,sizeof(usedr));
        int ans=0,pre_len=0;
        Line[2*n+1].h=Line[2*n].h;
        for(int i = 1; i<=2*n; i++)
        {
            int l=upper_bound(X+1,X+1+m,Line[i].le)-(X+1);
            int r=upper_bound(X+1,X+1+m,Line[i].ri)-(X+1);
            add(1,1,m,l,r,Line[i].id);
            ans+=abs(len[1]-pre_len);
            ans+=2*block[1]*(Line[i+1].h-Line[i].h);
            pre_len=len[1];
        }

        printf("%d\n", ans);
    }
}

C++14(g++5.4) 解法, 执行用时: 8ms, 内存消耗: 616K, 提交时间: 2019-11-05 17:59:43

//Author:XuHt
#include <cmath>
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 20006, INF = 0x3f3f3f3f;
int n, Max = -INF, Min = INF, tot, ans, pre;
struct P {
	int l, r, h, k;
	bool operator < (const P p) const {
		return h < p.h || (h == p.h && k > p.k);
	}
} a[N];
struct T {
	int sum, num, len;
	bool l, r;
} t[N<<2];

void add(int l, int r, int h, int k) {
	a[++tot].l = l;
	a[tot].r = r;
	a[tot].h = h;
	a[tot].k = k;
}

void work(int p, int l, int r) {
	if (t[p].sum) {
		t[p].num = t[p].l = t[p].r = 1;
		t[p].len = r - l + 1;
	} else if (l == r) t[p].len = t[p].num = t[p].l = t[p].r = 0;
	else {
		t[p].len = t[p<<1].len + t[p<<1|1].len;
		t[p].num = t[p<<1].num + t[p<<1|1].num;
		if (t[p<<1].r && t[p<<1|1].l) --t[p].num;
		t[p].l = t[p<<1].l;
		t[p].r = t[p<<1|1].r;
	}
}

void change(int p, int l, int r, int L, int R, int k) {
	if (l >= L && r <= R) {
		t[p].sum += k;
		work(p, l, r);
		return;
	}
	int mid = (l + r) >> 1;
	if (L <= mid) change(p << 1, l, mid, L, R, k);
	if (R > mid) change(p << 1 | 1, mid + 1, r, L, R, k);
	work(p, l, r);
}

int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		int x1, y1, x2, y2;
		scanf("%d %d %d %d", &x1, &y1, &x2, &y2);
		Max = max(Max, max(x1, x2));
		Min = min(Min, min(x1, x2));
		add(x1, x2, y1, 1);
		add(x1, x2, y2, -1);
	}
	if (Min <= 0) {
		for (int i = 1; i <= tot; i++) {
			a[i].l += 1 - Min;
			a[i].r += 1 - Min;
		}
		Max -= Min;
	}
	sort(a + 1, a + tot + 1);
	for (int i = 1; i <= tot; i++) {
		change(1, 1, Max, a[i].l, a[i].r - 1, a[i].k);
		while (a[i].h == a[i+1].h && a[i].k == a[i+1].k) {
			i++;
			change(1, 1, Max, a[i].l, a[i].r - 1, a[i].k);
		}
		ans += abs(t[1].len - pre);
		pre = t[1].len;
		ans += t[1].num * (a[i+1].h - a[i].h) << 1;
	}
	cout << ans << endl;
	return 0;
}

C++ 解法, 执行用时: 12ms, 内存消耗: 3712K, 提交时间: 2022-02-18 17:31:00

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
const int N=2e5+7;
const int mod=1e9+7;

struct E{
	int l,r,h,f;
	bool operator <(const E &a)const{ //扫描线按高度排序 
		return h<a.h;
	}
}e[N];

struct Node{ //线段树 
	int l,r,len,s,num; //分别为结点左右端点、区间长度、合并标记和线段个数 
	bool lc,rc; //左右儿子合并标记 
}tr[N<<2];

#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((tr[p].l+tr[p].r)>>1)

void pushup(int p){ //向上合并 
	if(tr[p].s){
		tr[p].len=tr[p].r-tr[p].l+1;
		tr[p].lc=tr[p].rc=1;
		tr[p].num=1;
	}else{
		tr[p].len=tr[ls].len+tr[rs].len;
		tr[p].lc=tr[ls].lc;
		tr[p].rc=tr[rs].rc;
		tr[p].num=tr[ls].num+tr[rs].num-(tr[ls].rc&tr[rs].lc);
	}
}

void build(int p,int l,int r){ //建树 
	tr[p].l=l;tr[p].r=r;
	if(l==r) return;
	build(ls,l,mid);
	build(rs,mid+1,r);
}
 
void update(int p,int ql,int qr,int k){ //区间修改 
	if(ql==tr[p].l&&qr==tr[p].r){
		tr[p].s+=k;
		pushup(p);
		return;
	}
	if(qr<=mid) update(ls,ql,qr,k);
	else if(ql>mid) update(rs,ql,qr,k);
	else update(ls,ql,mid,k),update(rs,mid+1,qr,k);
	pushup(p);
} 

signed main(){
	int n;
	while(cin>>n){
		int x1,x2,y1,y2,mx=-inf,mi=inf;
		int tot=0;
		for(int i=0;i<n;i++){
			cin>>x1>>y1>>x2>>y2;
			mx=max(mx,max(x1,x2));
			mi=min(mi,min(x1,x2));
			e[tot++]=(E){x1,x2,y1,1};
			e[tot++]=(E){x1,x2,y2,-1};
		}
		sort(e,e+tot);
		int ans=0,lst=0;
		build(1,mi,mx-1);
		for(int i=0;i<tot;i++){
			update(1,e[i].l,e[i].r-1,e[i].f);
			ans+=abs(tr[1].len-lst);
			ans+=(e[i+1].h-e[i].h)*2*tr[1].num;
			lst=tr[1].len;
		}
		cout<<ans<<"\n";
	}
	return 0;
}

详情