题解 P5490 【【模板】扫描线】

题解

看了怎么多题解，竟然没有一篇是下传标记的。

我来写一份常规的下传标记的做法。

我们需要维护区间最小值和最小值的个数

对于一个询问，如果区间最小值>0，那么返回区间长长度，否则说明区间有些地方是0，那么答案就是区间长度-最小值个数（长度）

然后就是普通线段树操作了，不需要标记用优化。

代码

#include<bits/stdc++.h>
using namespace std;
#define next Next
#define last Last
#define int long long
const int N=1e6+5;
int n,gs,len,b[N],mi[N*4],lazy[N*4],sum[N*4],Len[N*4];
struct node{
    int val,l,r,opt;
}a[N];
/*char buf[1<<21],*p1=buf,*p2=buf;
inline int gc(){return p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++;}*/
#define gc getchar
inline int read()
{
    int ret=0,f=0;char c=gc();
    while(!isdigit(c)){if(c=='-')f=1;c=gc();}
    while(isdigit(c)){ret=ret*10+c-48;c=gc();}
    if(f)return -ret;return ret;
}
void pushup(int nod)
{
    mi[nod]=min(mi[nod*2],mi[nod*2+1]);
    if(mi[nod]==mi[nod*2])sum[nod]=sum[nod*2];
    else sum[nod]=0;
    if(mi[nod]==mi[nod*2+1])sum[nod]+=sum[nod*2+1];
}
void pushdown(int nod)
{
    if(lazy[nod]==0)return;
    mi[nod*2]+=lazy[nod];
    mi[nod*2+1]+=lazy[nod];
    lazy[nod*2]+=lazy[nod];
    lazy[nod*2+1]+=lazy[nod];
    lazy[nod]=0;   
}
void build(int nod,int l,int r)
{
    Len[nod]=b[r+1]-b[l];
    if(l==r)
    {
        sum[nod]=Len[nod];
        return;
    }
    int mid=(l+r)/2;
    build(nod*2,l,mid);
    build(nod*2+1,mid+1,r);
    pushup(nod);
}
void change(int nod,int l,int r,int L,int R,int val)
{
    if(l==L&&r==R)
    {
        mi[nod]+=val;
        lazy[nod]+=val;
        return;
    }
    pushdown(nod);
    int mid=(l+r)/2;
    if(R<=mid)change(nod*2,l,mid,L,R,val);
    else if(L>mid)change(nod*2+1,mid+1,r,L,R,val);
    else{
        change(nod*2,l,mid,L,mid,val);
        change(nod*2+1,mid+1,r,mid+1,R,val);
    }
    pushup(nod);
}
int find(int nod,int l,int r,int L,int R)
{
    if(l==L&&r==R)
    {
        if(mi[nod]>0)return Len[nod];
        return Len[nod]-sum[nod];
    }
    pushdown(nod);
    int mid=(l+r)/2;
    if(R<=mid)return find(nod*2,l,mid,L,R);
    else if(L>mid)return find(nod*2+1,mid+1,r,L,R);
    else return find(nod*2,l,mid,L,mid)+find(nod*2+1,mid+1,r,mid+1,R);
    pushup(nod);
}
bool cmp(node a,node b)
{
    return a.val<b.val;
}
signed main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        int x1=read(),y1=read(),x2=read(),y2=read();
        a[++gs]=(node){x1,y1,y2,1};
        a[++gs]=(node){x2,y1,y2,-1};
        b[++len]=y1;
        b[++len]=y2;
    }
    sort(b+1,b+len+1);
    len=unique(b+1,b+len+1)-b-1;
    build(1,1,len-1);
    for(int i=1;i<=gs;i++)
    {
        a[i].l=lower_bound(b+1,b+len+1,a[i].l)-b;
        a[i].r=lower_bound(b+1,b+len+1,a[i].r)-b;
    }
    sort(a+1,a+gs+1,cmp);
    int ans=0;
    for(int i=1;i<gs;i++)
    {
        if(a[i].l<a[i].r)change(1,1,len-1,a[i].l,a[i].r-1,a[i].opt);
        ans=ans+find(1,1,len-1,1,len-1)*(a[i+1].val-a[i].val);
    }
    cout<<ans;
}