P9478题解

· · 题解

闲话

这是应该是这几年最简单的题了，连我这个菜鸡都会 95 分做法。

思路

前面 95 分其实就是一个扫描线模板，不懂的可以左转题目。

这题与扫描线模板有些不同，此题给出的是格子的坐标，而扫描线模板给出的是点的坐标，我们在读入时只需将它们的右下角坐标都加 1 即可。

对于斜线，由于最多只有 5 条，且长度不超过 10^5，只需将斜线暴力拆成一个一个点即可。

接下来讲满分做法。

如果只有横线或竖线，那么总面积是好求的，如果只有斜线也可以将它们暴力合并，算出总面积，考虑如何将这两部分合并。

事实上，由于斜线的性质，一条斜线最多只会与一条横线或竖线的一个点相交，显然这个点是好求的，但是如果一条斜线与多条横线或竖线相交在同一个位置就会算重，所以可以用一个 \operatorname{map} 记录哪些点已经被算过了，答案就是这两部分的面积和减去重叠部分。

代码

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>

using namespace std;

struct node{
    int cnt;
    long long x,X,y;
}l[1000005],e[15];
struct tree{
    int l,r,lazy;
    long long val;
}t[4000005];
bool cmp(node a,node b) {
    return a.y<b.y;
}
long long n,tot,TOT,sum,a[1000005],ans;
map<pair<int,int>,int>Map;
void build(int p,int l,int r) {
    if(l>r) return;
    t[p].l=l,t[p].r=r,t[p].lazy=t[p].val=0;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(p*2,l,mid),build(p*2+1,mid+1,r);
}
void update(int p) {
    if(t[p].lazy) t[p].val=a[t[p].r+1]-a[t[p].l];
    else t[p].val=t[p*2].val+t[p*2+1].val;
}
void change(int p,int L,int R,int cnt) {
    if(t[p].l==L&&t[p].r==R) {
        t[p].lazy+=cnt;
        update(p);
        return;
    }
    int mid=(t[p].l+t[p].r)>>1;
    if(R<=mid) change(p*2,L,R,cnt);
    else if(L>mid) change(p*2+1,L,R,cnt);
    else change(p*2,L,mid,cnt),change(p*2+1,mid+1,R,cnt);
    update(p);
}
int main() {
    cin>>n>>n>>n>>n;
    for(int i=1;i<=n;i++) {
        int op,x,X,y,Y;
        cin>>op>>x>>y>>X>>Y;
        if(op==3) e[++sum].x=x,e[sum].X=X,e[sum].y=y;
        else l[++tot*2-1].x=x,l[tot*2-1].X=X,l[tot*2-1].y=y,l[tot*2-1].cnt=1,l[tot*2].x=x,l[tot*2].X=X,l[tot*2].y=Y,l[tot*2].cnt=-1,a[tot*2-1]=x,a[tot*2]=X;
    }
    int cnt=1;
    while(cnt) {
        cnt=0;
        for(int i=1;i<=sum;i++) 
        for(int j=1;j<=sum;j++) 
        if(j!=i&&e[i].y&&e[j].y&&e[i].y-e[i].x==e[j].y-e[j].x) 
        if(e[j].x>=e[i].x&&e[j].X<=e[i].X||e[i].x<=e[j].x&&e[j].x<=e[i].X&&e[i].X<=e[j].X) cnt++,e[i].x=min(e[i].x,e[j].x),e[i].X=max(e[i].X,e[j].X),e[i].y=min(e[i].y,e[j].y),e[j].y=0;
    }
    for(int i=1;i<=sum;i++) {
        if(!e[i].y) continue;
        ans+=e[i].X-e[i].x+1;
        for(int j=1;j<=2*tot;j+=2) {
            long long x=l[j].y-e[i].y+e[i].x,y=l[j].x+e[i].y-e[i].x;
            if(l[j].x==l[j].X&&l[j].x>=e[i].x&&l[j].x<=e[i].X&&y>=l[j].y&&y<=l[j+1].y) {
                if(!Map[make_pair(l[j].x,y)]) Map[make_pair(l[j].x,y)]=1,ans--;
            }
            else if(l[j].y==l[j+1].y&&l[j].y>=e[i].y&&l[j].y<=e[i].y+e[i].X-e[i].x&&x>=l[j].x&&x<=l[j].X) if(!Map[make_pair(x,l[j].y)]) Map[make_pair(x,l[j].y)]=1,ans--;
        }
    }
    for(int i=1;i<=2*tot;i++) {
        l[i].x--;
        if(i&1) l[i].y--,a[i]--;
    }
    sort(a+1,a+1+2*tot),sort(l+1,l+1+2*tot,cmp),TOT=unique(a+1,a+1+2*tot)-a-1,build(1,1,TOT);
    for(int i=1;i<2*tot;i++) {
        int L=lower_bound(a+1,a+TOT+1,l[i].x)-a,R=lower_bound(a+1,a+TOT+1,l[i].X)-a-1;
        change(1,L,R,l[i].cnt),ans+=t[1].val*(l[i+1].y-l[i].y);
    }
    cout<<ans;
    return 0;
}