摘要
Title: 1987. 粉刷栅栏
Tag: 差分，离散化，扫描线
Memory Limit: 64 MB
Time Limit: 1000 ms

1987. 粉刷栅栏

题意

农夫约翰发明了一种绝妙的方法来粉刷牛棚旁边的长栅栏（把栅栏想象成一维的数轴）。
他只需要在他最喜欢的奶牛贝茜身上挂一个刷子，然后在一旁悠闲的喝凉水就行了。
贝茜沿着栅栏来回走动时，会将她走过的栅栏部分涂上油漆。
贝茜从栅栏上的位置 0 处开始，共进行 N 次移动。
移动可能形如 10 L，表示向左移动 10 单位距离，也可能形如 15 R，表示向右移动 15 单位距离。
给定贝茜的 N 次移动列表，约翰想知道至少被涂抹了 2 层油漆的区域的总长度。
整个行进过程中，贝茜距离出发地的距离不会超过 $10^9$ 。

思路

题意换而言之：给一个数轴（数据范围为[-1e9,1e9]），每次给一个区间（最多 $1e5$ 个区间），每个区间进行+1操作，求多长的区间被染至少两次。

分析：

那么复杂度应该控制到 $nlogn$ ，可以使用差分来做，但是！由于数据范围是1e9，所以不能用简单的差分来做（即上图的右边作法），这样会导致超时，复杂度会到 $1e9$
由于是区间的统计，不是点的统计，所以需要先将区间转化为点

优化方案：

离散化
- 最多用到2e5个点
map
- 即上图左边的作法
- 将每个单位区间缩成一个数，比如 $1$ 就可以代表[1,2)这个区间
- 那么如果我想让[L,R]的单位区间全部加上 $1$ $1$ ，就可以让[L,R-1]给每个数都加 $1$ $1$
  - 即map[L]++ ,map[R-1+1]--
  - 即map[L]++ ,map[R]--
  - 即单位区间映射为一个整数
  - 那么此时题目就转换成了求原数组中大于等于 $2$ 的数的个数
- 由于数据范围，则求原数组不能挨个点求，但是有很多点是没有用过的（即0），最多有 $2e5$ 的数有数值，那么我们可以只考虑这些数
- 如图
  - $b_i$ 就是map标记过的点，其余的都是0
  - 那么可以看出 $b_i$ 到 $b_{i+1}-1$ 的值都是一样的，如果 $b_1$ 的前缀和 $\ge 2$ ，说明 $[b_1, b_2-1]$ 的数都是 $\ge 2$ 的，共 $b_2-1-b_1+1$ 个数，即 $b_2-b_1$ ，那么结果加上这个数即可，依此类推找下一个标记的点
扫描线
- 用扫描线的思想再推一遍，和map思想相同
- 当某个区间+1时，通常是让(L, 1), (R, -1)扔进列表中，并进行升序排序
- 之后同理

代码

map

用到 $Counter$ 类，相当于字典的升级版

'''
Author: NEFU AB-IN
Date: 2022-01-11 14:11:42
FilePath: \ACM\Acwing\1987.py
LastEditTime: 2022-01-11 16:01:48
'''

from collections import Counter

d = Counter()


def solve():
    n = int(input())
    pos = 0  #初始位置为0
    for _ in range(n):
        x, op = input().split()
        x = int(x)
        if op == 'L':
            d[pos - x] += 1
            d[pos] -= 1
            pos -= x
        else:
            d[pos] += 1
            d[pos + x] -= 1
            pos += x
    last, cnt, res = 0, 0, 0
    for x in sorted(d.keys()):
        if cnt >= 2:
            res += (x - last)
        cnt += d[x]
        last = x
    print(res)


if __name__ == "__main__":
    solve()

扫描线

'''
Author: NEFU AB-IN
Date: 2022-01-11 17:10:01
FilePath: \ACM\Acwing\1987.1.py
LastEditTime: 2022-01-11 17:13:02
'''
lst = []


def solve():
    n = int(input())
    pos = 0  #初始位置为0
    for _ in range(n):
        x, op = input().split()
        x = int(x)
        if op == 'L':
            lst.append((pos - x, 1))
            lst.append((pos, -1))
            pos -= x
        else:
            lst.append((pos, 1))
            lst.append((pos + x, -1))
            pos += x
    last, cnt, res = 0, 0, 0
    for x, y in sorted(lst):
        if cnt >= 2:
            res += (x - last)
        cnt += y
        last = x
    print(res)


if __name__ == "__main__":
    solve()