[传智杯 #5 初赛] I-不散的宴会

本文主要是介绍[传智杯 #5 初赛] I-不散的宴会，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

洛谷P8877 [传智杯 #5 初赛] I-不散的宴会

题目大意

学生社会可以被看作一个排列成等腰直角三角形的节点阵列。该节点阵列共有 $n$ 行，第 $i$ 行共有 $i$ 个节点，我们将第 $i$ 行第 $j$ 列的节点标号为 $(i, j)$ 。

这些点具有权值。节点 $(i, j)$ 的权值为 $r_i\oplus c_j$ ，其中 $r$ 和 $c$ 是给定的 $01$ 序列。

这些点有边相连。对于 $1\leq i<n$ ， $1\leq j<i$ ，会有一条边连接 $(i, j)$ 和 $(i + 1, j)$ 。此外，对于 $2\leq i\leq n$ ，还会有边连接 $(i, i)$ 和 $i-1,a_i)$ ，其中 $a$ 是给定的序列。

现在你需要从这些节点中，选出一些节点，使得这些节点间两两不存在边相连，最大化选出来的节点的权值之和。

$1\leq n\leq 10^6,1\leq a_i<i$

题解

首先，我们可以发现，这个图有 $\dfrac{n(n+1)}{2}$ 个点， $\dfrac{n(n-1)}{2}+(n-1)$ 条边，边数比点数少 $1$ ，这个图还是连通的，所以这个图是一棵树。

我们将所有第 $1$ 层的点、第 $n$ 层的点和度数为 $3$ 的点设为关键点。那么关键点的个数是 $O (n)$ 的，因为关键点只可能出现在第 $1$ 层、第 $n$ 层和连接 $(i, i)$ 和 $i-1,a_i)$ 的边上（可以自己画图感受一下）。

除了关键点，其他点的度数都为 $2$ ，那么这些点肯定都在一条链上。于是，我们可以把一条链看成两个关键点的边，这些关键点和边就构成一棵虚树，因为它的点的个数是 $O (n)$ 的，所以边的个数也是 $O (n)$ 的。

建虚树时，我们从下往上枚举每一行，用 $v_i$ 表示第 $i$ 列最后一个关键点在虚树上的编号。假设当前遍历到第 $i$ 行，则将 $i-1,a_i)$ 和 $v_{a_i}$ 在虚树上连一条边，将 $(i, i)$ 和 $i-1,a_i)$ 在虚树上连一条边，并用 $i-1,a_i)$ 来更新 $v_{a_i}$ ，还要求出新加在虚树上的点的权值。

建好的虚树后，即求树上最大点权独立集，可以用 $D P$ 来求。

设 $f_u,g_u$ 分别表示选择或不选择虚树上的节点 $u$ 的情况下，子树 $u$ 能取得的最大点权独立集的值。

假设有两个关键点 $u$ 和 $v$ ，它们之间通过链 $s=\{v_1,v_2,\dots,v_k\}$ 连接，则转移式为

$f_u+=\max\{val(v_2,v_3,\dots,v_{k-1})+f_v,val(v_2,v_3,\dots,v_k)+g_v\}$

$g_u+=\max\{val(v_1,v_2,\dots,v_{k-1})+f_v,val(v_1,v_2,\dots,v_k)+g_v\}$

其中 $val(v_1,v_2,\dots,v_k)$ 表示 $v_1$ 到 $v_k$ 在不能选择相邻元素的情况下可以取得的最大点权独立集。

这个图还有一个性质：虚树中每条边在原图中对应的链上的点在同一列上。

那么，假设这条链在第 $k$ 列，其所在的区间为 $[a, b]$ ，则：

若 $c_k=0$ ，则每个位置的权值为 $r_a,r_{a+1}\dots,r_b$
若 $c_k=1$ ，则每个位置的权值为 $\neg r_a,\neg r_{a+1},\dots,\neg r_b$

那么，问题就转化为，查询对 $r$ 序列或 $\neg r$ 序列求区间最大点独立集的大小。

