调了一天了

cf上第四个点挂了，但是造了好几组数据也没找出来哪里挂了，求分治带师调调

做法是用nxt数组维护每一个数下一次出现的位置，查询的时候用线段树维护nxt数组最小值判断是否合法

#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define re register

using namespace std;
const int N=3e5+10,INF=1e9+1;
int n,a[N];

int t[N<<2][2];
int pre[N],nxt[N];
inline void up(int x,int op)
{
	if(!op) t[x][op]=min(t[x<<1][op],t[x<<1|1][op]);
	else 
	{
		if(a[t[x<<1][op]]>a[t[x<<1|1][op]]) t[x][op]=t[x<<1][op];
		else t[x][op]=t[x<<1|1][op];
	}
}
void build(int x,int l,int r,int op)
{
	if(l==r)
	{
		if(!op) t[x][op]=nxt[l];
		else t[x][op]=l;
		return ;
	}
	int mid=l+r>>1;
	build(x<<1,l,mid,op),build(x<<1|1,mid+1,r,op);
	up(x,op);
}
int ask(int x,int l,int r,int ql,int qr,int op)
{
	if(l>=ql&&r<=qr) return t[x][op];
	int mid=l+r>>1;
	if(!op)
	{
	    int ret=INF;
		if(ql<=mid) ret=min(ret,ask(x<<1,l,mid,ql,qr,op));
		if(mid<qr) ret=min(ret,ask(x<<1|1,mid+1,r,ql,qr,op));
		return ret;
	}
	else
	{
		int ret=0;
		if(ql<=mid) 
		{
			int p=ask(x<<1,l,mid,ql,qr,op);
			ret= a[p]>a[ret] ? p : ret ;
		}
		if(mid<qr) 
		{
			int q=ask(x<<1|1,mid+1,r,ql,qr,op);
			ret= a[q]>a[ret] ? q : ret ;
		}
	    return ret;	
	}
}
int ans;

void solve(int l,int r)
{
	if(l>r) return ;
	if(l==r)
	{
		ans+=(a[l]==1);
		return ;
	}
    int mid=ask(1,1,n,l,r,1); 
    if(mid<=(l+r>>1))
    {
    	for(re int i=mid;i>=l;--i)
    	{
    		if(mid-i+1>a[mid]) break ;
    		if(i+a[mid]-1>r) continue ;
    		ans+= ask(1,1,n,i,i+a[mid]-1,0)>i+a[mid]-1 ;
    	//	cout<<mid<<" "<<ask(1,1,n,i,i+a[mid]-1)<<"\n";
		}
	}
	else
	{
		for(re int i=mid;i<=r;++i)
		{
			if(i-mid>a[mid]) break ;
			if(i-a[mid]+1<l) continue ;
			ans+= ask(1,1,n,i-a[mid]+1,i,0)>i ;
		}
	}
//	cout<<mid<<" "<<ans<<"\n";
	solve(l,mid-1),solve(mid+1,r);
}

inline int read(){char cr=getchar();int x_=0,fui=1;while(cr<48){if(cr=='-')fui=-1;cr=getchar();}while(cr>47)x_=(x_*10)+(cr^48),cr=getchar();return x_*fui;}
inline void mwrite(int aq){if(aq>9)mwrite(aq/10);putchar((aq%10)|48);}
inline void write(int af,char cr){mwrite(af<0?(putchar('-'),af=-af):af);putchar(cr);}

signed main()
{
	n=read();
	a[0]=-INF;
	for(re int i=1;i<=n;++i) a[i]=read(),nxt[i]=INF;
	for(re int i=1;i<=n;++i) 
	{
	//	if(!pre[a[i]]) pre[a[i]]=i;
		if(pre[a[i]]) nxt[pre[a[i]]]=i;
		pre[a[i]]=i;
	}
	build(1,1,n,0),build(1,1,n,1);
	solve(1,n);
	write(ans,' ');
	return 0;
}