【学习笔记】吉司机线段树 / 势能分析线段树
Foreword
吉司机线段树是由吉如一老师在集训队论文中提出的一种可以维护区间取
Basic tips
结合例题可以更好理解吉司机线段树。
例题:P6242。
题面给定数列
-
-
- 询问
\sum\limits_{i=l}^{r}{A_i} 。 - 询问
\max\limits_{i=l}^{r}{A_i} 。 - 询问
\max\limits_{i=l}^{r}{B_i} 。
每次操作完成后都更新
显然最棘手的问题就是如何维护
首先我们考虑懒标记如何规划,分别记四个懒标记表示
以下记
同时我们需要记录区间严格次大值,因为在操作
同时在下传懒标记时,由于记录的是最大值加的最多的那一次,故需要记录最大值的出现次数,记
操作
吉司机一大特点就是码量较大,所以结合代码理解会更深入。
采用结构体封装的方法会清晰一点。
以下代码:
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace FASTIO {
inline int read() {
int res = 0, f = 1;
char ch = getchar();
while (!isdigit (ch)) f = ch == '-' ? -1 : 1, ch = getchar();
while (isdigit (ch)) res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
return res * f;
}
inline void write (int x) {
int st[33], top = 0;
if (x < 0) x = -x, putchar ('-');
do { st[top ++] = x % 10, x /= 10; } while (x);
while (top) putchar (st[-- top] + '0');
}
} using namespace FASTIO;
const int MAXN = 5e5 + 10, inf = 0x3f3f3f3f3f3f3f3f;
int n, m, A[MAXN]
namespace Beats {
struct Segmentree {
int l, r, Val, maxfst, maxsec, maxhis, cnt;
int lazy1, lazy2, lazy3, lazy4;
/* 1 维护 A 中最大值加的最多的一次,2 维护 B 中的,3 维护 A 中除最大值外的,4 维护 B 中的 */
void clearLazy() { lazy1 = lazy2 = lazy3 = lazy4 = 0; }
} Seg[MAXN << 2];
#define lson rt << 1
#define rson rt << 1 | 1
void pushup (int rt) {
Seg[rt].maxfst = max (Seg[lson].maxfst, Seg[rson].maxfst);
Seg[rt].maxhis = max (Seg[lson].maxhis, Seg[rson].maxhis);
Seg[rt].Val = Seg[lson].Val + Seg[rson].Val;
if (Seg[lson].maxfst == Seg[rson].maxfst) {
Seg[rt].maxsec = max (Seg[lson].maxsec, Seg[rson].maxsec);
Seg[rt].cnt = Seg[lson].cnt + Seg[rson].cnt;
}
if (Seg[lson].maxfst > Seg[rson].maxfst) {
Seg[rt].maxsec = max (Seg[lson].maxsec, Seg[rson].maxfst);
Seg[rt].cnt = Seg[lson].cnt;
}
if (Seg[lson].maxfst < Seg[rson].maxfst) {
Seg[rt].maxsec = max (Seg[lson].maxfst, Seg[rson].maxsec);
Seg[rt].cnt = Seg[rson].cnt;
}
return;
}
void Build (int l, int r, int rt) {
Seg[rt].l = l, Seg[rt].r = r;
if (l == r) {
Seg[rt].maxfst = Seg[rt].Val = Seg[rt].maxhis = A[l];
Seg[rt].maxsec = -inf, Seg[rt].cnt = 1;
return;
}
int mid = l + r >> 1;
Build (l, mid, lson), Build (mid + 1, r, rson);
pushup (rt);
}
void update (int rt, int a, int b, int c, int d) { /* a 区间 maxfst 加,b 区间 maxhis 加, c 区间 maxsec 加,d 区间 maxhis_sec 加 */
Seg[rt].Val += (a * Seg[rt].cnt + c * (Seg[rt].r - Seg[rt].l + 1 - Seg[rt].cnt));
Seg[rt].maxhis = max (Seg[rt].maxhis, Seg[rt].maxfst + b);
Seg[rt].maxfst += a;
if (Seg[rt].maxsec != -inf) Seg[rt].maxsec += c;
Seg[rt].lazy2 = max (Seg[rt].lazy2, Seg[rt].lazy1 + b), Seg[rt].lazy1 += a;
Seg[rt].lazy4 = max (Seg[rt].lazy4, Seg[rt].lazy3 + d), Seg[rt].lazy3 += c;
return;
}
void pushdown (int rt) {
int maxVal = max (Seg[lson].maxfst, Seg[rson].maxfst);
if (maxVal == Seg[lson].maxfst)
update (lson, Seg[rt].lazy1, Seg[rt].lazy2, Seg[rt].lazy3, Seg[rt].lazy4);
else
update (lson, Seg[rt].lazy3, Seg[rt].lazy4, Seg[rt].lazy3, Seg[rt].lazy4);
if (maxVal == Seg[rson].maxfst)
update (rson, Seg[rt].lazy1, Seg[rt].lazy2, Seg[rt].lazy3, Seg[rt].lazy4);
else
update (rson, Seg[rt].lazy3, Seg[rt].lazy4, Seg[rt].lazy3, Seg[rt].lazy4);
return Seg[rt].clearLazy();
}
void ModifySum (int ql, int qr, int rt, int k) {
int l = Seg[rt].l, r = Seg[rt].r;
// if (ql > l || qr < r) return;
if (ql <= l && qr >= r)
return update(rt, k, k, k, k);
int mid = l + r >> 1;
pushdown (rt);
if (ql <= mid)
ModifySum (ql, qr, lson, k);
if (qr > mid)
ModifySum (ql, qr, rson, k);
pushup (rt);
return;
}
void ModifyMin (int ql, int qr, int rt, int k) {
int l = Seg[rt].l, r = Seg[rt].r;
if (Seg[rt].maxfst <= k) return;
if (ql <= l && qr >= r && Seg[rt].maxsec < k)
return update (rt, k - Seg[rt].maxfst, k - Seg[rt].maxfst, 0, 0);
int mid = l + r >> 1;
pushdown (rt);
if (ql <= mid)
ModifyMin (ql, qr, lson, k);
if (qr > mid)
ModifyMin (ql, qr, rson, k);
pushup (rt);
return;
}
int querySum (int ql, int qr, int rt) {
int l = Seg[rt].l, r = Seg[rt].r;
// if (ql > l || qr < r) return 0;
if (ql <= l && qr >= r)
return Seg[rt].Val;
int mid = l + r >> 1, tmpSum = 0;
pushdown (rt);
if (ql <= mid)
tmpSum += querySum (ql, qr, lson);
if (qr > mid)
tmpSum += querySum (ql, qr, rson);
return tmpSum;
}
int queryMax (int ql, int qr, int rt) {
int l = Seg[rt].l, r = Seg[rt].r;
// if (ql > l || qr < r) return -inf;
if (ql <= l && qr >= r)
return Seg[rt].maxfst;
int mid = l + r >> 1, tmpMax = -inf;
pushdown (rt);
if (ql <= mid)
tmpMax = max (tmpMax, queryMax (ql, qr, lson));
if (qr > mid)
tmpMax = max (tmpMax, queryMax (ql, qr, rson));
return tmpMax;
}
int queryMax_his (int ql, int qr, int rt) {
int l = Seg[rt].l, r = Seg[rt].r;
// if (ql > l || qr < r) return -inf;
if (ql <= l && qr >= r)
return Seg[rt].maxhis;
int mid = l + r >> 1, tmpMax_his = -inf;
pushdown (rt);
if (ql <= mid)
tmpMax_his = max (tmpMax_his, queryMax_his (ql, qr, lson));
if (qr > mid)
tmpMax_his = max (tmpMax_his, queryMax_his (ql, qr, rson));
return tmpMax_his;
}
} using namespace Beats;
signed main() {
/*
freopen ("P6242_1.in","r",stdin);
freopen ("Ans.out","w",stdout);
*/
n = read(), m = read();
for (int i = 1; i <= n; i ++) A[i] = read();
Build (1, n, 1);
while (m --) {
int opt = read(), l = read(), r = read(), k;
if (opt == 1) {
k = read();
ModifySum (l, r, 1, k);
}
if (opt == 2) {
k = read();
ModifyMin (l, r, 1, k);
}
if (opt == 3)
write (querySum (l, r, 1)), putchar ('\n');
if (opt == 4)
write (queryMax (l, r, 1)), putchar ('\n');
if (opt == 5)
write (queryMax_his (l, r, 1)), putchar ('\n');
}
return 0;
}
总时间复杂度
例题:U180387 CTSN loves segment tree
我们将需要查询的
对此,我们分别计其为
在下放最小值、加法标记时跟模板一样,对于
在从左右儿子节点更新了根节点的最大值后,我们分
以下根节点记为
对于左儿子,记为
-
-
-
-
lson$ 中 $A$ 中最大值、$B$ 中最大值与 $rt$ 均不相等,故 $cVal_{0,1},cVal_{1,0},cVal_{1,1}$ 均不存在,赋为 $-inf$,更新 $cVal_{0,0}
对于右儿子,同理做,只需要每次取
区间查询的最终结果即为四种情况的最大值:
总复杂度
#include <bits/stdc++.h>
#define int long long
using namespace std;
namespace FASTIO {
inline int read() {
int res = 0, f = 1;
char ch = getchar();
while (!isdigit (ch)) f = ch == '-' ? -1 : 1, ch = getchar();
while (isdigit (ch)) res = (res << 1) + (res << 3) + (ch ^ 48), ch = getchar();
return res * f;
}
inline void write (int x) {
int st[33], top = 0;
if (x < 0) x = -x, putchar ('-');
do { st[top ++] = x % 10, x /= 10; } while (x);
while (top) putchar (st[-- top] + '0');
}
} using namespace FASTIO;
/* Beginning time: 15:16 */
const int MAXN = 3e5 + 10, inf = 0x7f7f7f7f7f7f7f7f;
int n, m, A[MAXN], B[MAXN];
namespace Beats {
struct Segment {
int l, r, minLazy[2], cVal[2][2], maxVal[2], maxSec[2], AddLazy[2]; /* 0 : A. 1 : B */
void clearLazy () { minLazy[0] = minLazy[1] = inf, AddLazy[0] = AddLazy[1] = 0; }
}Seg[MAXN << 2];
#define lson rt << 1
#define rson rt << 1 | 1
inline int GetAns (int rt) { return max ({Seg[rt].cVal[0][0], Seg[rt].cVal[0][1], Seg[rt].cVal[1][0], Seg[rt].cVal[1][1]}); }
inline void updateMin (int rt, int Tag, bool id) {
if (Seg[rt].maxVal[id] <= Tag) return;
Seg[rt].cVal[1][1] += (Seg[rt].cVal[1][1] != -inf) ? (Tag - Seg[rt].maxVal[id]) : 0;
Seg[rt].cVal[!id][id] += (Seg[rt].cVal[!id][id] != -inf) ? (Tag - Seg[rt].maxVal[id]) : 0;
Seg[rt].maxVal[id] = Seg[rt].minLazy[id] = Tag;
return;
}
inline void updateSum (int rt, int Tag, bool id) {
for (int i = 0; i < 2; i ++) {
for (int j = 0; j < 2; j ++)
Seg[rt].cVal[i][j] += (Seg[rt].cVal[i][j] != -inf) ? (Tag) : 0;
}
Seg[rt].maxVal[id] += Tag;
Seg[rt].maxSec[id] += (Seg[rt].maxSec[id] != -inf) ? Tag : 0;
Seg[rt].minLazy[id] += (Seg[rt].minLazy[id] != inf) ? Tag : 0;
Seg[rt].AddLazy[id] += Tag;
return;
}
inline void pushup (int rt) {
Segment &ls = Seg[lson], &rs = Seg[rson], &root = Seg[rt];
for (int i = 0; i < 2; i ++) {
root.maxVal[i] = max (ls.maxVal[i], rs.maxVal[i]);
if (ls.maxVal[i] == rs.maxVal[i])
root.maxSec[i] = max (ls.maxSec[i], rs.maxSec[i]);
else if (ls.maxVal[i] > rs.maxVal[i])
root.maxSec[i] = max (ls.maxSec[i], rs.maxVal[i]);
else
root.maxSec[i] = max (ls.maxVal[i], rs.maxSec[i]);
}
if (root.maxVal[0] == ls.maxVal[0] && root.maxVal[1] == ls.maxVal[1]) {
root.cVal[0][0] = ls.cVal[0][0], root.cVal[0][1] = ls.cVal[0][1];
root.cVal[1][0] = ls.cVal[1][0], root.cVal[1][1] = ls.cVal[1][1];
}
else if (root.maxVal[0] == ls.maxVal[0] && root.maxVal[1] != ls.maxVal[1]) {
root.cVal[1][1] = root.cVal[0][1] = -inf;
root.cVal[1][0] = max (ls.cVal[1][1], ls.cVal[1][0]);
root.cVal[0][0] = max (ls.cVal[0][1], ls.cVal[0][0]);
}
else if (root.maxVal[0] != ls.maxVal[0] && root.maxVal[1] == ls.maxVal[1]) {
root.cVal[1][1] = root.cVal[1][0] = -inf;
root.cVal[0][1] = max (ls.cVal[1][1], ls.cVal[0][1]);
root.cVal[0][0] = max (ls.cVal[1][0], ls.cVal[0][0]);
}
else {
root.cVal[1][1] = root.cVal[1][0] = root.cVal[0][1] = -inf;
root.cVal[0][0] = max ({ls.cVal[0][0], ls.cVal[1][0], ls.cVal[0][1], ls.cVal[1][1]});
}
if (root.maxVal[0] == rs.maxVal[0] && root.maxVal[1] == rs.maxVal[1]) {
root.cVal[0][0] = max (root.cVal[0][0], rs.cVal[0][0]);
root.cVal[0][1] = max (root.cVal[0][1], rs.cVal[0][1]);
root.cVal[1][0] = max (root.cVal[1][0], rs.cVal[1][0]);
root.cVal[1][1] = max (root.cVal[1][1], rs.cVal[1][1]);
}
else if (root.maxVal[0] == rs.maxVal[0] && root.maxVal[1] != rs.maxVal[1]) {
root.cVal[1][0] = max ({root.cVal[1][0], rs.cVal[1][0], rs.cVal[1][1]});
root.cVal[0][0] = max ({root.cVal[0][0], rs.cVal[0][0], rs.cVal[0][1]});
}
else if (root.maxVal[0] != rs.maxVal[0] && root.maxVal[1] == rs.maxVal[1]) {
root.cVal[0][1] = max ({root.cVal[0][1], rs.cVal[0][1], rs.cVal[1][1]});
root.cVal[0][0] = max ({root.cVal[0][0], rs.cVal[1][0], rs.cVal[0][0]});
}
else
root.cVal[0][0] = max ({root.cVal[0][0], rs.cVal[0][0], rs.cVal[0][1], rs.cVal[1][0], rs.cVal[1][1]});
return;
}
void Build (int l, int r, int rt) {
Seg[rt].l = l, Seg[rt].r = r;
Seg[rt].clearLazy();
if (l == r) {
Seg[rt].cVal[1][1] = A[l] + B[l];
Seg[rt].cVal[0][0] = Seg[rt].cVal[0][1] = Seg[rt].cVal[1][0] = -inf;
Seg[rt].maxVal[0] = A[l], Seg[rt].maxVal[1] = B[l];
Seg[rt].maxSec[0] = Seg[rt].maxSec[1] = -inf;
return;
}
int mid = l + r >> 1;
Build (l, mid, lson);
Build (mid + 1, r, rson);
pushup (rt);
}
inline void pushdown (int rt) {
for (int i = 0; i < 2; i ++) {
if (Seg[rt].AddLazy[i]) {
updateSum (lson, Seg[rt].AddLazy[i], i);
updateSum (rson, Seg[rt].AddLazy[i], i);
}
}
for (int i = 0; i < 2; i ++) {
if (Seg[rt].minLazy[i] != inf) {
updateMin (lson, Seg[rt].minLazy[i], i);
updateMin (rson, Seg[rt].minLazy[i], i);
}
}
return Seg[rt].clearLazy();
}
void ModifyMin (int ql, int qr, int rt, int k, bool id) {
int l = Seg[rt].l, r = Seg[rt].r;
if (Seg[rt].maxVal[id] <= k) return;
if (ql <= l && qr >= r && Seg[rt].maxSec[id] < k)
return updateMin (rt, k, id);
int mid = l + r >> 1;
pushdown (rt);
if (ql <= mid)
ModifyMin (ql, qr, lson, k, id);
if (qr > mid)
ModifyMin (ql, qr, rson, k, id);
pushup (rt);
}
void ModifySum (int ql, int qr, int rt, int k, bool id) {
int l = Seg[rt].l, r = Seg[rt].r;
if (ql <= l && qr >= r)
return updateSum (rt, k, id);
int mid = l + r >> 1;
pushdown (rt);
if (ql <= mid)
ModifySum (ql, qr, lson, k, id);
if (qr > mid)
ModifySum (ql, qr, rson, k, id);
pushup (rt);
}
int query (int ql, int qr, int rt) {
int l = Seg[rt].l, r = Seg[rt].r;
if (ql <= l && qr >= r)
return GetAns (rt);
int mid = l + r >> 1, tmpMax = -inf;
pushdown (rt);
if (ql <= mid)
tmpMax = max (tmpMax, query (ql, qr, lson));
if (qr > mid)
tmpMax = max (tmpMax, query (ql, qr, rson));
return tmpMax;
}
} using namespace Beats;
signed main() {
n = read(), m = read();
for (int i = 1; i <= n; i ++) A[i] = read();
for (int i = 1; i <= n; i ++) B[i] = read();
Build (1, n, 1);
while (m --) {
int opt = read(), l = read(), r = read(), k;
if (opt == 1)
ModifyMin (l, r, 1, k = read(), 0);
if (opt == 2)
ModifyMin (l, r, 1, k = read(), 1);
if (opt == 3)
ModifySum (l, r, 1, k = read(), 0);
if (opt == 4)
ModifySum (l, r, 1, k = read(), 1);
if (opt == 5)
write (query (l, r, 1)), putchar ('\n');
}
return 0;
}
综上看来,吉司机线段树最主要的想法就是通过懒标记去维护和更新值。
Practise
站内习题:
P10639 BZOJ4695 最佳女选手
P4314 CPU 监控
站外习题:
UOJ #169.【UR #11】元旦老人与数列
UOJ #164.【清华集训2015】V
LOJ #6029.「雅礼集训 2017 Day1」市场