Segment tree beats 学习笔记
似乎时间不是很够了，就学一些最常用的吧。
不过这种题真的挺锻炼码力的
Gorgeous Sequence：区间取min，区间最值
给定长为 (n) 的序列。要求支持三种操作：
0 l r v：区间 (l...r) 对 (v) 取 (min)。
1 l r：区间求最大值
2 l r：区间求和(1 le n,m le 10^6)
维护最大值 (mx)，最大值个数(mxcnt)，次大值(smx)。
如果 (mx le v)，直接返回。
否则，如果 (smx < v < mx)，打标记。
否则，(v le smx),暴力递归。
复杂度：(O(n log n))
struct Data {
int ls, rs, mx, mxcnt, smx, tag;
ll sum;
Data(){ls = rs = mxcnt = sum = 0; tag = mx = smx = -1; }
inline void clear() { ls = rs = mxcnt = sum = 0; tag = mx = smx = -1; }
}dat[NN];
#define ls(x) dat[x].ls
#define rs(x) dat[x].rs
#define mx(x) dat[x].mx
#define mxcnt(x) dat[x].mxcnt
#define smx(x) dat[x].smx
#define tag(x) dat[x].tag
#define sum(x) dat[x].sum
int ttot, root;
inline void pushup(int cur) {
sum(cur) = sum(ls(cur)) + sum(rs(cur));
if (mx(ls(cur)) == mx(rs(cur))) {
mx(cur) = mx(ls(cur));
mxcnt(cur) = mxcnt(ls(cur)) + mxcnt(rs(cur));
smx(cur) = max(smx(ls(cur)), smx(rs(cur)));
} else if (mx(ls(cur)) > mx(rs(cur))) {
mx(cur) = mx(ls(cur));
mxcnt(cur) = mxcnt(ls(cur));
smx(cur) = max(smx(ls(cur)), mx(rs(cur)));
} else {
mx(cur) = mx(rs(cur));
mxcnt(cur) = mxcnt(rs(cur));
smx(cur) = max(smx(rs(cur)), mx(ls(cur)));
}
}
void build(int L, int R, int &cur) {
cur = ++ttot;
if (L == R) {
mx(cur) = h[L]; mxcnt(cur) = 1;
smx(cur) = tag(cur) = -1;
sum(cur) = h[L];
return ;
}
int mid = (L + R) >> 1;
build(L, mid, ls(cur)), build(mid + 1, R, rs(cur));
pushup(cur);
}
inline void pusht(int cur, int v) {
if (mx(cur) <= v) return ;//bug
sum(cur) += 1ll * mxcnt(cur) * (v - mx(cur));
mx(cur) = v; tag(cur) = v;
}
inline void pushdown(int cur) {
if (~tag(cur))//bug
pusht(ls(cur), tag(cur)), pusht(rs(cur), tag(cur)), tag(cur) = -1;
}
void modify_min(int L, int R, int l, int r, int v, int cur) {
if (mx(cur) <= v) return ;
if (l <= L && R <= r && smx(cur) < v) return pusht(cur, v), void();
int mid = (L + R) >> 1; pushdown(cur);
if (l <= mid) modify_min(L, mid, l, r, v, ls(cur));
if (r > mid) modify_min(mid + 1, R, l, r, v, rs(cur));
pushup(cur);
}
Cartesian Tree : 区间加区间取 (min)
（弱化版）支持区间加，区间取 (min)（或者区间取 (max)，但只会有一种），单点插入，全局求和。
(n le 150000)
离线后单点插入变为单点修改。
打标记的时候注意加法标记和 (min(max)) 标记的顺序。由于打加法标记的时候可以很方便地修改之前的 (min(max)) 标记，于是可以认为每时每刻一个点的标记都是先加法后 (min(max)) 的。注意没有 (min(max)) 标记的时候不要修改 (min(max)) 标记。
inline void pushadd(int cur, int v) {
if (!cnt(cur)) return ;
sum(cur) += 1ll * cnt(cur) * v;
mx(cur) += v; smx(cur) += v; addtag(cur) += v;
if (~mintag(cur)) mintag(cur) += v;//bug
}
inline void pushmin(int cur, int v) {
if (!cnt(cur) || mx(cur) <= v) return ;
sum(cur) += 1ll * mxcnt(cur) * (v - mx(cur));
mx(cur) = v; mintag(cur) = v;
}
inline void pushdown(int cur) {
if (addtag(cur))
pushadd(ls(cur), addtag(cur)), pushadd(rs(cur), addtag(cur)), addtag(cur) = 0;
if (~mintag(cur))
pushmin(ls(cur), mintag(cur)), pushmin(rs(cur), mintag(cur)), mintag(cur) = -1;
}
再放一个区间取 (max) 的完整版：
namespace Seg_L {//max, add, pointset, getsum
struct Data {
int ls, rs, cnt, mn, mncnt, smn, maxtag, addtag;
ll sum;
Data() { ls = rs = cnt = mncnt = sum = addtag = 0; mn = smn = maxtag = inf; }
}Dat[N << 2];
#define ls(x) Dat[x].ls
#define rs(x) Dat[x].rs
#define cnt(x) Dat[x].cnt
#define mn(x) Dat[x].mn
#define mncnt(x) Dat[x].mncnt
#define smn(x) Dat[x].smn
#define maxtag(x) Dat[x].maxtag
#define addtag(x) Dat[x].addtag
#define sum(x) Dat[x].sum
int ttot;
inline void pushup(int cur) {
sum(cur) = sum(ls(cur)) + sum(rs(cur));
cnt(cur) = cnt(ls(cur)) + cnt(rs(cur));
if (mn(ls(cur)) == mn(rs(cur))) {
mn(cur) = mn(ls(cur)); mncnt(cur) = mncnt(ls(cur)) + mncnt(rs(cur));
smn(cur) = min(smn(ls(cur)), smn(rs(cur)));//bug
} else if (mn(ls(cur)) < mn(rs(cur))) {
mn(cur) = mn(ls(cur)), mncnt(cur) = mncnt(ls(cur));
smn(cur) = min(smn(ls(cur)), mn(rs(cur)));
} else {
mn(cur) = mn(rs(cur)), mncnt(cur) = mncnt(rs(cur));
smn(cur) = min(smn(rs(cur)), mn(ls(cur)));
}
}
inline void pushadd(int cur, int v) {
if (!cnt(cur)) return ;
sum(cur) += 1ll * cnt(cur) * v;
mn(cur) += v; smn(cur) += v; addtag(cur) += v;
if (maxtag(cur) != inf) maxtag(cur) += v;//bug
}
inline void pushmax(int cur, int v) {
if (!cnt(cur) || mn(cur) >= v) return ;
sum(cur) += 1ll * mncnt(cur) * (v - mn(cur));
mn(cur) = v; maxtag(cur) = v;
}
inline void pushdown(int cur) {
if (addtag(cur))
pushadd(ls(cur), addtag(cur)), pushadd(rs(cur), addtag(cur)), addtag(cur) = 0;
if (maxtag(cur) != inf)
pushmax(ls(cur), maxtag(cur)), pushmax(rs(cur), maxtag(cur)), maxtag(cur) = inf;
}
void modify_max(int L, int R, int l, int r, int v, int cur) {
if (!cur || mn(cur) >= v) return ;
if (l <= L && R <= r && smn(cur) > v) return pushmax(cur, v), void();//bug
int mid = (L + R) >> 1; pushdown(cur);
if (l <= mid) modify_max(L, mid, l, r, v, ls(cur));
if (r > mid) modify_max(mid + 1, R, l, r, v, rs(cur));
pushup(cur);
}
void modify_add(int L, int R, int l, int r, int v, int cur) {
if (!cur) return ;
if (l <= L && R <= r) return pushadd(cur, v), void();
int mid = (L + R) >> 1; pushdown(cur);
if (l <= mid) modify_add(L, mid, l, r, v, ls(cur));
if (r > mid) modify_add(mid + 1, R, l, r, v, rs(cur));
pushup(cur);
}
void modify_point(int L, int R, int pos, int v, int &cur) {
if (!cur) cur = ++ttot;
if (L == R) return sum(cur) = mn(cur) = v, mncnt(cur) = 1, cnt(cur) = 1, void();
int mid = (L + R) >> 1; pushdown(cur);
if (pos <= mid) modify_point(L, mid, pos, v, ls(cur));
else modify_point(mid + 1, R, pos, v, rs(cur));
pushup(cur);
}
}