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

学习笔记:KTT

学习笔记:KTT

Part.1 基本算法

引入这样一个问题(其实这并不是板子,但是笔者认为这是此算法的另一种理解方式):

luogu P5693 EI 的第六分块

区间加,区间最大子段和。

这东西有个十分重要的性质,所有加的数都是正数。

先考虑怎么单点修,这是山海经,只需维护 \(lmax, rmax, totmax, sum\),竟然如此轻易。

那么现在扩展到区间修改:

首先肯定需要维护刚才提到的四个值,但是修改咋修改这些东西呢。

不难发现肯定就是形如区间加 \(len\times x\),其中 \(len\) 表示这个值对应的区间长度。

那么转化一下就变为了每个节点维护 \(O(len)\) 个一次函数,每次横坐标加 \(x\),询问最大值。

这的确是李超能做到的,但李超最难受的一点便是无法删除(只能撤销),那么如果只涉及这一个节点绝对是正确的,可是如果子节点被修改,那么 PushUp 就会修改区间内的线段,我们不得不暴力重构,这样就假了。

接下来接着挖掘性质,通过观察力可得:\(lmax, rmax, totmax\) 的区间长度单调不减,证明比较简单。

这启发了我们,也就是至多进行 \(O(n\log n)\) 次修改!

现在切入正题:

如果我们可以得知什么时候会发生上述区间长度的增长,那么复杂度就有了保证,可是如何维护这个问题呢,可以通过如下问题更直观的感受(这两个问题其实维护的信息基本一致,不过如下问题更为简洁):

\(n\)\(k_i x+b_i\) 的一次函数,每次区间给 \(x\) 加,区间询问最大值。

如图,不难发现,函数之间的大小关系是“单调”的,像这样的大小关系变换称为一次“击败”事件。

由此,可以维护出产生任意一次击败事件的最小的 \(\Delta x\) 当增加的 \(x\) 高过这个阈值就暴力重构。

惊奇的发现,这个击败事件其实就和上述的 \(lmax\) 等区间长度增长是很像的。

于是这样干复杂度大概就是 \(O(n\log^2 n)\) 的了,经过更严谨的势能分析可以发现是 \(O(n\log^3 n)\) 的,不过实际常数很小,可以近似看做 \(O(n\log^2 n)\)

总复杂度:\(O((n+m)\log^3 n)\)

具体实现就是对于两个一次函数求交点,然后对这个交点的横坐标取个 \(min\) 就行。

回到原问题,既然已经知道了 \(lmax, rmax, totmax, sum\) 的更新方法,那么只需要对 \(lmax, rmax, totmax\) 三个转移的交点统统取 \(min\) 就好。

细节:

  1. \(\Delta x\) 要开浮点数。
  2. 可以封一个一次函数减小码量。
  3. 查询合并两个区间答案使用结构体更加便捷。
