CVBB ACM Team

到此差别页面的链接

--- 2020-2021:teams:legal_string:组队训练比赛记录:contest10 [2021/08/06 21:08]
jxm2001
+++ 2020-2021:teams:legal_string:组队训练比赛记录:contest10 [2021/08/11 16:00] (当前版本)
jxm2001
@@ 行 8: / 行 8: @@
 |  C  |  1  |  0  |  2  |
 |  D  |  2  |  1  |  0  |
-|  E  |  0  |  0  |  0  |
+|  E  |  2  |  0  |  0  |
-|  G  |  0  |  0  |  2  |
+|  G  |  0  |  1  |  2  |
 |  J  |  2  |  0  |  1  |
 |  K  |  2  |  0  |  0  |
@@ 行 280: / 行 280: @@
 		solve();
 	}
+	return 0;
+}
+</code>
+</hidden>
+===== E. Growing Tree =====
+==== 题意 ====
+给定一棵树，初始时只有一个颜色为 $c$ 的 $1$ 号结点，接下来 $m$ 个操作：
+  - 对结点 $u$ 添加一个颜色为 $c$ 的叶子结点 $n+1$(设当前共有 $n$ 个结点)
+  - 查询结点 $u$ 子树颜色为 $c$ 的结点数量
+==== 题解 ====
+维护每个结点 $u$ 的最新儿子 $\text{hson}(u)$ 以及每个结点的子树在单括号序列的终止结点 $\text{dfr}(u)$(子树不包含该点)。
+于是新插入叶子结点 $n+1$ 时，如果 $u$ 没有叶子结点，则有 $\text{dfr}(n+1)\gets \text{dfr}(u)$，否则有 $\text{dfr}(n+1)\gets \text{hson}(u)$。
+然后将 $\text{hson}(u)$ 更新为 $n+1$ 即可实现序列的维护。$u$ 的子树查询等价于查询序列 $[\text{pos}(u),\text{pos}(\text{dfr}(u)))$ 的信息。
+接下来为每种颜色开一个平衡树，每棵平衡树维护该颜色结点的所有位置。
+则操作 $2$ 等价于查询颜色为 $c$ 的平衡树中位置位于 $[\text{pos}(u),\text{pos}(\text{dfr}(u)))$ 的结点个数。
+发现 $\text{pos}(u)$ 是动态更新的，但是 $\text{pos}(u),\text{pos}(v)$ 的相对大小是不会改变的，因此考虑建立一棵平衡树维护所有 $\text{pos}(u)$。
+如果用 $\text{splay}$ 维护 $\text{pos}(u)$，则每次查询 $\text{pos}(u)$ 时间复杂度为 $O(\log n)$，在颜色为 $c$ 的平衡树查询的结点数的时间复杂度为 $O\left(\log^2 n\right)$。
+考虑 $O(1)$ 查询 $\text{pos}(u)$。一种想法是将 $\text{pos}(u)$ 映射到实数空间，每次插入叶子结点则将 $\text{pos}(n+1)$ 赋值为 $\cfrac {\text{pos}(u)+\text{pos}(v)}{2}$。
+其中 $u,v$ 表示 $n+1$ 在单括号序列的左右相邻结点，但这样会导致精度误差。
+考虑替罪羊树维护 $\text{long long}$ 空间，替罪羊树定期重构重新赋值部分 $\text{pos}(u)$，保证了树的深度，不会导致精度误差。
+算法总时间复杂度变为  $O(n\log n)$。
+<hidden 查看代码>
+<code cpp>
+const int MAXN=5e5+5;
+const LL MAXV=1LL<<62;
+LL val[MAXN];
+namespace Tree1{
+	#define lch(k) node[node[k].lch]
+	#define rch(k) node[node[k].rch]
+	const double alpha=0.70;
+	struct Node{
+		int lch,rch,sz;
+	}node[MAXN];
+	int root,a[MAXN],n;
+	bool isbad(int k){
+		return alpha*node[k].sz<max(lch(k).sz,rch(k).sz);
+	}
+	void build(int &k,int lef,int rig,LL vl,LL vr){
+		if(lef>rig) return k=0,void();
+		int mid=lef+rig>>1;
+		k=a[mid];
+		val[k]=vl+vr>>1;
+		if(lef==rig){
+			node[k].lch=node[k].rch=0;
+			node[k].sz=1;
+			return;
+		}
+		build(node[k].lch,lef,mid-1,vl,val[k]-1);
+		build(node[k].rch,mid+1,rig,val[k]+1,vr);
+		node[k].sz=lch(k).sz+rch(k).sz+1;
+	}
+	void dfs(int k){
+		if(!k)return;
+		dfs(node[k].lch);
+		a[++n]=k;
+		dfs(node[k].rch);
+	}
+	void rebuild(int &k,LL vl,LL vr){
+		n=0;
+		dfs(k);
+		build(k,1,n,vl,vr);
+	}
+	void check(int &k,int id,LL vl,LL vr){
+		if(k){
+			if(isbad(k))
+			rebuild(k,vl,vr);
+			else if(val[id]<val[k])
+			check(node[k].lch,id,vl,val[k]-1);
+			else
+			check(node[k].rch,id,val[k]+1,vr);
+		}
+	}
+	void Insert(int &k,int id){
+		if(!k){
+			k=id;
+			node[k].lch=node[k].rch=0;
+			node[k].sz=1;
+			return;
+		}
+		node[k].sz++;
+		if(val[id]<val[k])
+		Insert(node[k].lch,id);
+		else
+		Insert(node[k].rch,id);
+	}
+	void Insert(int id){
+		Insert(root,id);
+		check(root,id,0,MAXV);
+	}
+	#undef lch
+	#undef rch
+}
+namespace Tree2{
+	struct Node{
+		int r,sz,ch[2];
+	}node[MAXN];
+	#define lch(k) node[node[k].ch[0]]
+	#define rch(k) node[node[k].ch[1]]
+	void push_up(int k){
+		node[k].sz=lch(k).sz+rch(k).sz+1;
+	}
+	void split(int k,int &k1,int &k2,LL v){
+		if(!k) return k1=k2=0,void();
+		if(val[k]<=v){
+			k1=k;
+			split(node[k].ch[1],node[k1].ch[1],k2,v);
+			push_up(k1);
+		}else{
+			k2=k;
+			split(node[k].ch[0],k1,node[k2].ch[0],v);
+			push_up(k2);
+		}
+	}
+	void merge(int &k,int k1,int k2){
+		if(!k1||!k2)return k=k1|k2,void();
+		if(node[k1].r>node[k2].r){
+			k=k1;
+			merge(node[k].ch[1],node[k1].ch[1],k2);
+			push_up(k);
+		}else{
+			k=k2;
+			merge(node[k].ch[0],k1,node[k2].ch[0]);
+			push_up(k);
+		}
+	}
+	void Insert(int &root,int id){
+		node[id].r=rand();
+		node[id].sz=1;
+		node[id].ch[0]=node[id].ch[1]=0;
+		int lef,rig;
+		split(root,lef,rig,val[id]);
+		merge(lef,lef,id);
+		merge(root,lef,rig);
+	}
+	int rank(int root,LL v){
+		int lef,rig,ans;
+		split(root,lef,rig,v-1);
+		ans=node[lef].sz+1;
+		merge(root,lef,rig);
+		return ans;
+	}
+	int query(int root,LL vl,LL vr){
+		return rank(root,vr)-rank(root,vl);
+	}
+	#undef lch
+	#undef rch
+};
+int root[MAXN],col[MAXN],hson[MAXN],dfr[MAXN];
+void solve(){
+	int n=1;
+	col[1]=read_int();
+	val[1]=0;
+	val[0]=MAXV;
+	Tree1::Insert(1);
+	Tree2::Insert(root[col[1]],1);
+	int m=read_int(),lastans=0;
+	while(m--){
+		int t=read_int()^lastans,u=read_int()^lastans,c=read_int()^lastans;
+		if(t==1){
+			int v=hson[u]?hson[u]:dfr[u];
+			hson[u]=++n;
+			col[n]=c;
+			dfr[n]=v;
+			val[n]=val[u]+val[v]>>1;
+			Tree1::Insert(n);
+			Tree2::Insert(root[c],n);
+		}
+		else{
+			lastans=Tree2::query(root[c],val[u],val[dfr[u]]);
+			enter(lastans);
+		}
+	}
+	Tree1::root=0;
+	_rep(i,1,n){
+		root[col[i]]=0;
+		hson[i]=dfr[i]=0;
+	}
+}
+int main()
+{
+	int T=read_int();
+	while(T--)
+	solve();
 	return 0;
 }
