首页 > 其他分享 >P4577 [FJOI2018] 领导集团问题

P4577 [FJOI2018] 领导集团问题

时间:2024-04-04 11:55:18浏览次数:16  
标签:p2 p1 P4577 rs int 领导 mid FJOI2018 ls

P4577 [FJOI2018] 领导集团问题

整体 dp

先将权值离散化到 \([1,m]\)。

考虑朴素的树形 dp,设 \(f_{u,i}\) 表示在 \(u\) 子树中选了若干点,点权都 \(\ge i\) 的最大点集。转移分为是否选 \(u\) 点:

不选 \(u\) 点,对于 \(i\in [1,m]\),\(f_{u,i}=\sum f_{v,i}\)

选 \(u\) 点,对于 \(i\in [1,a_u]\),\(f_{u,i}=\max(f_{u,i},\sum f_{v,a_u}+1)\)

前者由于状态中为 \(\ge i\),所以就是一个单点加;后者是区间修改 \(\max\)。这些操作都是线段树合并操作,考虑整体 dp,前者 merge 操作时覆盖,后者区间覆盖 \(\max\),也可以线段树维护标记。但是在动态开点线段树上区间修改较复杂,在这题有更好的办法。

可以发现 \(f_{u,i}\ge f_{u,i+1}\),也就是序列是从左到右单调递减的,再看第二个操作,\(f_{u,a_u}\) 一定会加 \(1\),然后就是覆盖一段 \([p,a_u]\) 权值都是 \(f_{u,a_u}\) 的极大区间,并且改变的量为 \(1\)。考虑一个 trick,维护 \(g_{u,i}=f_{u,i}-f_{u,i+1}\)。区间覆盖就变成只需要修改 \(p-1\) 和 \(a_u\) 两个点的差分值即可(区间 \([p,a_u]\) 的差分值都是 \(0\))。考虑 \(p\) 的求法,只需要在线段树二分即可,单次 \(O(\log n)\)。

复杂度 \(O(n\log n)\)。

#include <bits/stdc++.h>
#define pii std::pair<int, int>
#define fi first
#define se second
#define pb push_back
typedef long long i64;
const int N = 2e5 + 10;
int n, cnt, tot, num, ans;
int a[N], b[N];
int h[N];
struct node {
	int to, nxt;
} e[N << 1];
void add(int u, int v) {
	e[++cnt].to = v;
	e[cnt].nxt = h[u];
	h[u] = cnt;
}
struct seg {
	int ls, rs, sm;
} t[N * 40];
void gtag(int u, int v) {if(u) t[u].sm += v;}
void pushup(int u, int ls, int rs) {
	t[u].sm = 0;
	if(ls) t[u].sm = t[ls].sm;
	if(rs) t[u].sm += t[rs].sm;
}
void ins(int &u, int l, int r, int x, int y) {
	if(!x) return;
	if(!u) u = ++tot;
	if(l == r) {
		gtag(u, y);
		return; 
	}
	int mid = (l + r) >> 1;
	if(x <= mid) ins(t[u].ls, l, mid, x, y);
	else ins(t[u].rs, mid + 1, r, x, y);
	pushup(u, t[u].ls, t[u].rs);
}
int query(int u, int l, int r, int L, int R) {
	if(!u) return 0;
	if(L <= l && r <= R) {
		return t[u].sm;
	}
	int mid = (l + r) >> 1, ret = 0;
	if(L <= mid) ret += query(t[u].ls, l, mid, L, R);
	if(R > mid) ret += query(t[u].rs, mid + 1, r, L, R);
	return ret;
}
void mg(int p1, int p2, int l, int r) {
	if(l == r) {
		t[p1].sm += t[p2].sm;
		return;
	}
	int mid = (l + r) >> 1;
	if(t[p1].ls && t[p2].ls) mg(t[p1].ls, t[p2].ls, l, mid);
	else if(t[p2].ls) t[p1].ls = t[p2].ls;
	if(t[p1].rs && t[p2].rs) mg(t[p1].rs, t[p2].rs, mid + 1, r);
	else if(t[p2].rs) t[p1].rs = t[p2].rs;
	pushup(p1, t[p1].ls, t[p1].rs);
}
int find(int u, int l, int r, int v) {
	if(!u) return 0;
	if(l == r) {
		if(t[u].sm < v) return l - 1;
		return l;
	}
	int mid = (l + r) >> 1;
	if(v <= t[t[u].rs].sm) return find(t[u].rs, mid + 1, r, v); 
	else return find(t[u].ls, l, mid, v - t[t[u].rs].sm);
}
void dfs(int u, int fa) {
	for(int i = h[u]; i; i = e[i].nxt) {
		int v = e[i].to;
		if(v == fa) continue;
		dfs(v, u);
		mg(u, v, 1, num);
	}
	int sum = query(u, 1, num, a[u], num), p = find(u, 1, num, sum + 1);
	ins(u, 1, num, a[u], 1), ins(u, 1, num, p, -1);
}
void Solve() {
	std::cin >> n;

	tot = n;
	for(int i = 1; i <= n; i++) {
		std::cin >> a[i];
		b[++num] = a[i];
	}
	std::sort(b + 1, b + num + 1);
	num = std::unique(b + 1, b + num + 1) - b - 1;
	for(int i = 1; i <= n; i++) {
		a[i] = std::lower_bound(b + 1, b + num + 1, a[i]) - b;
	}
	for(int i = 2; i <= n; i++) {
		int u;
		std::cin >> u;
		add(u, i), add(i, u);
	}

	dfs(1, 0);
	std::cout << query(1, 1, num, 1, num) << "\n";
}
int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
	Solve();

	return 0;
}

