题意：
有n个盒子 一个小球 和m次猜测序列(a1-am)
小球一开始位于初始位置s 第一次猜测前可以移动一次小球（移动到相邻位置或者原地不动）然后每次猜测可以移动一次小球 所以最多移动m+1次
问有多少对 s(起始位置) t(结束位置) 满足不被猜测到
题解：
- 显然可以观察出一个结论 对一小球的某一个初始位置 它所能到达的结束位置的集合里的所有元素是连续的 所以对于该起始位置有一个左界(向左最远能到达哪里) 和一个右界
- 假设要求出左边界 那么小球只会进行两种操作 等待和左移 右边界同理
- 所以这里可以得到一个$O(nm)$复杂度的算法 可惜过不得
- 可以将其看作是一个 $m*n$ 的图 每行都会有一个障碍 位于 $(i,ai)$ , $(0,i)$表示第i个小球的起始位置 所以问题就转化为小球一开始处于第0行 可以向下向左下向右下移动 求出每个初始点的左右界
- 设 L[i] 为向左移动过程中原地等待的次数
- 从m~1倒着放入障碍 显然 当前障碍会影响 起始点位于：ai+当前行数 的小球（该小球一路左下移动 直到遇到该障碍不得不向下移动） 当他向下移所到达的点 完全等效于 起始点位于 ai+当前行数+1 的小球， 一路向左下移动到达的点 因为i+1~m的状态已经处理好了 所以直接继承即可 记得加一 也就是当前不得不向下移动一次
- 因为倒着放入障碍 所以起始点+1的小球也是一定能到该位置的
#include <bits/stdc++.h> using namespace std; const int N=3e5+100; const int T=1e5; #define ll long long int n,m,a[N],L[N],R[N]; int main() { cin>>n>>m; if(n==1)return printf("0"),0; for(int i=1;i<=m;i++)scanf("%d",&a[i]); for(int i=m;i>=1;i--) { L[i+a[i]+T]=L[i+a[i]+1+T]+1; R[a[i]-i+T]=R[a[i]-i-1+T]+1; } ll ans=0; for(int i=1;i<=n;i++) { int l=max(1,i-(m+1)+L[i+T]); int r=min(n,i+(m+1)-R[i+T]); ans+=1ll*(r-l+1); } cout<<ans; return 0; }