首页 > 其他分享 >[COCI2015-2016#3] NEKAMELEONI 题解

[COCI2015-2016#3] NEKAMELEONI 题解

时间：2024-08-05 22:09:33浏览次数：12  
标签：now idx int 题解 COCI2015 tree siz 2016 top

前言

题目链接：LOJ；洛谷。

题意简述

在二叉树上，不断删除叶子，你要维护其树链剖分后重儿子编号和。如果两个孩子大小相同，在一开始连向左儿子，或者保持修改前的连接。

\(n \leq 2 \times 10^5\)。

题目分析

有分块的、有二分的，那我来讲一讲我的想法——树剖维护树剖。

首先反转操作，不断加叶子，那么可能发生变化的就是根到当前结点上，轻儿子变成重儿子。由于树链剖分的性质，这样的个数不会超过 \(\log\)。考虑根据它的树剖，不断跳到重链顶 \(u\)，判断 \(\operatorname{fa}(u)\) 的重儿子会不会从 \(\operatorname{bro}(u)\) 变成 \(u\)。

假设发生了变化，那么会发生什么？记 \(\operatorname{tail}(u)\) 表示一条以 \(u\) 为 \(\operatorname{top}\) 的重链的链底。记 \(v = \operatorname{top}(\operatorname{fa}(u))\)，那么我们要把 \(\operatorname{bro}(u) \sim \operatorname{tail}(v)\) 的 \(\operatorname{top}\) 修改为 \(\operatorname{bro}(u)\)，并把 \(u \sim \operatorname{tail}(u)\) 的 \(\operatorname{top}\) 修改为 \(v\)，而且 \(\operatorname{tail}(v)\) 修改为 \(\operatorname{tail}(u)\)。

树链修改，考虑用树剖。嗯？显然不能用它这个变来变去的树剖，不然上不了数据结构。所以要把最终的二叉树先剖了，用一棵线段树支持树链修改。

至于如何判断会不会发生改变，我们显然困扰在 \(\operatorname{siz}(u) = \operatorname{siz}(\operatorname{bro}(u))\) 的情况，这种情况会保持当前操作之前的形态。如果 \(u\) 和 \(\operatorname{bro}(u)\) 之前都没有任何操作，那么就是保持在左儿子。否则，考虑最后一次操作是在 \(u\) 还是 \(\operatorname{bro}(u)\)，其所在的结点就是操作前的重儿子。为什么？由题意正向考虑，在这一次操作前，其所在节点的 \(\operatorname{siz}\) 大，是在删除后才相等，所以保留。

这个可以无脑主席树和 dfs 序。相当于查询子树里第 \(i\) 个版本的最大值。

注意到，维护 \(\operatorname{siz}\) 也可以用树链剖分无脑维护。

预处理出完成所有操作后的树的树链剖分，很水。但是把重儿子编号记成了轻儿子编号还能有 \(60\) 分？

总的时间复杂度是 \(\Theta(m \log^3 n)\)。

代码

有一些细节要注意。无脑的坏处是码量略大。

#include <iostream>
#include <cstdio>
using namespace std;

int n, m;
int L[200010], R[200010];
int del[200010];
long long ans[200010];
bool mark[200010];
int when[200010];

int fa[200010], top[200010], dpt[200010];
int son[200010], siz[200010];
void dfs(int now) {
	siz[now] = 1;
	if (L[now]) dpt[L[now]] = dpt[now] + 1, fa[L[now]] = now, dfs(L[now]), siz[now] += siz[L[now]], siz[L[now]] > siz[son[now]] && (son[now] = L[now]);
	if (R[now]) dpt[R[now]] = dpt[now] + 1, fa[R[now]] = now, dfs(R[now]), siz[now] += siz[R[now]], siz[R[now]] > siz[son[now]] && (son[now] = R[now]);
}
int dfn[200010], timer;
int dfnL[200010], dfnR[200010];
void redfs(int now, int tp) {
	dfn[dfnL[now] = ++timer] = now;
	top[now] = tp;
	if (son[now]) redfs(son[now], tp);
	if (L[now] && L[now] != son[now]) redfs(L[now], L[now]);
	if (R[now] && R[now] != son[now]) redfs(R[now], R[now]);
	dfnR[now] = timer;
}

int TOP[200010], SON[200010], SIZ[200010];
int ED[200010];
void DFS(int now) {
	SIZ[now] = !mark[now];
	if (L[now]) DFS(L[now]), SIZ[now] += SIZ[L[now]], when[now] = max(when[now], when[L[now]]);
	if (R[now]) DFS(R[now]), SIZ[now] += SIZ[R[now]], when[now] = max(when[now], when[R[now]]);
	if (!mark[now]) {
		if (L[now] && !mark[L[now]] && siz[L[now]] > siz[R[now]]) {
			SON[now] = L[now];
		} else if (R[now] && !mark[R[now]] && siz[R[now]] > siz[L[now]]) {
			SON[now] = R[now];
		} else {
			if (L[now] && !mark[L[now]] && when[L[now]] > when[R[now]]) {
				SON[now] = L[now];
			} else if (R[now] && !mark[R[now]]){
				SON[now] = R[now];
			} else if (L[now] && !mark[L[now]]){
				SON[now] = L[now];
			} else {
				SON[now] = 0;
			}
		}
	}
}
void REDFS(int now, int tp) {
	TOP[now] = tp, ED[tp] = now;
	if (SON[now]) REDFS(SON[now], tp), ans[m + 1] += SON[now];
	if (L[now] && !mark[L[now]] && L[now] != SON[now]) REDFS(L[now], L[now]);
	if (R[now] && !mark[R[now]] && R[now] != SON[now]) REDFS(R[now], R[now]);
}

struct Segment_Tree {
	#define lson (idx << 1    )
	#define rson (idx << 1 | 1)
	
	struct node {
		int l, r;
		int top, siz;
		bool tag;
		int lazy;
	} tree[200010 << 2];
	
	void build(int idx, int l, int r) {
		tree[idx] = {l, r, 0, 0, false, 0};
		if (l == r) return tree[idx].top = TOP[dfn[l]], tree[idx].siz = SIZ[dfn[l]], void();
		int mid = (l + r) >> 1;
		build(lson, l, mid);
		build(rson, mid + 1, r);
	}
	
	void pushtag_top(int idx, int tp) {
		tree[idx].top = tp;
		tree[idx].tag = true;
	}
	
	void pushtag_lazy(int idx, int lazy) {
		tree[idx].lazy += lazy;
		tree[idx].siz += lazy;
	}
	
	void pushdown(int idx) {
		if (tree[idx].tag) {
			pushtag_top(lson, tree[idx].top);
			pushtag_top(rson, tree[idx].top);
			tree[idx].tag = false;
		}
		if (tree[idx].lazy) {
			pushtag_lazy(lson, tree[idx].lazy);
			pushtag_lazy(rson, tree[idx].lazy);
			tree[idx].lazy = 0;
		}
	}
	
	void modify_top(int idx, int l, int r, int val) {
		if (tree[idx].l > r || tree[idx].r < l) return;
		if (l <= tree[idx].l && tree[idx].r <= r) return pushtag_top(idx, val);
		pushdown(idx);
		modify_top(lson, l, r, val);
		modify_top(rson, l, r, val);
	}
	
	void modify_lazy(int idx, int l, int r, int val) {
		if (tree[idx].l > r || tree[idx].r < l) return;
		if (l <= tree[idx].l && tree[idx].r <= r) return pushtag_lazy(idx, val);
		pushdown(idx);
		modify_lazy(lson, l, r, val);
		modify_lazy(rson, l, r, val);
	}
	
	int query_siz(int idx, int p) {
		if (tree[idx].l > p || tree[idx].r < p) return 0;
		if (tree[idx].l == tree[idx].r) return tree[idx].siz;
		pushdown(idx);
		return query_siz(lson, p) | query_siz(rson, p);
	}
	
	int query_top(int idx, int p) {
		if (tree[idx].l > p || tree[idx].r < p) return 0;
		if (tree[idx].l == tree[idx].r) return tree[idx].top;
		pushdown(idx);
		return query_top(lson, p) | query_top(rson, p);
	}
	
	#undef lson
	#undef rson
} yzh;

int bro(int x) {
	if (x == L[fa[x]]) return mark[R[fa[x]]] ? 0 : R[fa[x]];
	return mark[L[fa[x]]] ? 0 : L[fa[x]];
}

int gettop(int x) {
	return yzh.query_top(1, dfnL[x]);
}

int getsiz(int x) {
	return yzh.query_siz(1, dfnL[x]);
}

void modify_lazy(int u, int v) {
	while (top[u] != top[v]) {
		if (dpt[top[u]] < dpt[top[v]]) swap(u, v);
		yzh.modify_lazy(1, dfnL[top[u]], dfnL[u], 1);
		u = fa[top[u]];
	}
	if (dfnL[u] > dfnL[v]) swap(u, v);
	yzh.modify_lazy(1, dfnL[u], dfnL[v], 1);
}

void modify_top(int u, int v, int w) {
	while (top[u] != top[v]) {
		if (dpt[top[u]] < dpt[top[v]]) swap(u, v);
		yzh.modify_top(1, dfnL[top[u]], dfnL[u], w);
		u = fa[top[u]];
	}
	if (dfnL[u] > dfnL[v]) swap(u, v);
	yzh.modify_top(1, dfnL[u], dfnL[v], w);
}

struct Yet_another_Segment_Tree {
	struct node {
		int lson, rson;
		int val;
	} tree[200010 * 80];
	int tot;
	
	int root[200010];
	
	int copyNode(int idx) {
		return tree[++tot] = tree[idx], tot;
	}
	
	void modify(int &idx, int trl, int trr, int p, int v) {
		if (trl > p || trr < p) return;
		idx = copyNode(idx);
		tree[idx].val = max(tree[idx].val, v);
		if (trl == trr) return;
		int mid = (trl + trr) >> 1;
		modify(tree[idx].lson, trl, mid, p, v);
		modify(tree[idx].rson, mid + 1, trr, p, v);
	}
	
	int query(int idx, int trl, int trr, int l, int r) {
		if (!idx || trl > r || trr < l) return 0;
		if (l <= trl && trr <= r) return tree[idx].val;
		int mid = (trl + trr) >> 1;
		return max(query(tree[idx].lson, trl, mid, l, r), query(tree[idx].rson, mid + 1, trr, l, r));
	}
} ttrr;

bool check(int i, int u, int v) {
	if (i == 1) return L[fa[u]] == u;
	int resu = ttrr.query(ttrr.root[i - 1], 1, n, dfnL[u], dfnR[u]),
		resv = ttrr.query(ttrr.root[i - 1], 1, n, dfnL[v], dfnR[v]);
	if (!resu && !resv) return L[fa[u]] == u;
	return resu > resv;
}

signed main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; ++i) scanf("%d%d", &L[i], &R[i]);
	scanf("%d", &m);
	for (int i = 1; i <= m; ++i) scanf("%d", &del[i]), mark[del[i]] = true, when[del[i]] = i;
	dfs(1), redfs(1, 1);
	DFS(1), REDFS(1, 1);
	for (int i = 1; i <= m; ++i) {
		ttrr.root[i] = ttrr.root[i - 1];
		ttrr.modify(ttrr.root[i], 1, n, dfnL[del[i]], i);
	}
	yzh.build(1, 1, n);
	for (int i = m; i >= 1; --i) {
		int u = del[i];
		long long res = 0;
		mark[u] = false;
		modify_lazy(u, 1);
		yzh.modify_top(1, dfnL[u], dfnL[u], u);
		ED[u] = u;
		if (u == 1) continue;
		if (!bro(u)) {
			SON[fa[u]] = u;
			res += u;
			int ftop = gettop(fa[u]);
			ED[ftop] = ED[u];
			yzh.modify_top(1, dfnL[u], dfnL[u], ftop);
			u = ftop;
		}
		while (u != 1) {
			int v = bro(u);
			int sizu = getsiz(u), sizv = getsiz(v);
			int ftop = gettop(fa[u]);
			if (v && SON[fa[u]] == v && (sizu > sizv || (sizu == sizv && check(i, u, v)))) {
				res += u - v;
				SON[fa[u]] = u;
				ED[v] = ED[ftop];
				ED[ftop] = ED[u];
				modify_top(u, ED[u], ftop);
				modify_top(v, ED[v], v);
			}
			u = ftop;
		}
		ans[i] = ans[i + 1] + res;
	}
	for (int i = 1; i <= m + 1; ++i) {
		printf("%lld\n", ans[i]);
	}
	return 0;
}

