题解 P3875 【[TJOI2010]被污染的河流】

中二病 · 2019-04-27 20:43:41 · 题解

扫描线，用线段树维护。
把每个矩形左边界和右边界存储，给左边界赋值1，右边界赋值-1，把线段排序，然后依次处理每个线段，给线段所在的区间加上付的值，把每个值>0的区间加到ans里就是当前被矩形覆盖的线的长度，再乘上距离下一个线段之间的距离，就是这两个线段之间覆盖矩形的面积。
然后考虑用线段树处理。先想到用lazy_tag进行区间修改，但其实只有+1和-1的操作并且都是成对出现的，所以只要在push_up的时候对cnt[i]>0的i区间更新sum即可

if(cnt[qaq])
sum[qaq]=r-l+1;
else sum[qaq]=sum[left(qaq)]+sum[right(qaq)];

然后这个题坐标全是整数且数据不大，所以偷个懒不用离散化

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int N=100010;
struct pg
{
    int x;
    int y1;
    int y2;
    int flag;
}line[N*5];
int cnt[N*10],sum[N*10];
int n;
bool cmp(pg a,pg b)
{
    return a.x<b.x;
}
int left(int qaq)
{
    return qaq<<1;
}
int right(int qaq)
{
    return qaq<<1|1;
}
void push_up(int qaq,int l,int r)
{
    if(cnt[qaq])
        sum[qaq]=r-l+1;
    else sum[qaq]=sum[left(qaq)]+sum[right(qaq)];
}
void change(int qaq,int l,int r,int nl,int nr,int k)
{
    if(nl<=l&&nr>=r)
    {
        cnt[qaq]+=k;
        push_up(qaq,l,r);
        return ;
    }
    int mid=(l+r)>>1;
    if(nl<=mid)change(left(qaq),l,mid,nl,nr,k);
    if(nr>mid)change(right(qaq),mid+1,r,nl,nr,k);
    push_up(qaq,l,r);
}
int main()
{
    cin>>n;
    int X1,X2,Y1,Y2;
    int tot=0;
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d%d%d",&X1,&Y1,&X2,&Y2);
        if(X1>X2)swap(X1,X2);
        if(Y1>Y2)swap(Y1,Y2);
        if (X1==X2)
        {
             line[++tot].x=X1-1;line[tot].y1=Y1;line[tot].y2=Y2;line[tot].flag=1;
             line[++tot].x=X2+1;line[tot].y1=Y1;line[tot].y2=Y2;line[tot].flag=-1;
         }
         else
         {
             line[++tot].x=X1;line[tot].y1=Y1-1;line[tot].y2=Y2+1;line[tot].flag=1;
             line[++tot].x=X2;line[tot].y1=Y1-1;line[tot].y2=Y2+1;line[tot].flag=-1;
         }
    }
    sort(line+1,line+tot+1,cmp);
    int ans=0;
    for(int i=1;i<=tot;i++)
    {
        //cout<<sum[1]<<endl;
            ans+=sum[1]*(line[i].x-line[i-1].x);
            change(1,0,100010,line[i].y1,line[i].y2-1,line[i].flag);
    }
    cout<<ans;
    return 0;
}

如果要进行离散化，对所有的x值排序并去重，标上序号，用c[i]表示序号为i的x值，然后再push_up时改成sum[qaq]=c[r]-c[l]+1即可