题目链接：HDU - 6406
预处理出从起点开始，到每个点的个数，以及每个点作为起点到终点的个数。
然后对于当前的点，分段考虑即可。
预处理的时候可以用ST表优化。
AC代码：
#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,mx[N][20],m,h[N],pre[N],a[N],suf[N];
inline int ask(int l,int r){int k=log2(r-l+1);return max(mx[l][k],mx[r-(1<<k)+1][k]);
}
inline int find(int l,int r,int v){int pos=l;while(l<r){int mid=l+r>>1;if(ask(pos,mid)>v) r=mid;else l=mid+1;}return l;
}
inline void solve(){cin>>n>>m;for(int i=1;i<=n;i++) scanf("%d",&h[i]),mx[i][0]=h[i];for(int j=1;j<=17;j++) for(int i=1;i<=n-(1<<j)+1;i++)mx[i][j]=max(mx[i][j-1],mx[i+(1<<(j-1))][j-1]);for(int i=1;i<=n;i++) pre[i]=pre[i-1]+(h[i]>a[i-1]),a[i]=max(a[i-1],h[i]);for(int i=n;i>=1;i--){if(i==n||ask(i+1,n)<=h[i]) suf[i]=1;else suf[i]=suf[find(i+1,n,h[i])]+1;}for(int i=1,x,y,z;i<=m;i++){scanf("%d %d",&x,&y); y=max(a[x-1],y);if(x==n||ask(x+1,n)<=y) z=0;else z=suf[find(x+1,n,y)];printf("%d\n",pre[x-1]+(y>a[x-1])+z);}
}
signed main(){int T; cin>>T; while(T--) solve();return 0;
}