记录编号	608636	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	轻重数字	最终得分	100
用户昵称	梦那边的美好TT	是否通过	通过
代码语言	C++	运行时间	33.587 s
提交时间	2025-10-28 16:56:03	内存使用	88.03 MiB

#include <bits/stdc++.h>
using namespace std;
const int MOD=1000003;
const int MAXN=500010;
int n,ecnt;
int a[MAXN],f[MAXN],pre[MAXN],nxt[MAXN],lst[MAXN];
struct Evt{
    bool t;
    int y,l,r,v;
    bool operator<(const Evt& o)const{return y<o.y;}
}evts[MAXN<<2];
struct Dat{
    int mx,cnt;
    Dat(int m=0,int c=0):mx(m),cnt(c){}
    friend Dat operator+(const Dat& a,const Dat& b){
        Dat res;
        res.mx=max(a.mx,b.mx);
        res.cnt=0;
        if(res.mx==a.mx)res.cnt=(res.cnt+a.cnt)%MOD;
        if(res.mx==b.mx)res.cnt=(res.cnt+b.cnt)%MOD;
        return res;
    }
};
struct Seg{
    struct Node{
        int tag;
        Dat dat;
        Node(int t=0,const Dat& d=Dat()):tag(t),dat(d){}
        void add(int v){dat.mx+=v;tag+=v;}
    }tr[MAXN<<2];
    void up(int p){tr[p].dat=tr[p<<1].dat+tr[p<<1|1].dat;}
    void down(int p){
        if(tr[p].tag){
            tr[p<<1].add(tr[p].tag);
            tr[p<<1|1].add(tr[p].tag);
            tr[p].tag=0;
        }
    }
    void build(int p=1,int l=1,int r=n){
        tr[p]=Node();
        if(l==r)return;
        int m=(l+r)>>1;
        build(p<<1,l,m);
        build(p<<1|1,m+1,r);
    }
    void upd(int L,int R,int v,int p=1,int l=1,int r=n){
        if(L<=l&&r<=R){tr[p].add(v);return;}
        down(p);
        int m=(l+r)>>1;
        if(L<=m)upd(L,R,v,p<<1,l,m);
        if(m<R)upd(L,R,v,p<<1|1,m+1,r);
        up(p);
    }
    void set(int x,int v,int p=1,int l=1,int r=n){
        if(l==r){tr[p].dat=Dat(l,v);return;}
        down(p);
        int m=(l+r)>>1;
        if(x<=m)set(x,v,p<<1,l,m);
        else set(x,v,p<<1|1,m+1,r);
        up(p);
    }
}seg[2];
void add(int& x,int y){x=(x+y)%MOD;if(x<0)x+=MOD;}
void addevt(bool t,int l,int r,int y1,int y2,int v){
    if(l<=r&&y1<=y2){
        evts[++ecnt]={t,y1,l,r,v};
        evts[++ecnt]={t,y2+1,l,r,-v};
    }
}
void proci(int i){
    if(a[i]==a[i+1])return;
    bool t=i&1;
    int l=pre[i],r=nxt[i];
    int L=pre[i+1],R=nxt[i+1];
    if(l<1&&L<1&&r>n&&R>n)return;
    if(R>r){swap(l,L);swap(r,R);t=!t;}
    if(l<=L){addevt(t,l+1,i,i+1,r-1,1);addevt(t,L+1,i,i+1,R-1,-1);}
    else{addevt(!t,L+1,l,i+1,R-1,1);addevt(t,l+1,i,R,r-1,1);}
}
int main(){
    freopen("digit.in","r",stdin);
    freopen("digit.out","w",stdout);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin>>n;
    for(int i=1;i<=n;++i)cin>>a[i];
    memset(lst,0,sizeof(lst));
    for(int i=1;i<=n;++i){
        pre[i]=lst[a[i]];
        if(lst[a[i]])nxt[lst[a[i]]]=i;
        lst[a[i]]=i;
    }
    for(int i=1;i<=n;++i) if(lst[i]&&!nxt[lst[i]])nxt[lst[i]]=n+1;
    seg[0].build();seg[1].build();
    seg[0].set(1,1);seg[1].set(1,1);
    f[0]=1;ecnt=0;
    for(int i=1;i<n;++i)proci(i);
    sort(evts+1,evts+ecnt+1);
    int eptr=1;
    for(int i=1;i<=n;++i){
        while(eptr<=ecnt&&evts[eptr].y<=i){
            seg[evts[eptr].t].upd(evts[eptr].l,evts[eptr].r,evts[eptr].v);
            eptr++;
        }
        f[i]=0;
        Dat d0=seg[0].tr[1].dat;
        if(d0.mx==i)add(f[i],d0.cnt);
        Dat d1=seg[1].tr[1].dat;
        if(d1.mx==i)add(f[i],d1.cnt);
        add(f[i],MOD-f[i-1]);
        if(i<n){seg[0].set(i+1,f[i]);seg[1].set(i+1,f[i]);}
    }
    cout<<(f[n]%MOD+MOD)%MOD<<endl;
    return 0;
}