C++14(g++5.4) 解法, 执行用时: 94ms, 内存消耗: 2912K, 提交时间: 2019-09-28 19:25:30

#include <cstdio>
using namespace std;

const int MAXN=1e5+5;
int seg[MAXN<<2],tag[MAXN<<2];
#define ls rt<<1
#define rs rt<<1|1

int tpr[MAXN],pre[MAXN];

void pushup(int rt){
    seg[rt]=seg[ls]>seg[rs]? seg[ls] : seg[rs];
}

void pushdown(int rt){
    if(tag[rt]){
        seg[ls]+=tag[rt];
        seg[rs]+=tag[rt];
        tag[ls]+=tag[rt];
        tag[rs]+=tag[rt];
        tag[rt]=0;
    }
}

void update(int L,int R,int v,int l,int r,int rt){
    if(L<=l && R>=r){
        seg[rt]+=v;
        tag[rt]+=v;
        return ;
    }
    int m=l+r>>1;
    pushdown(rt);
    if(L<=m) update(L,R,v,l,m,ls);
    if(R>m) update(L,R,v,m+1,r,rs);
    pushup(rt);
}

void chmax(int &a,int b){if(a<b) a=b;}

int main(){
    int n,x,ans=0;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&x);
        pre[i]=tpr[x];
        update(pre[i]+1,i,1,1,n,1);
        if(tpr[x]) update(pre[tpr[x]]+1,pre[i],-1,1,n,1);
        tpr[x]=i;
        chmax(ans,seg[1]);
    }
    printf("%d\n",ans);
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 93ms, 内存消耗: 3192K, 提交时间: 2019-06-08 10:50:04

#include<iostream>
#include<cstdio>
using namespace std;int seg[400005],tag[400005],lst[100005],rem[100005];
inline void dt(int root) {
    if (!tag[root]) return;
    seg[root<<1]+=tag[root],seg[root<<1|1]+=tag[root];
    tag[root<<1]+=tag[root],tag[root<<1|1]+=tag[root];
    return tag[root]=0,void();
}
void mdf(int root,int l,int r,int ql,int qr,int delta) {int mid=l+r>>1;
    if (ql<=l&&r<=qr) return seg[root]+=delta,tag[root]+=delta,void();dt(root);
    if (ql<=mid) mdf(root<<1,l,mid,ql,qr,delta);
    if (qr>mid) mdf(root<<1|1,mid+1,r,ql,qr,delta);
    return seg[root]=max(seg[root<<1],seg[root<<1|1]),void();
}
int main() {int n,x,ans=0;
    scanf("%d",&n);for (register int i=1;i<=n;++i) {
        scanf("%d",&x),lst[i]=rem[x],mdf(1,1,n,lst[i]+1,i,1);
        if (lst[i]) mdf(1,1,n,lst[lst[i]]+1,lst[i],-1);
        rem[x]=i,ans=max(ans,seg[1]);
    }printf("%d",ans);return 0;
}