EI 的第六分块
#include <iostream>
#include <algorithm>using namespace std;const int N = 4e5 + 10;#define int long long
using ld = long double;
const ld double_inf = 1e100;class Poly
{public :int k, b;Poly operator + (Poly x){return {k + x.k, b + x.b};}Poly operator + (int x){return {k, b + k * x};}
};Poly max(Poly x, Poly y)
{if (x.b != y.b) return x.b < y.b ? y : x;return x.k < y.k ? y : x;
}ld calc(Poly x, Poly y)
{if (x.k == y.k) return double_inf;ld pos = (ld)(x.b - y.b) / (ld)(y.k - x.k);if (pos <= 0) return double_inf;return pos;
}struct Node
{int lmax, rmax, totmax, sum;friend Node operator + (Node x, Node y){Node tmp;tmp.sum = x.sum + y.sum;tmp.lmax = max(x.lmax, x.sum + y.lmax);tmp.rmax = max(y.rmax, y.sum + x.rmax);tmp.totmax = max({x.totmax, y.totmax, x.rmax + y.lmax});return tmp;}
};int a[N];class SemTree
{#define lid id << 1#define rid id << 1 | 1public :Poly lmax[N << 2], rmax[N << 2], totmax[N << 2], sum[N << 2];ld x[N << 2];int tag[N << 2], L[N << 2], R[N << 2];void PushUp(int id){sum[id] = sum[lid] + sum[rid];lmax[id] = max(lmax[lid], sum[lid] + lmax[rid]);rmax[id] = max(rmax[rid], sum[rid] + rmax[lid]);totmax[id] = max(max(totmax[lid], totmax[rid]), rmax[lid] + lmax[rid]);x[id] = min(x[lid], x[rid]);x[id] = min(x[id], calc(lmax[lid], sum[lid] + lmax[rid]));x[id] = min(x[id], calc(rmax[rid], sum[rid] + rmax[lid]));x[id] = min(x[id], min({calc(totmax[lid], totmax[rid]), calc(max(totmax[lid], totmax[rid]), rmax[lid] + lmax[rid])}));// x[id] = min(x[id], min({calc(totmax[lid], totmax[rid]), calc(totmax[lid], rmax[lid] + lmax[rid]), calc(totmax[rid], rmax[lid] + lmax[rid])}));}void Push(int id, int v){tag[id] += v;lmax[id] = lmax[id] + v;rmax[id] = rmax[id] + v;totmax[id] = totmax[id] + v;sum[id] = sum[id] + v;x[id] -= v;}void PushDown(int id){if (tag[id]){Push(lid, tag[id]), Push(rid, tag[id]);tag[id] = 0;}}void ReBuild(int id){if (x[id] <= 0){PushDown(id);x[id] = double_inf;ReBuild(lid), ReBuild(rid);PushUp(id);}}void Build(int id, int l, int r){x[id] = double_inf;L[id] = l;R[id] = r;if (l == r){Poly tmp = {1, a[l]};x[id] = double_inf, lmax[id] = rmax[id] = totmax[id] = sum[id] = tmp;return ;}int mid = (l + r) >> 1;Build(lid, l, mid), Build(rid, mid + 1, r);PushUp(id);}void Update(int id, int cl, int cr, int l, int r, int val){if (l <= cl && cr <= r) return Push(id, val);int mid = (cl + cr) >> 1;PushDown(id);ReBuild(id);if (l <= mid) Update(lid, cl, mid, l, r, val);if (r > mid) Update(rid, mid + 1, cr, l, r, val);PushUp(id);}Node Query(int id, int cl, int cr, int l, int r){if (l <= cl && cr <= r) return {lmax[id].b, rmax[id].b, totmax[id].b, sum[id].b};int mid = (cl + cr) >> 1;PushDown(id);ReBuild(id);if (r <= mid) return Query(lid, cl, mid, l, r);else if (l > mid) return Query(rid, mid + 1, cr, l, r);else return Query(lid, cl, mid, l, r) + Query(rid, mid + 1, cr, l, r);}
}T;signed main()
{// freopen("data.in", "r", stdin); freopen("data.out", "w", stdout);ios :: sync_with_stdio(false), cin.tie(0), cout.tie(0);int n, q; cin >> n >> q;for (int i = 1; i <= n; i++) cin >> a[i];T.Build(1, 1, n);for (int i = 1; i <= q; i++){int op, l, r; cin >> op >> l >> r;if (op == 1){int x; cin >> x;T.Update(1, 1, n, l, r, x);}else{cout << max(0ll, T.Query(1, 1, n, l, r).totmax) << '\n';}}return 0;
}

Part.2 例题

这东西出现概率还是蛮低的。

一道比较好的题:CF 1830F

http://www.hskmm.com/?act=detail&tid=31118

相关文章:

  • 题解:P10104 [GDKOI2023 提高组] 异或图
  • 2025 年筛网厂家推荐榜:聚焦场景适配与高效需求,锰钢筛网/聚氨酯筛网/合金焊接筛网/自清洁筛网/防堵筛网厂家滨州沃森网业成优选
  • P7076 [CSP-S2020] 动物园
  • 汽车价格战全面熄火了?不卷价格该卷什么? - 教程
  • P10067 [CCO 2023] Real Mountains
  • 先辈题解
  • U-Boot启动探秘:从汇编到命令行的奇幻之旅 - 指南
  • 双指针的初步了解
  • 倍增并查集学习笔记
  • 两数相加-leetcode
  • CF2147E
  • 线程共享区域
  • ZR 2025 NOIP 二十连测 #1
  • 运行时数据区
  • work1
  • 2025 年液压机厂家推荐榜:伺服/小型/大型/数控/液压机厂家口碑推荐,品质可靠 聚焦智能适配,助力企业高效生产
  • 快速上手!山海鲸 4 种高频数据接入方式
  • AI赋能,重塑未来招聘:深度解析易路AI人岗匹配解决方案
  • 2025高级语言程序设计第一次作业lcr
  • luogu 个人主页
  • D230809E. 勇敢的阿乐
  • 解码Linux文件IO之标准IO
  • 10.14 CSP-S模拟31 改题记录
  • 高级程序语言第一次作业
  • 安装devc++过程的分享以及问题的记录
  • Linux之线程池 - 指南
  • zlog1
  • LlamaIndex检索调优实战:分块、HyDE、压缩等8个提效方法快速改善答案质量
  • 动火作业风险早预警!AI + 热成像技术筑牢防火安全线
  • 解题报告-P5664 [CSP-S2019] Emiya 家今天的饭