当前位置: 首页 > news >正文

CF280D k-Maximum Subsequence Sum 题解(线段树+反悔贪心维护k段最大子段和)

线段树维护区间最大子段和是好做的:每个节点维护当前最大子段和、从左端点开始的最大子段和、从右端点开始的最大子段和、当前节点的和。

这个题允许我们选择最多 \(k\) 段,于是我们可以考虑一个类似于反悔贪心的做法:一开始区间内所有元素的系数都是 \(+1\),代表所有元素都没选入答案。假设我们第一次选择了一个子区间 \([l,r]\in [L,R]\),则我们可以将 \([l,r]\) 的元素都乘以 \(-1\),代表答案中已经选择了 \([l,r]\) 这个区间的元素,然后再选择修改后的一个区间。

例如数组 \(a=[-1,100,-100,100,-1]\),第一次选择区间 \([2,4]\),则将 \(a\) 修改为 \([-1,-100,100,-100,-1]\),然后再选择此时的最大子段和区间 \([3,3]\),代表我们不选 \(3\) 这个元素。

容易发现,我们每次操作都会新增一个选段,所以最多进行 \(k\) 次这样的操作。如果一次操作时发现选择的子段和为负,则代表已经没有正贡献的元素了,可以直接停止。

于是我们只需要维护最大、最小子段和(因为要处理取相反数的操作),以及对应的方案。

时间复杂度 \(O(mk\log n)\).

const int MAXN = 1e5 + 5;
int n, m, a[MAXN];struct _sgt {struct _node {int sm, flg, lmx, rmx, mx, lmn, rmn, mn;int lmxi, rmxi, mxl, mxr, lmni, rmni, mnl, mnr;} tr[MAXN << 2];void update(_node &x, _node ls, _node rs) {x.sm = ls.sm + rs.sm;tie(x.lmx, x.lmxi) = max(make_pair(ls.lmx, ls.lmxi),make_pair(ls.sm + rs.lmx, rs.lmxi));tie(x.rmx, x.rmxi) = max(make_pair(rs.rmx, rs.rmxi),make_pair(rs.sm + ls.rmx, ls.rmxi));tie(x.mx, x.mxl, x.mxr) = max({make_tuple(ls.mx, ls.mxl, ls.mxr),make_tuple(rs.mx, rs.mxl, rs.mxr),make_tuple(ls.rmx + rs.lmx, ls.rmxi, rs.lmxi),});tie(x.lmn, x.lmni) = min(make_pair(ls.lmn, ls.lmni),make_pair(ls.sm + rs.lmn, rs.lmni));tie(x.rmn, x.rmni) = min(make_pair(rs.rmn, rs.rmni),make_pair(rs.sm + ls.rmn, ls.rmni));tie(x.mn, x.mnl, x.mnr) = min({make_tuple(ls.mn, ls.mnl, ls.mnr),make_tuple(rs.mn, rs.mnl, rs.mnr),make_tuple(ls.rmn + rs.lmn, ls.rmni, rs.lmni),});}void pushup(int p) {update(tr[p], tr[lson], tr[rson]);}void addtag(int p) {tr[p].flg = !tr[p].flg;tr[p].lmx *= -1;tr[p].rmx *= -1;tr[p].mx *= -1;tr[p].lmn *= -1;tr[p].rmn *= -1;tr[p].mn *= -1;tr[p].sm *= -1;swap(tr[p].lmx, tr[p].lmn);swap(tr[p].lmxi, tr[p].lmni);swap(tr[p].rmx, tr[p].rmn);swap(tr[p].rmxi, tr[p].rmni);swap(tr[p].mx, tr[p].mn);swap(tr[p].mxl, tr[p].mnl);swap(tr[p].mxr, tr[p].mnr);}void pushdown(int p) {if (!tr[p].flg) return;addtag(lson); addtag(rson);tr[p].flg = 0;}auto query(int p, int l, int r, int L, int R) {if (L <= l && r <= R) return tr[p];pushdown(p);int v = INT_MIN;_node res = {v, 0, v, v, v, v, v, v};auto ls = (L <= mid ? query(lson, l, mid, L, R) : res);auto rs = (mid < R ? query(rson, mid + 1, r, L, R) : res);update(res, ls, rs);return res;}void modify(int p, int l, int r, int L, int R) {if (L <= l && r <= R) return addtag(p);pushdown(p);if (L <= mid) modify(lson, l, mid, L, R);if (mid < R) modify(rson, mid + 1, r, L, R);pushup(p);}void build(int p, int l, int r) {if (l == r) {tr[p] = {a[l], 0, a[l], a[l], a[l], a[l], a[l], a[l], l, l, l, l, l, l, l, l};return;}build(lson, l, mid);build(rson, mid + 1, r);pushup(p);}void modify2(int p, int l, int r, int k, int v) {if (l == r) {tr[p] = {v, 0, v, v, v, v, v, v, l, l, l, l, l, l, l, l};return;}pushdown(p);if (k <= mid) modify2(lson, l, mid, k, v);else modify2(rson, mid + 1, r, k, v);pushup(p);}
} t;void work() {cin >> n;for (int i = 1; i <= n; ++i)cin >> a[i];t.build(1, 1, n);cin >> m;while (m--) {int op; cin >> op;if (op == 0) {int k, v; cin >> k >> v;t.modify2(1, 1, n, k, v);} else {int l, r, k, ans = 0; cin >> l >> r >> k;vector<pair<int, int>> v;for (int i = 1; i <= k; ++i) {auto res = t.query(1, 1, n, l, r);int tmp = res.mx, L = res.mxl, R = res.mxr;if (tmp < 0) break;ans += tmp;t.modify(1, 1, n, L, R);v.push_back({L, R});}for (auto [L, R]:v)t.modify(1, 1, n, L, R);cout << ans << endl;}}
}
http://www.hskmm.com/?act=detail&tid=26759