对于一个 $01$ 序列，我们可以用贪心来求最大点独立集。比如，对于长度为 $2 k$ 的全 $1$ 段，最大点独立集显然为 $k$ ；对于长度为 $2 k + 1$ 的全 $1$ 段，最大点独立集显然为 $k + 1$ 。对于含有 $0$ 的序列，可以以 $0$ 作为分隔划分出各种全 $1$ 段，在分别求和相加即可。

下面，我们考虑如何求区间最大点独立集。

我们可以预处理出两个数组：

$h_i$ 表示仅考虑前 $i$ 个元素得出的最大点独立集的大小
$p_i$ 表示第 $i$ 个元素所在的全 $1$ 段的最后一个 $1$ 的位置。如果位置 $i$ 是 $0$ ，则 $p_i=i-1$

假设我们当前要计算区间 $[l, r]$ 的最大点权独立集的大小，那么结果为

$h_r-h_{\min(r,p_l)}+\lfloor\dfrac{\min(r,p_l)-l+2}{2}\rfloor$

即先求出 $min(r,p_l)+1,r]$ 这一段的最大点权独立集的大小，再统计 $l,\min(r,p_l)]$ 这一段长度为 $r-\min(r,p_l)+1$ 的全 $1$ 段的最大点权独立集大小（长度为 $k$ 的全 $1$ 段的最大点权独立集的大小为 $\lfloor\dfrac{k+1}{2}\rfloor$ ）。

时间复杂度为 $O (n)$ 。

code

#include<bits/stdc++.h>
using namespace std;
const int N=1000000;
int n,cnt=0,R[N+5],C[N+5],a[N+5],v[N+5],vd[N+5],s[2*N+5],h[2][N+5],p[2][N+5];
int tot=0,d[2*N+5],l[2*N+5],r[2*N+5];
long long f[2*N+5],g[2*N+5],w[2*N+5][4];
long long gt(int i,int l,int r){if(r-l+1<=-2) return -1e18;if(l>r) return 0ll;int e=C[i];return 1ll*h[e][r]-h[e][min(r,p[e][l])]+(min(r,p[e][l])-l+2)/2;
}
void gtin(long long *v1,int i,int l,int r){v1[0]=gt(i,l,r);v1[1]=gt(i,l,r-1);v1[2]=gt(i,l+1,r);v1[3]=gt(i,l+1,r-1);
}
void add(int xx,int yy,int i,int ll,int rr){l[++tot]=r[xx];d[tot]=yy;r[xx]=tot;gtin(w[tot],i,ll,rr);
}
void init(int e){for(int i=1,lst=0;i<=n;i++){if((R[i]^e)==0){h[e][i]=h[e][i-1];lst=i;}else h[e][i]=h[e][lst]+(i-lst+1)/2;}p[e][n+1]=n;for(int i=n;i>=1;i--){if((R[i]^e)==0) p[e][i]=i-1;else p[e][i]=p[e][i+1];}
}
void dfs(int u){f[u]=s[u];for(int i=r[u];i;i=l[i]){int v=d[i];dfs(v);f[u]+=max(f[v]+w[i][3],g[v]+w[i][2]);g[u]+=max(f[v]+w[i][1],g[v]+w[i][0]);}
}
int main()
{scanf("%d",&n);for(int i=1;i<=n;i++) scanf("%d",&R[i]);for(int i=1;i<=n;i++) scanf("%d",&C[i]);for(int i=2;i<=n;i++) scanf("%d",&a[i]);init(0);init(1);for(int i=1;i<=n;i++){v[i]=++cnt;vd[i]=n;s[cnt]=R[n]^C[i];}for(int i=n;i>=2;i--){add(++cnt,v[a[i]],a[i],i,vd[a[i]]-1);v[a[i]]=cnt;vd[a[i]]=i-1;s[cnt]=R[i-1]^C[a[i]];add(cnt,v[i],i,i,vd[i]-1);}dfs(cnt);printf("%lld",max(f[cnt],g[cnt]));return 0;
}