[USACO13JAN] Painting the Fence S – 差分,离散化

有一个刷子，一开始位于 \(0\) 点，进行 \(N \leq 10^5\) 次移动，每次向左移动若干个单位或者向右移动若干个单位。求有多少个整点被涂上了至少 \(K\) 层涂料。

Solution

难度：L2

假设刷子当前位置是 \(pos\)，下一次向右移动 \(c\) 个单位，那么这次移动会将 \([pos,pos+c)\) 范围内的所有点 \(+1\)，如果向左移动那么会将 \([pos-c,pos)\) 内的所有点 \(+1\)

于是打上差分标记，最后求前缀和就可以了

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 1000005;

struct range {
    int l,r;
} r[N];

int n,k,c,p[N],s[N];
char o;
map<int,int> mp;

signed main() {
    ios::sync_with_stdio(false);
    cin>>n>>k;
    int pos=0;
    for(int i=1;i<=n;i++) {
        cin>>c>>o;
        if(o=='L') r[i]={pos-c,pos}, pos-=c;
        else r[i]={pos,pos+c}, pos+=c;
    }
    for(int i=1;i<=n;i++) {
        mp[r[i].l]++;
        mp[r[i].r]++;
    }
    int ind=0;
    for(auto i=mp.begin();i!=mp.end();i++) {
        i->second = ++ind;
        p[ind] = i->first;
    }
    for(int i=1;i<=n;i++) {
        //cout<<r[i].l<<" "<<r[i].r<<endl;
        r[i].l=mp[r[i].l];
        r[i].r=mp[r[i].r];
    }
    for(int i=1;i<=n;i++) {
        s[r[i].l]++;
        s[r[i].r]--;
    }
    for(int i=1;i<=ind;i++) s[i]+=s[i-1];
    int ans=0;
    for(int i=1;i<ind;i++) if(s[i]>=k) ans+=p[i+1]-p[i];
    cout<<ans<<endl;
}