腾讯云网站备案吗/网站优化网络推广seo

题目背景

简而言之，从0开始，进行N次左移或者右移，每经过一段，都把墙刷一遍，问最后多长的墙被刷了两遍？
移动的次数不算大，但移动的范围很大

解题思路

段化点

在一个区间内刷一遍，这个区间范围内所有的段都加了1，很容易的想到这是题差分的题目，差分的题目通常对点做处理，这里是段
因为它最后问的是长度，所以考虑问题的时候应该是把段用来点表示

如图，将[L,L+1]段用L来表示，所以如果要将[L,R]之间刷一遍，那相当于是把段L，L+1,L+2…R-1都刷一遍，相当于+1，反映在差分数组里则：
b[L]+=1;
b[R-1+1]-=1; 即b[R]-=1;

巧用map

这里直接实现离散化比较麻烦，不如用map来的快
map会动态的维护有序不重复序列

由差分数组得原数组

因为这里数据的范围非常大，但其实我们观察差分数组的特点就能发现：

map中只存储了差分序列中b值不为0的部分
整个差分序列就应该是如图所示的，b之间夹杂着很多的0，每经过一个b，其前缀和数组会经历里程碑式的增加（前缀和是非降序的），且会稳定在一个值，直到下一个b的出现，所以我们要算原数组，即前缀和数组中大于2的有多少？
直接对b进行操作即可，用一个变量记录当前前缀和，然后如果发现它大于2了，那就拿当前b的序号-1减去上一个b的序号+1，算出这一段符合条件的长度，以此类推，整个差分数组遍历完即可算出答案。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>using namespace std;int main()
{map<int, int> b;int n;scanf("%d", &n);int x = 0, y;char s[2];while (n -- ){scanf("%d%s", &y, s);if (*s == 'R'){b[x] ++ ;b[x + y] -- ;  //x+y-1+1=x+yx += y;}else{b[x - y] ++ ;b[x] -- ;   //x-1+1=xx -= y;}}//由上可知map里存的都是差分数组里会引起前缀和变化的位置int res = 0, sum = 0, last;    //其余都是0，不会引起变化，所以只要把map遍历一遍就好了for (auto& [x, v]: b){if (sum >= 2) res += x - last;sum += v;last = x;}printf("%d\n", res);return 0;
}作者：yxc
链接：https://www.acwing.com/activity/content/code/content/2279865/
来源：AcWing