专栏文章

题解：P11518 [CCO 2024] Heavy Light Decomposition

MMeta_Morph
P11518题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mio81zqx
此快照首次捕获于
2025/12/02 14:53
3 个月前
此快照最后确认于
2025/12/02 14:53
3 个月前
查看原文

[CCO 2024] Heavy Light Decomposition 题解

博客园链接：[CCO 2024] Heavy Light Decomposition 题解 - Add_Catalyst - 博客园 (cnblogs.com)。

知识点

DP，线段树优化。

分析

考虑 ai,ai+1a_i,a_{i+1} 间限制：
  1. ai≠ai+1a_i \neq a_{i+1}。
  2. ai,ai+1a_i,a_{i+1} 之间只有一个为重一个为轻，则可以得到同时包含它们的区间限制：
    考虑使 aia_i 为重的两侧最近节点，设为 l,rl,r。特别地，若左侧不存在，则 l=0l=0；若右侧不存在，则 r=n+1r=n+1。同理，ai+1a_{i+1} 的设为 L,RL,R。
    由于将序偶 <l,r><l,r> 和 <L,R><L,R> 对换后几乎等价，不妨假设有 R<rR<r 以减少情况数。那么只有两种情况：
    1. l≤Ll\le L：
      此时只有 ai+1a_{i+1} 可以为重，区间范围是 <(l,i],[i+1,r)>∖<(L,i],[i+1,R)><(l,i],[i+1,r)>\setminus<(L,i],[i+1,R)>，放到一个二维平面上就是一个 (l,i]×[i+1,r)(l,i]\times[i+1,r) 的矩形减去 (L,i]×[i+1,R)(L,i]\times [i+1,R) 的矩形。
    2. l>Ll>L：
      那么 ai,ai+1a_i,a_{i+1} 都可能为重。
      • aia_i 为重，区间范围为 <(L,l],[i+1,R)><(L,l],[i+1,R)>。
      • ai+1a_{i+1} 为重，区间范围为 <(l,i],[R,r)><(l,i],[R,r)>。
除相邻点限制之外，还有交替的限制，那么我们将上面的矩形加减放到两个数组 sum0/1sum_{0/1} 中实现，sum0/1sum_{0/1} 分别表示 ii 为奇数的点要为轻、为重。发现，如果满足 sum0/1,j,i=i−j(j≤i)sum_{0/1,j,i}=i-j(j\le i)，则 [i,j][i,j] 是一个合法的”好数组“，可以得到一个二维前缀和的 O(n2)O(n^2) 算法。
设 fif_i 为前 ii 个数的合法方案数，那么有：
f0=1fi=∑j=1ifj−1[sum0/1,j,i=i−j]f_0 = 1 \\ f_i = \sum_{j=1}^i f_{j-1} [sum_{0/1,j,i}=i-j] \\
又发现，除 j=ij=i 外，其余 sum0,j,i,sum1,j,isum_{0,j,i},sum_{1,j,i} 中只有一者可以满足 i−ji-j，且 sum0/1,j,i≤i−jsum_{0/1,j,i}\le i-j 永远成立，移项，得到 sum0/1,j,i+j≤isum_{0/1,j,i}+j\le i。
那么考虑开两棵线段树做扫描线，维护 sum0/1,j,i+jsum_{0/1,j,i}+j 的最大值以及其对应位置的 DP 值 fj−1f_{j-1}，最后查询 fif_i 时再减掉 fi−1f_{i-1} 即可。

代码

已删去模运算和快读快写。
CPP
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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...