题解 P2205 【[USACO13JAN]画栅栏Painting the Fence】

· · 题解

这道题我们可以用差分的思想做，首先，每走一步相当于将走过的区间权值都加1，那么题目就可以转化为区间修改，查询>=k的值的个数，这不难想到树状数组，线段树。当然，由于区间是加上一个相同的值，所以可以使用差分优化。

Ps：差分，数组b[i]维护原数组a[i]-a[i-1]的值，原数组a[i]的值就是b[i]的前缀和，利用树状数组 线段树 可以做到区间修改(虽然被优化成了点修改)，单点查询。当在原数组[l，r）区间中加上同一个数val，相当于在差分数组中的b[l]+=val,b[r]-=val。

以上所讲，除了差分，在这题都是大材小用，本题可以用扫描线来写。

Ps：扫描线，记录一条线段的左端点l，右端点r，当你"扫描"到l时，表示你进入了这条线段，当你扫描到r时，表示你离开了这条线段，所以这条线段的覆盖区间为[l，r）。

now：此时被几条线段覆盖。

由于我们只用记录一个点被涂过几次，所以进入一条线段是将now+1，离开一条线段时将now-1，此时我们只需统计now>=k的区间。由于数据范围过大我们需要离散化，记录每一条线段的左右端点，排序一下，从一个端点到另一个端点，如果此时now>=k，就将answer加上两个端点中的点数。

具体见代码：

#include<cstdio>
#include<algorithm>
#define N 100005
using namespace std;
int n,l,len,m,now,i,ans;
char k;
//x记录这个点的坐标，val记录这个点是线段的头还是线段的尾;
struct P{int x,val;int operator<(const P&t)const{return x<t.x;}}line[N<<1];
main()
{
    scanf("%d%d",&n,&m);
    for(i=0;i<n;++i)
    {
        scanf("%d %c",&len,&k);
        //将线段拆成点;
        if(k=='R')
        {
            line[++l]=(P){now,+1};
            line[++l]=(P){now+=len,-1};
        }
        else
        {
            line[++l]=(P){now,-1};
            line[++l]=(P){now-=len,+1};
        }
    }
    sort(line+1,line+l+1);
    //"扫描..."
    now=line[1].val;
    for(i=2;i<=l;++i)
    {
        if(now>=m) ans+=line[i].x-line[i-1].x;
        now+=line[i].val;
    }
    printf("%d",ans);
}

精简过的：

#include<cstdio>
#include<algorithm>
struct P{int x,y;int operator<(const P&t)const{return x<t.x;}}e[200010];
int l,n,m,i,w,ans;char c;
inline void R(int &x){c=getchar();for(;c<48||c>57;c=getchar());for(x=0;c>47&&c<58;c=getchar())x=(x<<1)+(x<<3)+c-48;}
main()
{
    R(n);R(m);
    for(i=0;i<n;++i)
    {
        R(l);e[i<<1].x=w;
        if(getchar()=='L')
        {
            e[i<<1].y=-1;
            e[i<<1|1]=(P){w-=l,+1};
        }else
        {
            e[i<<1].y=+1;
            e[i<<1|1]=(P){w+=l,-1};
        }
    }std::sort(e,e+(n<<1));
    w=e[0].y;
    for(i=0;i+1<n<<1;w+=e[++i].y)
        if(w>=m)ans+=e[i+1].x-e[i].x;
    printf("%d",ans);
}