题目内容

塔子哥有一个一维的坐标系，上面一共有$n$个点，依次为$1,2,…,n$，他初始时位于$k$。现在她按照一个指令集合运动，如下:

·指令$L$:向左移动一个单位，如果当前位于$1$，则原地不动。

·指令$R$:向右移动一个单位，如果当前位于$n$，则原地不动。

这里提供一种时间复杂度为 $O(N + M)$ 的做法： 观察到，dp数组有且仅有 00000111110101011111000 这种前缀连续 1 中间可能有 01 交错段后缀连续 1 的情况，考虑存储 dp 数组内 1 出现的第一个位置和最后一个位置，被 1 完全包含的 0 出现的第一个位置和最后一个位置，发现可以使用这些信息直接转移。

#include <bits/stdc++.h>

using namespace std;

int n;