标签：now,idx,int,题解,COCI2015,tree,siz,2016,top
From： https://www.cnblogs.com/XuYueming/p/18327374

相关文章

  • Codeforces Round 963 (Div. 2) A - C 详细题解(思路加代码,C++,Python) -- 来自灰名
    比赛链接:Dashboard-CodeforcesRound963(Div.2)-Codeforces之后有实力了再试试后面的题目，现在要做那些题，起码要理解一个多小时题目A:链接:Problem-A-Codeforces题目大意理解:        极少数不考翻译能读懂的cf题目(bushi)每个测试用例第一行一个n，......
  • P4604 [WC2017] 挑战 题解
    题目描述任务一给定\(n\)个\(32\)位无符号整数，将它们从小到大排序。任务二有\(2n\)个人玩"石头剪刀布"游戏，他们分成两排，每排\(n\)个人，\(a_{i,j}=0/1/2\)分别表示第\(i\)排第\(j\)人出石头、剪刀、布。\(q\)次询问，每次给定\(x,y,l\)，询问第一排第\(x\simx......
  • CF228E 题解
    CF228E题解题目简述给定一个\(n\)个点，\(m\)条边的无向图，每条边都为\(0\)或\(1\)，可以进行若干次操作，与此点相连的所有点权值取反，求一种方案使得所有边都变为\(1\)。前置知识二分图二分图染色思路简述首先明白一点：对于同一条边，操作偶数次是没有必要的！因为最终会回......
  • [Violet 6]故乡的梦 题解
    前言题目链接：Hydro&bzoj。题意简述无向联通图给出起点终点，多次询问删边后最短路，或报告不连通。\(n,m,q\leq2\times10^5\)。题目分析首先想到，如果删掉的边不是原来最短路的边，那么最短路不会发生变化。因此我们只需考虑删除了原来在最短路上的边。不妨把原先最短路任......
  • 洛谷-P9830 题解
    思路分析分析样例：见红线，长宽各为2，存在格点；黄线长2宽3，没有格点。考虑延长黄线使得长4宽6，发现有格点。思考格点，如果长和宽都可以被分成\(p\timesl\)的格式，则存在格点。那么，就能想出：推论1：对于\((0\,\0)\)和\((x\,\y)\)之间没有格点，当且仅当\(\gcd(x\,......
  • P9596 冒泡排序 2 题解
    题目链接。Statement记\(f(A)\)为序列\(A\)的冒泡排序趟数，操作：单点改，全局查\(f(A)\).\(n,m\le5\cdot10^5\)，值域1e9.Solution结论：\[Ans=\max_{i\in[1..n]}\left\{\sum_{j\in[1..i]}[A_j>A_i]\right\}\]怎么观察出来啊QAQ证明：对于每个位置\(p\)，观察到每趟都......
  • AGC046C 题解
    blog。好菜啊，不会这题，来写个题解/kel。很难直接做，先找一点性质：操作只改变相对顺序，而总数不变。这启示我们记录每个\(0\)前面的极长\(1\)连续段长度。记第\(i(1\lei\leC)\)个\(0\)对应长度为\(a_i\)，就存在下面的等价表述：每次操作可以选定\(i,j(1\lei<j\leC)\)，......
  • 洛谷-P9574 题解
    思路分析分析样例：==TTBTBTTBTBTTTBTTB->TTBTTBBTTBTTTBTTB->TTBTTBTBBTTTTBTTB->TTBTTBTBBTTTTTBBT----1-----2-----3---4--观察区块2，发现BTTB进行操作后与右边的TB再次构成BTTB，我们发现在这个区块内，可以从左向右不断操作，我们称这种特性为传递性，可......
  • AT_abl_e Replace Digits 题解
    题目传送门前置知识线段树解法需要维护区间信息，考虑使用线段树维护。预处理出\(\overline{xx\dotsx}\)，其中\(x\in\{1,2,3,4,5,6,7,8,9\}\)，便于区间赋值。然后就是普通的线段树板子了。代码#include<bits/stdc++.h>usingnamespacestd;#definelllonglong#de......
  • AGC027C 题解
    注意到如果可以构造出所有由\(\texttt{A}\)和\(\texttt{B}\)组成的字符串，那么在图上游走的路径必须成环，并且的环上的每一个点都必须同时有一个\(\texttt{A}\)邻居和\(\texttt{B}\)邻居。于是可以考虑把点拆分为入点和出点，相邻两个点为\(\texttt{AA},\texttt{BB}\)的，从......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99