驻波驻波，楼上 dashen 的做法确实很强，但是有没有抛弃大脑直接暴力分讨莽过去的做法？

有的有的！

思路分析

先考虑一个经典的 dp，设 $f_i$ 表示将 $1\sim i$ 划分为若干好数组的方案，则有转移 $f_i=\sum f_{j-1}$，其中满足 $[j,i]$ 是一个好区间。

这样枚举 $i$，枚举 $j$，$O(n)$ 检测，就有 $O(n^3)$ 的 dp 了。注意到 $n\le 5\times 10^5$，考虑优化。

不难发现好的子数组在原数组中，要么是奇数位置为轻元素，偶数位置为重元素；要么是偶数位置为轻元素，奇数位置为重元素，所以我们分两种情况转移：分别是以 $i$ 结尾，奇数位置为轻元素和 $i$ 结尾，偶数位置为轻元素。两者本质没有区别，我们依靠前者讨论。

我们考虑区间左端点 $j$ 可以取到哪些位置，考虑对于任意 $x\in [1,i]$，元素 $x$ 对左端点 $j$ 的约束。

• 若 $x$ 为奇数位置，作为轻元素约束 $j$。

则 $j$ 必须满足 $[lst_x+1,n]$，即对于任意 $i\in [1,n]$，只要 $j\in [lst_x+1,n]$，区间 $[j,i]$ 就可以满足 $x$ 的限制。

证明不难，当 $j\in [lst_x+1,x]$ 时，区间至多包含一个 $x$。当 $j>x$，区间一个 $x$ 都没有，自然无法约束。

容易发现，对 $j$ 的限制个数是奇数位置所有位置。

• 若 $x$ 为偶数位置，作为重元素约束 $j$

这种情况较为复杂。

首先可以发现对 $j$ 限制个数是元素种类数，对于同一种元素，我们用这种元素在 $[1,i]$ 中最后一次出现的位置来约束 $j$。

记 $p$ 为上一个在奇数位置出现的 $x$，$q$ 为 $x$ 上一次出现的位置。当 $j\le q$ 时，$[i,j]$ 一定包含了 $q,x$，满足重元素的限制，当 $j\le p$ 时，$p$ 作为重元素出现在奇数位置，$[i,j]$ 不合法，所以 $x$ 的限制是 $j\in [q+1,p]\cup[x+1,n]$。

注意：此时是按照 $x$ 是 $[1,i]$ 最后一次出现的数，随着 $i$ 的右移，如果在偶数位置出现一个和 $x$ 一样的元素 $y$。就要先撤销 $x$ 的限制，然后加入 $y$ 的限制。

考虑如何维护满足限制的端点：维护每个位置满足限制的个数，不难维护出限制的总个数，对于一个位置，如果它足一个限制，就让他的标记数组加一。如果一个位置满足的限制个数为总个数，就说明 $[j,i]$ 是一个合法的端点。

注意一种特殊情况是 $[i,i]$ 是合法区间，我们只统计 $j\in [1,i-1]$ 的合法左端点。

直接用数组模拟是 $O(n^2)$，容易用线段树优化到 $O(n\log n)$，具体的记录每个区间任意位置满足限制个数最大值，满足限制个数达到这个最大值的 $f_{i-1}$ 之和，pushup 分讨一下即可。

然后这个问题就解决了。

代码

#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(){
	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;
} 

如有错误，请指出。