记录编号	608815	评测结果	AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
题目名称	4184.轻重数字	最终得分	100
用户昵称	梦那边的美好TE	是否通过	通过
代码语言	C++	运行时间	27.480 s
提交时间	2025-10-29 16:34:11	内存使用	81.42 MiB

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int N=5e5+10;
const int M=(N<<2);
const int mod=1000003;
int n,a[N],lst[3][N],t[3][N],f[N];
struct seg{int l,r,v;};
struct node{
	vector<seg>pat[N];
	int mx[M],tag[M],sum[M];
	#define ls (p<<1)
	#define rs (p<<1|1)
	void pushup(int p){
		if(mx[ls]==mx[rs]){
			mx[p]=mx[ls];
			sum[p]=(sum[ls]+sum[rs])%mod;
		}else if(mx[ls]>mx[rs]){
			mx[p]=mx[ls];
			sum[p]=sum[ls];
		}else if(mx[ls]<mx[rs]){
			mx[p]=mx[rs];
			sum[p]=sum[rs];
		}
	}
	void maketag(int p,int v){
		tag[p]+=v,mx[p]+=v;
	}
	void pushdown(int p){
		if(!tag[p])return;
		maketag(ls,tag[p]);
		maketag(rs,tag[p]);
		tag[p]=0;return;
	}
	void add(int p,int l,int r,int L,int R,int v){
		if(L<=l&&r<=R)return maketag(p,v),void();
		pushdown(p);int mid=(l+r)>>1;
		if(L<=mid)add(ls,l,mid,L,R,v);
		if(R>mid)add(rs,mid+1,r,L,R,v);
		pushup(p);return;
	}
	void upd(int p,int l,int r,int x,int v){
		if(l==r)return sum[p]=v,void();
		int mid=(l+r)>>1;pushdown(p);
		if(x<=mid)upd(ls,l,mid,x,v);
		if(x>mid)upd(rs,mid+1,r,x,v);
		pushup(p);return;
	}
	int calc(int c){
		if(mx[1]==c)return sum[1];
		else return 0;
	}
	void modify(int id,int x,int y,int v){
		pat[id].push_back(seg{x,y,v});
		if(x<=y)add(1,1,n,x,y,v);
	}
	void remove(int x){
		for(auto w:pat[x]){
			if(w.l<=w.r)add(1,1,n,w.l,w.r,-w.v);
		}
	}
}tr1,tr2;
int main(){
	freopen("digit.in","r",stdin);
	freopen("digit.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",a+i);
		lst[0][i]=t[0][a[i]];
		lst[1][i]=t[2][a[i]];
		lst[2][i]=t[1][a[i]];
		t[0][a[i]]=i;
		if(i&1)t[1][a[i]]=i;
		else t[2][a[i]]=i;
	}
	int c1=0,c2=0;
	f[0]=1;
	for(int i=1,p;i<=n;i++){
		if(i&1){
			tr1.modify(i,lst[0][i]+1,n,1);
			c1++;
		}else{
			int p=lst[0][i];
			if(p)tr1.remove(p);
			else c1++;
			tr1.modify(i,lst[2][i]+1,p,1);
			tr1.modify(i,i+1,n,1); 
		}
		f[i]+=tr1.calc(c1),f[i]%=mod;
		if(i&1){
			int p=lst[0][i];
			if(p)tr2.remove(p);
			else c2++;
			tr2.modify(i,lst[1][i]+1,p,1);
			tr2.modify(i,i+1,n,1);
		}else{
			tr2.modify(i,lst[0][i]+1,n,1);
			c2++;
		}
		f[i]+=tr2.calc(c2),f[i]%=mod;
		f[i]+=f[i-1],f[i]%=mod;
		if(i){
			tr1.upd(1,1,n,i,f[i-1]);
			tr2.upd(1,1,n,i,f[i-1]);
		}
	}
	printf("%lld\n",f[n]);
	return 0;
}