[CCO 2024] Heavy Light Decomposition 題解

知識點

DP，線段樹優化。

分析

考慮 \(a_i,a_{i+1}\) 間限制：

1. \(a_i \neq a_{i+1}\)。

2. \(a_i,a_{i+1}\) 之間只有一個為重一個為輕，則可以得到同時包含它們的區間限制：

   考慮使 \(a_i\) 為重的兩側最近節點，設為 \(l,r\)。特別地，若左側不存在，則 \(l=0\)；若右側不存在，則 \(r=n+1\)。同理，\(a_{i+1}\) 的設為 \(L,R\)。

   由于將序偶 \(<l,r>\) 和 \(<L,R>\) 對換后幾乎等價，不妨假設有 \(R>r\) 以減少情況數。那么只有兩種情況：

   1. \(l\le L\)：

      此時只有 \(a_{i+1}\) 可以為重，區間范圍是 \(<(l,i],[i+1,r)>\setminus<(L,i],[i+1,R)>\)，放到一個二維平面上就是一個 \((l,i]\times[i+1,r)\) 的矩形減去 \((L,i]\times [i+1,R)\) 的矩形。

   2. \(l>L\)：

      那么 \(a_i,a_{i+1}\) 都可能為重。

      • \(a_i\) 為重，區間范圍為 \(<(L,l],[i+1,R)>\)。
      • \(a_{i+1}\) 為重，區間范圍為 \(<(l,i],[R,r)>\)。

除相鄰點限制之外，還有交替的限制，那么我們將上面的矩形加減放到兩個數組 \(sum_{0/1}\) 中實現，\(sum_{0/1}\) 分別表示 \(i\) 為奇數的點要為輕、為重。發現，如果滿足 \(sum_{0/1,j,i}=i-j(j\le i)\)，則 \([i,j]\) 是一個合法的”好數組“，可以得到一個二維前綴和的 \(O(n^2)\) 算法。

設 \(f_i\) 為前 \(i\) 個數的合法方案數，那么有：

又發現，除 \(j=i\) 外，其余 \(sum_{0,j,i},sum_{1,j,i}\) 中只有一者可以滿足 \(i-j\)，且 \(sum_{0/1,j,i}\le i-j\) 永遠成立，移項，得到 \(sum_{0/1,j,i}+j\le i\)。

那么考慮開兩棵線段樹做掃描線，維護 \(sum_{0/1,j,i}+j\) 的最大值以及其對應位置的 DP 值 \(f_{j-1}\)，最后查詢 \(f_i\) 時再減掉 \(f_{i-1}\) 即可。

代碼

已刪去模運算和快讀快寫。

int n,cha;
int a[N],f[N],pre[N],nxt[N],lst[N];
struct Change {
	bool t;
	int y,xa,xb,v;
	friend bool operator <(Change a,Change b) { return a.y<b.y; }
} Cha[N<<2];
struct Data {
	int mx,val;
	Data(int mx=0,int val=0):mx(mx),val(val) {}

	friend Data operator +(Data A,Data B) {
		Data C(max(A.mx,B.mx),0);
		if(C.mx==A.mx)toadd(C.val,A.val);
		if(C.mx==B.mx)toadd(C.val,B.val);
		return C;
	}
};
struct SEG {
	struct node {
		int tag;
		Data dat;
		node(int tag=0,Data dat=Data()):tag(tag),dat(dat) {}

		void down(int _tag) { dat.mx+=_tag,tag+=_tag; }
	} tr[N<<2];
#define ls (p<<1)
#define rs (p<<1|1)
#define mid ((l+r)>>1)
	void Up(int p) { tr[p].dat=tr[ls].dat+tr[rs].dat; }

	void Down(int p) { if(tr[p].tag)tr[ls].down(tr[p].tag),tr[rs].down(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;
		Build(ls,l,mid),Build(rs,mid+1,r),Up(p);
	}

	void Plus(int L,int R,int d,int p=1,int l=1,int r=n) {
		if(L<=l&&r<=R)return tr[p].down(d);
		Down(p);
		if(L<=mid)Plus(L,R,d,ls,l,mid);
		if(mid<R)Plus(L,R,d,rs,mid+1,r);
		Up(p);
	}

	void Change(int x,int d,int p=1,int l=1,int r=n) {
		if(l==r)return tr[p].dat=Data(l,d),void();
		return Down(p),x<=mid?Change(x,d,ls,l,mid):Change(x,d,rs,mid+1,r),Up(p);
	}
#undef ls
#undef rs
#undef mid
} seg[2];

void Plus(bool t,int xa,int xb,int ya,int yb,int d) {
	if(xa<=xb&&ya<=yb)Cha[++cha]=Change{t,ya,xa,xb,d},Cha[++cha]=Change{t,yb+1,xa,xb,-d};
}

void Plus(int i) {
	if(a[i]==a[i+1])return;
	bool t(i&1);
	int l(pre[i]),r(nxt[i]),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)Plus(t,l+1,i,i+1,r-1,1),Plus(t,L+1,i,i+1,R-1,-1);
	else Plus(!t,L+1,l,i+1,R-1,1),Plus(t,l+1,i,R,r-1,1);
}

signed main() {
#ifdef Plus_Cat
	freopen(Plus_Cat ".in","r",stdin),freopen(Plus_Cat ".out","w",stdout);
#endif
	/*DE("Input & Init");*/
	I(n);
	FOR(i,1,n)I(a[i]),pre[i]=lst[a[i]],nxt[lst[a[i]]]=i,lst[a[i]]=i;
	FOR(i,1,n)if(lst[i])nxt[lst[i]]=n+1;
	/*DE("Init");*/
	seg[0].Build(),seg[0].Change(1,f[0]=1),seg[1].Build(),seg[1].Change(1,f[0]=1);
	FOR(i,1,n-1)Plus(i);
	sort(Cha+1,Cha+cha+1);
	/*DE("Solve");*/
	int it(1);
	FOR(i,1,n) {
		while(it<=cha&&Cha[it].y<=i)seg[Cha[it].t].Plus(Cha[it].xa,Cha[it].xb,Cha[it].v),++it;
		if(seg[0].tr[1].dat.mx==i)toadd(f[i],seg[0].tr[1].dat.val);
		if(seg[1].tr[1].dat.mx==i)toadd(f[i],seg[1].tr[1].dat.val);
		toadd(f[i],Mod-f[i-1]);
		if(i<n)seg[0].Change(i+1,f[i]),seg[1].Change(i+1,f[i]);
	}
	/*DE("Output");*/
	O(f[n],'\n');
	return 0;
}