提出 #63935285

---

ソースコード 拡げる

#include<bits/stdc++.h>
#define LL long long
#define ull unsigned long long
#define mkpr make_pair
#define lc(p) ((p)*2)
#define rc(p) ((p)*2+1)
#define fir first
#define sec second
using namespace std;
inline LL read() {
    LL x=0;
    bool t=0;
    char ch=getchar();
    while(ch<'0'||ch>'9')t|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+(ch^48),ch=getchar();
    return t?-x:x;
}
const int N=300005;
int n,a[N];
int ans,f[N],g[N],mp[N];

int tr[N<<2],tag[N<<2];
void pushup(int p) {
    tr[p]=max(tr[lc(p)],tr[rc(p)]);
}
void pushdown(int p) {
    if(tag[p]) {
        tr[lc(p)]+=tag[p];
        tr[rc(p)]+=tag[p];
        tag[lc(p)]+=tag[p];
        tag[rc(p)]+=tag[p];
        tag[p]=0;
    }
}
void modify(int p,int l,int r,int ql,int qr,int v) {
    if(ql<=l&&r<=qr) {
        tr[p]+=v;
        tag[p]+=v;
        return;
    }
    pushdown(p);
    int mid=(l+r)>>1;
    if(ql<=mid)modify(lc(p),l,mid,ql,qr,v);
    if(qr>mid)modify(rc(p),mid+1,r,ql,qr,v);
    pushup(p);
}
int query(int p,int l,int r,int ql,int qr) {
    if(ql<=l&&r<=qr) {
        return tr[p];
    }
    pushdown(p);
    int mid=(l+r)>>1;
    if(qr<=mid)return query(lc(p),l,mid,ql,qr);
    if(ql>mid)return query(rc(p),mid+1,r,ql,qr);
    return max(query(lc(p),l,mid,ql,qr),query(rc(p),mid+1,r,ql,qr));
}
int main() {
  //  freopen("in.txt","r",stdin);
//   freopen("out.txt","w",stdout);
    n=read();
    for(int i=1; i<=n; i++) {
        a[i]=read();
    }
    for(int i=n; i>=1; i--) {
        g[i]=g[i+1]+(mp[a[i]]==0);
        mp[a[i]]=i;
    }
    memset(mp,0,sizeof mp);
    for(int i=1; i<n; i++) {
        if(i>1)modify(1,1,n,max(1,mp[a[i]]),i-1,1);
        if(i>1)ans=max(ans,query(1,1,n,1,i-1)+g[i+1]);
        f[i]=f[i-1]+(mp[a[i]]==0);
        modify(1,1,n,i,i,f[i]);
        mp[a[i]]=i;
    }
    cout<<ans;
    return 0;
}
/*
add i

j<lst[i] no effect

j>=lst[i] +1


*/

提出情報

ジャッジ結果