20分代码求助
查看原帖
20分代码求助
242039
goodier楼主2021/10/1 14:55
#include <iostream>
#include <stdio.h>
#include <algorithm>
#define ll unsigned long long
using namespace std;
const int N = 1e6 + 10;
ll cnt,sum,n,t,y[N >> 1],lsy[N >> 1];
struct str{
    ll x,y1,y2,k1;
}smx[N >> 1];
struct stree{
    ll len,l,r,k2;
}st[N >> 2];
void pushup(ll p)
{
	if(st[p].k2)
	{
		st[p].len = lsy[st[p].r + 1] - lsy[st[p].l];
	}
	else
	{
		if(st[p].l == st[p].r) st[p].len = 0; 
		else st[p].len = st[p * 2].len + st[p * 2 + 1].len;
	}
}
void lsh()
{
    sort(y + 1, y + cnt + 1);
    t = unique(y + 1,y + cnt + 1)-y-1;
    swap(y,lsy);
}
bool cmp1(str a,str b)
{
    return a.x < b.x;
}
ll find(ll x)
{
    return lower_bound(lsy + 1,lsy + cnt + 1,x)-lsy;
}
void build(ll p,ll l,ll r)
{
    if(l == r)
    {
        st[p].l = st[p].r = l;
        return;
    }
    st[p].l = l;
    st[p].r = r;
    ll mid = (l + r) / 2;
    build(p * 2,l,mid);
    build(p * 2 + 1,mid + 1,r);
    return;
}
void change(ll p,ll l,ll r,ll k)
{
    if(l <= st[p].l && st[p].r <= r)
    {
        st[p].k2 += k;
        pushup(p);
        return;
    }
    ll mid =  (st[p].l + st[p].r) >> 1;
    if(l <= mid)
    {
        change(p * 2,l,r,k);
    }
    if(r > mid)
    {
        change(p * 2 + 1,l,r,k);
    }
    pushup(p);
}
int main()
{
    scanf("%lld",&n);
    for(ll i = 1; i <= n; i++)
    {
        ll a,b,c,d;
        scanf("%lld%lld%lld%lld",&a,&b,&c,&d);
        smx[++cnt].x = a,smx[cnt].y1 = b,smx[cnt].y2 = d,smx[cnt].k1 = 1;
        y[cnt] = b;
        smx[++cnt].x = c,smx[cnt].y1 = b,smx[cnt].y2 = d,smx[cnt].k1 = -1;
        y[cnt] = d;
    }
    sort(smx + 1,smx + cnt + 1,cmp1);
    lsh();
    build(1,1,t - 1);
    for(ll i = 1; i <= cnt; i++)
    {
		change(1,find(smx[i].y1),find(smx[i].y2) - 1,smx[i].k1);
        sum += st[1].len * (smx[i + 1].x - smx[i].x);
    }
    printf("%lld",sum);
    return 0;
}
2021/10/1 14:55
加载中...