标签:p2,p1,P4577,rs,int,领导,mid,FJOI2018,ls
From: https://www.cnblogs.com/FireRaku/p/18114037

相关文章

  • 【题解】A18535.来自领导的烦恼
    题目跳转思路:本题可以使用动态规划或递归的方式来实现,本质上是一道01背包的变型题。假设一共有\(n\)名员工,每一位员工的技能水平用\(a[i]\)表示。要使得两个部门的员工技能总和之差最小,意思就是尽可能地将一个部门的技能之和”凑“到\(\sum\limits_{i=1}^{n}a[i]\times\frac{1}......
  • 管理类联考-复试-管理类知识-领导&激励理论&控制
    激励理论69.......
  • 浅谈为客户或领导装系统和软件并设参调试运行
    一,问清”题目“和需求1.为啥要安装这个系统?要问详细了,不能简单笼统概括为WINXP/WIN7/WIN10/WIN11,而是要具体到那一年那个版本的win7,比如我就要装Windows7UltimatewithServicePack1(x64)的系统,软件安装说明书或者工程师说了,那再装。2.被安装的主机硬件配置是多少?......
  • 如何高效完成领导安排的复杂工作任务?罗列待办任务清单很有效
    面对日益激烈的商业竞争环境,企业的发展不仅要求我们不断提升自身的能力,还要求我们有能力独立处理越来越复杂的工作任务。这让我和许多同事都在思考一个问题:如何高效完成领导安排的复杂工作任务呢?在寻找高效完成任务的方法中,我发现将复杂的工作任务拆分,罗列出完成这项任务所需的待......
  • 从一步先到步步先,华为确立折叠屏领导地位
    在经历了连续几年的市场低迷之后,2024年智能手机迎来了复苏。春节刚过,华为就发布了甲辰龙年的第一款新机——华为Pocket2,为行业复苏点燃了第一把火。折叠屏手机作为一个新品类,从2019年出现至今已经过去近5年时间,随着技术的成熟以及用户认知的提升,正在跨越鸿沟进入到主流市场中。......
  • 领导力提升,才是高绩效的关键
    作为企业的CEO或团队管理者,在日常的团队管理工作中无论是领导力还是执行力,都是非常重要的。在领导力的提升方面,我们可以通过一整套方案来进行,包括如何设定目标,动机刺激、任务拆解、鼓励参与、责任承担、建立制度、建立文化、培养和提升员工及团队综合能力等等。找到团队核心目标......
  • 如何提升项目管理中的领导力?非常有效
    项目管理者是整个团队的领导,需要制定计划,组织团队,但很少有项目能完全按照计划实行,在项目过程中经常会出现一些问题,那么面对问题,如何来提升领导力呢? 1.要有组织与协调能力 想要成为一名受人尊敬和爱戴的领导,就必须学会正确的领导方法,就像弹钢琴那样,十个手指有长有短,要有分工与合......
  • 新疆维吾尔自治区卫健委领导莅临神州医疗大兴产品研发及产业化基地调研指导
    1月23日,新疆维吾尔自治区卫生健康委员会党组成员、副主任邹小广莅临神州医疗北京大兴产品研发及产业化基地调研指导工作。神州医疗联合创始人、总裁范子怡,副总裁胡守旺等热情接待并全程陪同。范子怡总裁首先对邹小广副主任的到来表示热烈欢迎,她介绍了神州医疗在精准医学方面的创新......
  • 初中英语优秀范文100篇-065I Want to Be a Leader in Group Work-我想在小组工作中担
    PDF格式公众号回复关键字:SHCZFW065记忆树1Therearemanydifferentrolesingroupwork.翻译在集体工作中,有很多不同的角色。简化记忆集体句子结构therebe的基本句型为:therebe+人或物+地点。其中,there是一个引导词,没有具体实际词义,be是谓语动词,人或物才是这......
  • 恭贺弘博创新-领导力沙盘模拟3.0特训营顺利举行
    2024年1月14日,弘博创新举办领导力沙盘模拟3.0特训营,汇聚了来自各行各业的精英,共同探讨领导力的发展与实践。 本次特训营邀请了国内著名领导力发展与企业管理效能提升专家王兵围老师通过生动的案例、启发式的沙盘演练和沉浸式的互动讨论等形式,引导大家深入了解领导力的内涵与实践。......