P2205 画栅栏Painting the Fence

题目描述

\(Farmer\) \(John\) 想出了一个给牛棚旁的长围墙涂色的好方法。（为了简单起见，我们把围墙看做一维的数轴，每一个单位长度代表一块栅栏）他只是简单的把刷子蘸满颜料，系在他最喜欢的奶牛\(Bessie\)上，然后让\(Bessie\)来回地经过围墙，自己则在一旁喝一杯冰镇的凉水。（……-_-|||) \(Bessie\) 经过的所有围墙都会被涂上一层颜料。\(Bessie\)从围墙上的位置\(0\)出发，并将会进行\(N\)次移动\((1 <= N <= 100,000\))。比如说，“\(10 L\)”的意思就是\(Bessie\)向左移动了\(10\)个单位。再比如说“\(15 R\)”的意思就是\(Bessie\)向右移动了\(15\)个单位。给出一系列\(Bessie\)移动的清单。\(FJ\) 想知道有多少块栅栏涂上了至少\(K\)层涂料。注意：\(Bessie\)最多会移动到离原点\(1,000,000,000\)单位远的地方。

输入输出格式

输入格式：

第1行： 两个整数： \(N K\)

第\(2...N+1\) 行： 每一行都描述了\(Bessie\)的一次移动。 （比如说 “\(15 L\)"）

输出格式：

一个整数：被至少涂上\(K\)层涂料的栅栏数

---

不知道为什么，一开始死活想不到咋离散。。

其实只需要取出现过的区间就行了。

多次修改区间一次询问，差分会比较快，\(O(1)\)修改,\(O(n)\)询问了。

code：

#include <cstdio>

#include <algorithm>

using namespace std;

const int N=200010;

int n,k;

int a[N];

char c;

struct node

{

    int d,loc;

    friend bool operator <(node n1,node n2)

    {

        return n1.loc<n2.loc;

    }

}t[N],f[N];

int main()

{

    scanf("%d%d",&n,&k);

    int to,now=0,cnt=0;

    for(int i=1;i<=n;i++)

    {

        scanf("%d %c",&to,&c);

        if(c=='R')

        {

            now+=to,a[i]=now;

            t[++cnt].loc=a[i-1];

            t[cnt].d=1;

            t[++cnt].loc=a[i];

            t[cnt].d=-1;

        }

        else

        {

            now-=to,a[i]=now;

            t[++cnt].loc=a[i];

            t[cnt].d=1;

            t[++cnt].loc=a[i-1];

            t[cnt].d=-1;

        }

    }

    sort(t+1,t+1+cnt);

    int cnt0=0;

    for(int i=1;i<=cnt;i++)

    {

        if(f[cnt0].loc==t[i].loc)

            f[cnt0].d+=t[i].d;

        else

            f[++cnt0].d=f[cnt0-1].d+t[i].d,f[cnt0].loc=t[i].loc;

    }

    int ans=0;

    for(int i=1;i<cnt0;i++)

        if(f[i].d>=k)

            ans+=f[i+1].loc-f[i].loc;

    printf("%d\n",ans);

    return 0;

}

---

2018.5.4