本文共 1391 字，大约阅读时间需要 4 分钟。
考虑算出\(nxt_i\)表示以\(i\)为左端点，不出现重复的数最远可以到的位置
然后枚举左端点\(l\)，枚举右端点\(r\)，如果当前区间内的最大值\(mx>r-l+1\)，我们就将右端点移到\(mx+l-1\)的位置上。
由于答案是\(O(n)\)的，所以总复杂度就是\(O(n\log n)\)
代码：
#include #include #include #include #include #include using namespace std;#define rg registervoid read(int &x){ char ch;bool ok; for(ok=0,ch=getchar();!isdigit(ch);ch=getchar())if(ch=='-')ok=1; for(x=0;isdigit(ch);x=x*10+ch-'0',ch=getchar());if(ok)x=-x;}const int maxn=3e5+10;int n,a[maxn],ans,nxt[maxn],mx[maxn*4];bool vis[maxn];void change(int x,int l,int r,int a,int b){ if(l==r)return mx[x]=b,void();int mid=(l+r)>>1; if(a<=mid)change(x<<1,l,mid,a,b);else change(x<<1|1,mid+1,r,a,b); mx[x]=max(mx[x<<1],mx[x<<1|1]);}int get(int x,int l,int r,int a,int b){ if(a<=l&&b>=r)return mx[x];int mid=(l+r)>>1,ans=0; if(a<=mid)ans=max(get(x<<1,l,mid,a,b),ans); if(b>mid)ans=max(ans,get(x<<1|1,mid+1,r,a,b)); return ans;}int main(){ read(n);int l=1; for(rg int i=1;i<=n;i++)read(a[i]),nxt[i]=n,change(1,1,n,i,a[i]); for(rg int i=1;i<=n;i++) if(!vis[a[i]])vis[a[i]]=1; else { while(a[l]!=a[i])vis[a[l]]=0,nxt[l]=i-1,l++; nxt[l]=i-1,l++; } for(rg int i=1;i<=n;i++){ for(rg int j=i;j<=nxt[i];j++){ int now=get(1,1,n,i,j); if(now>j-i+1)j+=(now-(j-i+1))-1;else ans++; } } printf("%d\n",ans);}
转载于:https://www.cnblogs.com/lcxer/p/11505753.html