神建模+dp——cf1236E

首先将两个人的所有可能的操作建立成一个模型：m+2行n列的矩阵

序列A对应图上的格子（i,Ai）,第0行作为起点，最后一行作为终点，每个点可以向左下，下，右下走，每种可行的情况对应图上的一条路径

推出一个性质：对于第一行每个起点，其能到达的终点范围必定是一个连续的区间

那么我们只要求出每个起点能到达的范围[l,r]，设第i个起点在向左下移动时被挡住L[i]步，那么其最后的位置是i+m+1-L[i]

考虑只向左走的情况，对于每个起点，当然是能向左走就向左走。除非在某一步被障碍物挡住了

考虑到上面的障碍作用更大（上面的障碍可能导致下面的障碍失效）所以自下往上考虑每个障碍物的影响

　　第i行的障碍物只会影响起点(0,A[i]+i)，这个点被挡住了一步,那么L[i]可以先从L[i+1]继承状态，再+1，

　　因为第i个起点向左下被挡住，向下走到的那个点，等价于第i+1个点不被挡住时走到该行的状态，因为比第i+1个点多被挡住了一次，所以需要+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;
}