题解 P4188 【[USACO18JAN]Lifeguards S】

· · 题解

这个题一看1e5的数据显然就想到了线段树做法：先把所有时间点离散化然后建线段树维护哪些位置上的覆盖次数为一，然后一个一个奶牛去查询他们的区间。 写着写着突然发现实际上我们就是要处理出每头奶牛区间里仅由他自己覆盖的长度，也就是那些覆盖次数为一的位置上的长度和。这样我们就有了一种线性查询的算法：先用差分算出每个时间点被覆盖的次数，然后对于那些为一的地方加上他们的长度，同时维护前缀和。这样对于每头奶牛就可以o(1)地求他管辖范围内的且仅由他管辖的长度，然后愉快的求最大值输出就好了(。・∀・)ノ

#include<stdio.h>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<bitset>
#include<vector>
#include<math.h>
#include<stack>
#include<map>
#include<queue>
#define ls(x) (x<<1)
#define rs(x) ((x<<1)|1)
#define eps 1e-9
using namespace std;
int n;
struct nod
{
    int l,r,ll,rr;
}cw[100005];
int b[300005],cnt,cc[300005];
int sum[800005];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d%d",&cw[i].l,&cw[i].r);
        b[++cnt]=cw[i].r;
        cw[i].r--;
        cw[i].ll=b[++cnt]=cw[i].l;
        cw[i].rr=b[++cnt]=cw[i].r;
    }
    sort(b+1,b+1+cnt);
    int tot=unique(b+1,b+1+cnt)-b;
    for(int i=1;i<=n;i++)
    {
        cw[i].l=lower_bound(b+1,b+1+tot,cw[i].l)-b;
        cw[i].r=lower_bound(b+1,b+1+tot,cw[i].r)-b;
        cc[cw[i].l]++;
        cc[cw[i].r+1]--;
    }//离散化
    int cov=0;//总的覆盖长度
    for(int i=1;i<=tot;i++)
    {
        cc[i]+=cc[i-1];
        if(cc[i])cov+=b[i+1]-b[i];
        if(cc[i]==1)sum[i]=b[i+1]-b[i];
        sum[i]+=sum[i-1];
    }
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        ans=max(ans,cov-(sum[cw[i].r]-sum[cw[i].l-1]));
    }
    printf("%d",ans);
}

我虽然是个蒟蒻，但是自认码风清新易读，应该都看得懂吧

φ(゜▽゜*)♪