[传智杯 #5 初赛] I

初赛] I"/>

[传智杯 #5 初赛] I

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

题目大意

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

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

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

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

1 ≤ n ≤ 1 0 6 , 1 ≤ a i < i 1\leq n\leq 10^6,1\leq a_i<i 1≤n≤106,1≤ai​<i

题解

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

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

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

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

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

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

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

f u + = max ⁡ { v a l ( v 2 , v 3 , … , v k − 1 ) + f v , v a l ( v 2 , v 3 , … , v k ) + g v } f_u+=\max\{val(v_2,v_3,\dots,v_{k-1})+f_v,val(v_2,v_3,\dots,v_k)+g_v\} fu​+=max{val(v2​,v3​,…,vk−1​)+fv​,val(v2​,v3​,…,vk​)+gv​}

g u + = max ⁡ { v a l ( v 1 , v 2 , … , v k − 1 ) + f v , v a l ( v 1 , v 2 , … , 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\} gu​+=max{val(v1​,v2​,…,vk−1​)+fv​,val(v1​,v2​,…,vk​)+gv​}

其中 v a l ( v 1 , v 2 , … , v k ) val(v_1,v_2,\dots,v_k) val(v1​,v2​,…,vk​)表示 v 1 v_1 v1​到 v k v_k vk​在不能选择相邻元素的情况下可以取得的最大点权独立集。

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

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

• 若 c k = 0 c_k=0 ck​=0，则每个位置的权值为 r a , r a + 1 … , r b r_a,r_{a+1}\dots,r_b ra​,ra+1​…,rb​
• 若 c k = 1 c_k=1 ck​=1，则每个位置的权值为 ¬ r a , ¬ r a + 1 , … , ¬ r b \neg r_a,\neg r_{a+1},\dots,\neg r_b ¬ra​,¬ra+1​,…,¬rb​

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

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

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

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

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

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

h r − h min ⁡ ( r , p l ) + ⌊ min ⁡ ( r , p l ) − l + 2 2 ⌋ h_r-h_{\min(r,p_l)}+\lfloor\dfrac{\min(r,p_l)-l+2}{2}\rfloor hr​−hmin(r,pl​)​+⌊2min(r,pl​)−l+2​⌋

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

时间复杂度为 O ( n ) O(n) 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;
}