已知wa pretest 4 代码加上和暴力的对拍如下

#include <bits/stdc++.h>
//#include <windows.h>
//#define int long long
#define ffor(i,a,b) for(int i=a-1;i++<b;)
#define dfor(i,a,b) for(int i=a+1;i-->b;)
#define KEY_DOWN(VK_NONAME) ((GetAsyncKeyState(VK_NONAME) & 0x8000) ? 1:0)
using namespace std;
#define N 800005
int n;
int a[N];
int b[N];
int s[N];
int tot=0;
void mainn()
{
    //scanf("%d",&n);
    n=10;
    for(int i=1; i<=n; i++)
    {
        //scanf("%d",&a[i]);
        a[i]=rand()%n;
        if(a[i]<0)
        {
        	a[i]=1;
		}
        a[i]-=(i);
    }
    int ans1=0;
    s[0]=n+1;
    a[n+1]=-914748264;
    for(int i=n; i>=1; i--)
    {
        for(int j=i; j<=n; j++)
        {
            if(a[j]+j>=j-i+1)
            {
                ans1++;
            }
            else
            {
                break;
            }
        }
    }
	//printf("\n%d\n",ans1);
    int ans=0;
    tot=0;
    for(int i=n; i>=1; i--)
    {
        while(tot>0 && a[s[tot]]>=a[i])
        {
            tot--;
        }
        tot++;
        s[tot]=i;/*
    	for(int j=1;j<=tot;j++)
    	{
    		printf("s[%d]=%d %d\n",j,s[j],a[s[j]]);
		}*/
        int l=1,r=tot;
        while(l<r)
        {
            int mid=(l+r)/2;
            //printf("(%d %d %d)\n",l,r,mid);
            if(a[s[mid]]==-i)
            {
                l=r=mid;
            }
            else if(a[s[mid]]>-i)
            {
                r=mid-1;
            }
            else
            {
                l=mid+1;
            }
        }
        while((a[s[r]]>-i || r>tot) && r>=0)
        {
            r--;
        }
        while(r<tot && a[s[r+1]]<=-i)
        {
            r++;
        }
        //printf("found %d %d\n",r,s[r]);
        ans+=(s[r]-i);
    }
    //printf("%d\n",ans);

    if(ans1!=ans)
    {
        printf("!!! %d\n",n);
        for(int i=1; i<=n; i++)
        {
            printf("%d ",a[i]);
        }
        while(1);
    }
}
int main()
{
    int T;
    //scanf("%d",&T);
    T=20000000;
    srand(time(0));
    while(T--)
    {
        mainn();
    }
    return 0;
}