相关文章:

  • 2025 西安新房住宅最新推荐榜权威发布:多维度测评 + 选房指南,助你精准置业品质/高端/优质/品牌/刚需新房推荐
  • C# async await 测试一
  • 2025 年快速卷帘门厂家最新推荐排行榜:聚焦智能定制与高效供货,精选实力厂家助您精准选购
  • 实验课1
  • 课后作业1
  • 详细介绍:Windows如何定制键盘按键
  • 深入解析:Oracle、PostgreSQL 与 MySQL 数据库对比分析与实践指南
  • TheHackersLabs Templo writeup
  • PCIe扫盲——链路初始化与训练基础(三)之LTSSM
  • #attrs
  • 国庆比赛总结
  • 记录第一个博客
  • PCIe扫盲——链路初始化与训练基础(二)
  • 2025 年 ppt 素材模板 /ppt 模板 ai 生成 /ppt 模板制作 /ppt 模版 / 课件 PPT 模板工具推荐:iSlide 技术优势与全场景服务能力解析
  • 10.8
  • 课后作业1(01-方法)
  • VMware ESXi 9.0 macOS Unlocker OEM BIOS 2.7 NVMe 驱动特殊定制版
  • 项目案例作业2
  • VMware ESXi 9.0 macOS Unlocker OEM BIOS 2.7 H3C 新华三 定制版
  • VMware ESXi 9.0 macOS Unlocker OEM BIOS 2.7 Inspur 浪潮 定制版
  • 上手 Rokid JSAR:新手也能快速入门的 AR 开发之旅
  • 2025 年氨基酸水溶肥厂家最新推荐榜单:聚焦花芽分化膨果上色需求,精选优质企业助农户科学选购花芽分化/膨果上色/促花稳果/低温酶解氨基酸水溶肥厂家推荐
  • VMware ESXi 8.0U3g macOS Unlocker OEM BIOS 2.7 H3C 新华三 定制版
  • 2025 年最新防火涂料厂家排行榜:钢结构各类防火涂料优质厂家最新推荐,助力建筑安全选型 钢结构/水性/隧道/环保/饰面型防火涂料厂家推荐
  • 嵌入式固件升级框架详解与实战经验
  • 2025 年家用电梯最新推荐排行榜:精选技术领先、服务优质的实力品牌,助您精准选购
  • helm 模板的基础使用
  • 20251008J赛合订本
  • [计算机组成] 计算机字体文件及其运行原理
  • 后量子密码技术延迟随数据量增加而降低