要开学了+帮同学求助
  • 板块灌水区
  • 楼主题解测试器
  • 当前回复2
  • 已保存回复2
  • 发布时间2020/8/31 02:51
  • 上次更新2023/11/5 13:55:22
查看原帖
要开学了+帮同学求助
172159
题解测试器楼主2020/8/31 02:51

感到焦虑,恐慌,迷茫,……呜

不知道你们怎么样

顺便帮个同学求助扫描线

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
long long n,ans=0;
long long p[200003],lp=0,l,lq=0;
long long x1,y1,x2,y2;
struct XXX{long long y,val,lx,rx;}q[200003];
long long f[800003],len[800003];
bool cmp(struct XXX u,struct XXX v){return u.y<v.y;}
void upd(int w,int l,int r)
{
    if(f[w])
        len[w]=p[r+1]-p[l];
    else
        len[w]=len[w*2]+len[w*2+1];
}
void add(int w,int l,int r,int u,int v,int k)
{
    if(p[r+1]<= u || v<=p[l])
        return;
    if(u<=p[l] && p[r+1]<=v)
    {
        f[w]+=k;
        upd(w,l,r);
        return;
    }
    int mid=(l+r)/2;
    add(w*2,l,mid,u,v,k);
    add(w*2+1,mid+1,r,u,v,k);
    upd(w,l,r);
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld%lld",&x1,&y1,&x2,&y2);
        p[++lp]=x1;p[++lp]=x2;
        q[++lq]=(struct XXX){y1,1,x1,x2};
        q[++lq]=(struct XXX){y2,-1,x1,x2};
    }
    sort(p+1,p+lp+1);
    l=unique(p+1,p+lp+1)-p-1;
    sort(q+1,q+lq+1,cmp);
    for(int i=1;i<lq;i++)
    {
        add(1,1,l-1,q[i].lx,q[i].rx,q[i].val);
        ans+=(q[i+1].y-q[i].y)*len[1];
    }
    printf("%lld",ans);
    return 0;
}
2020/8/31 02:51
加载中...