浙农大第十九届程序设计竞赛 G-最优的连续子段

最优的连续子段

分析

因为是区间问题，我们先选择一个定点，即枚举右端点r，那么我们要求的就是左端点在[1,r]，出现次数为1的数字最大个数。具体看图

假设当前已确定右端点r，且此时 ，可以确定，当左端点 时，这些区间中出现次数为1的数字的个数都会加1，而小于等于j的，就会全部减1
那为什么减一的区间是 ,明显，当右端点是j的时候，区间 已经被减过一次，自然不能再减

代码

#include<bits/stdc++.h>

#define ls now<<1
#define rs now<<1|1

using namespace std;

const int N=1e5+10;

int n;
int a[N],nex[N],s[N<<2],tag[N<<2],las[N];

inline void pd(int now)
{
    if(!tag[now]) return ;
    tag[ls]+=tag[now];s[ls]+=tag[now];
    tag[rs]+=tag[now];s[rs]+=tag[now];
    tag[now]=0;
    return ;
}

inline void add(int now,int l,int r,int x,int y,int z)
{
    if(r<x||l>y) return ;if(x<0||y>n) return ;
    if(l>=x&&r<=y)
    {
        s[now]+=z,tag[now]+=z;
        return ;
    }pd(now);

    int mid=(l+r)>>1;
    if(x<=mid) add(ls,l,mid,x,y,z);
    if(mid<y) add(rs,mid+1,r,x,y,z);

    s[now]=max(s[ls],s[rs]);
}

inline int find(int now,int l,int r,int x,int y)
{
    if(l>=x&&r<=y) return s[now];
    pd(now);

    int mid=(l+r)>>1,ret=0;
    if(x<=mid) ret=find(ls,l,mid,x,y);
    if(mid<y) ret=max(ret,find(rs,mid+1,r,x,y));

    return ret;
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++) scanf("%d",&a[i]);

    int ans=0;
    for (int i=1;i<=n;i++)
    {
        las[i]=nex[a[i]];nex[a[i]]=i;
        add(1,1,n,las[i]+1,i,1);
        add(1,1,n,las[las[i]]+1,las[i],-1);
        ans=max(ans,find(1,1,n,1,i));
    }

    printf("%d\n",ans);

    return 0;
}