介绍一种另解，以下称“征服”为“拓展”。
对于这些需要拓展，且拓展的时间有上界的题，我们通常都会有一个trick。那就是对于一个点 \(x\)，用它可以拓展到的点 \(y\) 的时间上界把 \(x\) 的时间上界继续缩小。用到这种trick的题有 P9755 [CSP-S 2023] 种树、[ABC304Ex] Constrained Topological Sort 等，以及本题。
关于这个trick在本题的具体体现，不妨设 \(t_i\) 为点 \(i\) 被拓展到的时间，\(a_i\) 为点 \(i\) 被拓展时间的上界。定义 \(L_i\) 为从点 \(i\) 拓展到点 \(1\)，满足 \(\forall i\in[1,i],t_i\leq a_i\) 的最大的 \(t_i\)。则 \(L_i\) 的转移式为：
\[L_i=\begin{cases}a_i&i=1\\min(L_{i-1}-1,a_i)&i>1\end{cases} \]这是因为从 \(i\) 拓展到 \(i-1\) 需要 \(1\) 的时间，且也要满足 \(t_i\leq a_i\)。
同理，定义 \(R_i\) 为从点 \(i\) 拓展到点 \(n\)，满足 \(\forall i\in[i,n],t_i\leq a_i\) 的最大的 \(t_i\)。则：
\[R_i=\begin{cases}a_i&i=n\\min(R_{i+1}-1,a_i)&i<n\end{cases} \]容易发现 \(L_i\) 是单调递减的，\(R_i\) 是单调递增的。
求出 \(L_i\) 和 \(R_i\) 有什么用呢？考虑当前枚举了一个起始点 \(P\)。对于除了 \(P\) 外的所有点，设其权值为
\[val_i=\begin{cases}L_i&i<P\\R_i&i>P\end{cases} \]贪心的想，要想满足每个点的时间上界，我们可以优先拓展那些 \(val\) 值小的点。那这样思路就很明显了，就像 dijkstra 一样，每次把当前可以拓展的点扔进一个小根堆里，按 \(val_i\) 排序，每次从堆顶取出一个点就相当于拓展了这个点，并把时间计数器 \(cnt+1\)，接着再把这个点可以拓展到且还未被拓展的点扔进堆里。判无解就是判当一个点被从堆顶取出时，当前的时间计数器是否满足 \(cnt\leq val_i\)，如果不满足，则说明点 \(P\) 不能作为起始点。这里贴一份代码：
#include<bits/stdc++.h>
#define int long long
#define fr first
#define sc second
using namespace std;
int Rana;
int n,a[200005],L[200005],R[200005],ans;
struct node{
int x,w;
};
inline bool operator <(const node A,const node B){
return A.w>B.w;
}
int vis[200005],val[200005];
inline bool solve(int P){
priority_queue <node> q;
for(int i=1;i<=n;i++){
val[i]=(i<P?L[i]:R[i]),vis[i]=0;//初始化val
}
q.push({P,val[P]});
int cnt=0;//时间计数器
while(q.size()){
int x=q.top().x;
q.pop(),cnt++,vis[x]=1;
if(cnt>val[x])return false;//P不能作为起始点
if(!vis[x-1]&&x-1>=1)q.push({x-1,val[x-1]});//往左拓展
if(!vis[x+1]&&x+1<=n)q.push({x+1,val[x+1]});//往右拓展
}
return true;
}
inline int read(){
register int x(0),t(0);
static char ch=getchar();
while(!isdigit(ch)){t|=(ch=='-'),ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48),ch=getchar();}
return t?-x:x;
}
signed main(){
Rana=read();while(Rana--){
n=read(),ans=0;
for(int i=1;i<=n;i++){
a[i]=read();
}
L[1]=a[1];
for(int i=2;i<=n;i++){
L[i]=min(L[i-1]-1,a[i]);
}
R[n]=a[n];
for(int i=n-1;i>=1;i--){
R[i]=min(R[i+1]-1,a[i]);
}
for(int i=1;i<=n;i++){
ans+=solve(i);
}
cout<<ans<<'\n';
}return 0;
}
但这样做是 \(O(n^2)\) 的，考虑如何优化。容易发现，对于一个起始点 \(P\)
\[t_i=\begin{cases}P-i+1+\sum\limits_{j=P+1}^{n}[R_j<=L_i]&i<P\\i-P+1+\sum\limits_{j=1}^{P-1}[L_j<=R_i]&i>P\end{cases} \]这是为什么？考虑 \(i<P\) 的情况。对于 \(\sum\) 前面那一部分，如果想要拓展到 \(i\)，则需先将 \([i+1,P+1]\) 的点扩展，因为开始在 \(P\) 时间就为 \(1\)，所以要加 \(1\)。对于 \(\sum\) 的部分，则表示在点 \(P\) 右边的需要比 \(i\) 先拓展的点的个数，因为 \(R_i\) 单调递增的性质，可以发现这些点为以 \(P+1\) 为开头的一段前缀，正确性显然。\(R_i\) 同理。
但是若是有 \(i<P,j>P,L_i=R_j\) 的情况呢？这样的情况放在暴力代码中，\(val_i\) 是等于 \(val_j\) 的，且它们一定是先拓展一个，再拓展另一个。也就是说，\(t_i+1=t_j\) 或者 \(t_j+1=t_i\)，判断是否可行则是看 \(\max(t_i,t_j)\) 是否小于 \(val_i\)。而在上面的式子中，\(t_i\) 和 \(t_j\) 都会是 \(\max(t_i,t_j)\)，而这对可行判断是没有影响的。
有了这个式子，我们如何快速判断可不可行？我们可以将 \(val_i\) 减去 \(t_i\)。若是不可行，则 \(\min\limits_{i=1\land i\ne P}^{n}(val_i-t_i)<0\)，其实就是看存不存在 \(t_i>val_i\)。
然后用数据结构维护就行了，我这里用了两棵平衡树，一颗维护 \(i<P\) 的点，以 \(L_i\) 作为排序的标准，一颗维护 \(i>P\) 的点，以 \(R_i\) 为排序的标准。一个平衡树的节点 \(i\) 要维护它排序的标准， \(val_i\)；\(val_i-t_i\) 的值，\(sum_i\)；以及它所在子树的 \(\min\limits_{j\in subtree_i} sum_j\)，\(minn_i\)。设它们为 \(T_0,T_1\)。枚举 \(P\) 时，每次 \(P\leftarrow P+1\) 时，将 \(P+1\) 从 \(T_1\) 中删除，并将 \(P\) 加入 \(T_0\)。同时，将 \(T_1\) 整棵树的 \(sum\) 减 \(1\)，\(T_0\) 整棵树的 \(sum\) 加 \(1\)。还要将 \(P+1\) 在 \(T_1\) 时对 \(T_0\) 的贡献抹去，\(P\) 在 \(T_0\) 时对 \(T_1\) 的贡献加上，具体表现为将 \(T_0\) 中 \(val\) 大于等于 \(R_{P+1}\) 的节点的 \(sum\) 加 \(1\)，\(T_1\) 中 \(val\) 大于等于 \(L_{P}\) 的节点的 \(sum\) 减 \(1\)。
代码如下：
#include<bits/stdc++.h>
#define int long long
#define fr first
#define sc second
using namespace std;
const int inf=0x3f3f3f3f3f3f3f3f;
mt19937 rnd(time(0));
struct Treap{
int val,sum,minn,siz,rnk,son[2],tag;
};
struct FHQ{
#define ls t[k].son[0]
#define rs t[k].son[1]
int rt=0,cnt=0;
Treap t[200005];
inline void calc(int k,int val){
if(k>0)t[k].minn+=val,t[k].sum+=val,t[k].tag+=val;return;
}
inline void pushup(int k){
t[k].minn=min({t[k].sum,t[ls].minn,t[rs].minn}),t[k].siz=t[ls].siz+t[rs].siz+1;return;
}
inline void pushdown(int k){
if(t[k].tag!=0){
calc(ls,t[k].tag),calc(rs,t[k].tag);
}t[k].tag=0;return;
}
inline int create(int val,int sum){
t[++cnt]={val,sum,sum,1,rnd(),{0,0},0};return cnt;
}
inline void split(int val,int k,int &L,int &R){
if(!k)L=R=0;
else{
pushdown(k);
if(t[k].val<=val)L=k,split(val,rs,rs,R);
else R=k,split(val,ls,L,ls);
pushup(k);
}return;
}
inline int merge(int L,int R){
pushdown(L),pushdown(R);
if(!L||!R){
return L+R;
}
if(t[L].rnk<t[R].rnk){
t[L].son[1]=merge(t[L].son[1],R),pushup(L);
return L;
}else{
t[R].son[0]=merge(L,t[R].son[0]),pushup(R);
return R;
}
}
inline void insert(int val,int sum){
int L,R;split(val,rt,L,R);
rt=merge(merge(L,create(val,sum)),R);return;
}
inline void delet(int val){
int L,R,mid;
split(val,rt,L,R),split(val-1,L,L,mid);
rt=merge(L,R);return;
}
inline int query(int val){
int L,R,res;split(val,rt,L,R);
res=t[L].siz,rt=merge(L,R);return res;
}
inline void updata(int val,int upd){
int L,R;split(val-1,rt,L,R);
calc(R,upd),rt=merge(L,R);return;
}
#undef ls
#undef rs
}T[2];
int Rana;
int n,a[200005],L[200005],R[200005],ans;
inline int read(){
register int x(0),t(0);
static char ch=getchar();
while(!isdigit(ch)){t|=(ch=='-'),ch=getchar();}
while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48),ch=getchar();}
return t?-x:x;
}
signed main(){
Rana=read();while(Rana--){
n=read(),ans=0;
for(int i=1;i<=n;i++){
a[i]=read();
}
L[1]=a[1];
for(int i=2;i<=n;i++){
L[i]=min(L[i-1]-1,a[i]);
}
R[n]=a[n];
for(int i=n-1;i>=1;i--){
R[i]=min(R[i+1]-1,a[i]);
}
T[0].rt=T[1].rt=T[0].cnt=T[1].cnt=0;
T[0].t[0].minn=inf,T[1].t[0].minn=inf;
for(int i=1;i<=n;i++){
T[1].insert(R[i],R[i]-i-1);
}
for(int i=1;i<=n;i++){
T[1].calc(T[1].rt,1),T[1].delet(R[i]);
T[0].updata(R[i],1),T[0].calc(T[0].rt,-1);
if(i>1){
T[0].insert(L[i-1],L[i-1]-T[1].query(L[i-1])-2);
T[1].updata(L[i-1],-1);
}
ans+=(T[0].t[T[0].rt].minn>=0&&T[1].t[T[1].rt].minn>=0);
}
cout<<ans<<'\n';
}return 0;
}