@@ 行 488: / 行 688: @@
 		solve();
 	}
+	return 0;
+}
+</code>
+</hidden>
+===== K. Starch Cat =====
+==== 题意 ====
+给定一棵点权树，每次询问一条路径的最大权值，强制在线。其中，路径的权值定义为该路径上的最大权点集，满足点集中所有点都不相邻。
+==== 题解 ====
+考虑建立点分树。对固定的根节点 $\text{rt}$，设 $\text{dp}(u,0/1,0/1)$ 表示从根节点出发到 $u$ 的路径，选/不选根节点以及选/不选 $u$ 结点得到的最大权值。
+不难得到状态转移方程，进一步，设 $f(d,u,0/1)$ 表示 $u$ 在点分树上根节点深度为 $d$ 的结点到 $u$ 的路径，选/不选根节点的最大权值。
+最后对于询问操作，可以找到 $u,v$ 在点分树上的 $\text{LCA}$，设 $\text{LCA}$ 在点分树的深度为 $d$，则答案为
+$$
+\max(f(d,u,0)+f(d,v,0),f(d,u,1)+f(d,v,1)-a_{\text{LCA}})
+$$
+时间复杂度 $O((n+m)\log n)$，尽管 $m$ 很大，但常数很小而且时限比较宽松，所以能过。
+<hidden 查看代码>
+<code cpp>
+struct Rand{
+    unsigned int n,seed;
+    Rand(unsigned int n,unsigned int seed)
+    :n(n),seed(seed){}
+    int get(long long lastans){
+        seed ^= seed << 13;
+        seed ^= seed >> 17;
+        seed ^= seed << 5;
+        return (seed^lastans)%n+1;
+    }
+};
+const int MAXN=5e5+5,MAXD=20;
+const LL inf=1e15;
+struct Edge{
+	int to,next;
+}edge[MAXN<<1];
+int head[MAXN],edge_cnt;
+void Insert(int u,int v){
+	edge[++edge_cnt]=Edge{v,head[u]};
+	head[u]=edge_cnt;
+}
+int sz[MAXN],mson[MAXN],tot_sz,root,root_sz;
+bool vis[MAXN];
+int a[MAXN],rt[MAXD][MAXN];
+LL dp[MAXN][2][2],dp2[MAXD][MAXN][2];
+void dfs(int u,int fa,int dep){
+	rt[dep][u]=root;
+	if(fa==0){
+		dp[u][0][0]=0;
+		dp[u][1][1]=a[u];
+		dp[u][1][0]=dp[u][0][1]=-inf;
+	}
+	else{
+		dp[u][0][0]=max(dp[fa][0][0],dp[fa][0][1]);
+		dp[u][0][1]=dp[fa][0][0]+a[u];
+		dp[u][1][0]=max(dp[fa][1][0],dp[fa][1][1]);
+		dp[u][1][1]=dp[fa][1][0]+a[u];
+	}
+	dp2[dep][u][0]=max(dp[u][0][0],dp[u][0][1]);
+	dp2[dep][u][1]=max(dp[u][1][0],dp[u][1][1]);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v]||v==fa)
+		continue;
+		dfs(v,u,dep);
+	}
+}
+void solve2(int u,int dep){
+	dfs(u,0,dep);
+}
+void find_root(int u,int fa){
+	sz[u]=1;mson[u]=0;
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v]||v==fa)
+		continue;
+		find_root(v,u);
+		sz[u]+=sz[v];
+		mson[u]=max(mson[u],sz[v]);
+	}
+	mson[u]=max(mson[u],tot_sz-sz[u]);
+	if(mson[u]<root_sz){
+		root=u;
+		root_sz=mson[u];
+	}
+}
+void solve(int u,int dep){
+	int cur_sz=tot_sz;
+	vis[u]=true;
+	solve2(u,dep);
+	for(int i=head[u];i;i=edge[i].next){
+		int v=edge[i].to;
+		if(vis[v])
+		continue;
+		tot_sz=sz[v]>sz[u]?cur_sz-sz[u]:sz[v];
+		root_sz=MAXN;
+		find_root(v,u);
+		solve(root,dep+1);
+	}
+}
+LL query(int u,int v){
+	int d=0;
+	while(rt[d][u]&&rt[d][u]==rt[d][v])d++;
+	d--;
+	return max(dp2[d][u][0]+dp2[d][v][0],dp2[d][u][1]+dp2[d][v][1]-a[rt[d][u]]);
+}
+int main(){
+	int n=read_int(),m=read_int(),seed=read_int();
+	_rep(i,1,n)a[i]=read_int();
+	_rep(i,2,n){
+		int f=read_int();
+		Insert(f,i);
+		Insert(i,f);
+	}
+	root_sz=MAXN;
+	tot_sz=n;
+	find_root(1,0);
+	solve(root,0);
+	long long lastans=0,ans=0;
+	constexpr int P=998244353;
+	Rand rand(n,seed);
+	for(int i=0;i<m;i++){
+	    int u=rand.get(lastans);
+	    int v=rand.get(lastans);
+	    int x=rand.get(lastans);
+	    lastans=query(u,v);//calculate the answer
+	    ans=(ans+lastans%P*x)%P;
+	}
+	enter(ans);
 	return 0;
 }
 </code>
 </hidden>

CVBB ACM Team

用户工具

站点工具

页面工具